Why does the execution timing of certain functions vary greatly?

Question

My code:

import java.math.BigDecimal;
public class ScienceFair {

private static long NewtonMethod()
{
    BigDecimal TWO = new BigDecimal(2);
    BigDecimal SQRT_TWO = new BigDecimal("1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727");
    BigDecimal TOLERANCE = BigDecimal.ONE.scaleByPowerOfTen(-100);

    long start = System.nanoTime();

    BigDecimal a = new BigDecimal(1);

    while(a.subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) {
        a = a.add(TWO.divide(a, 100, BigDecimal.ROUND_HALF_UP)).divide(TWO);
    }

    return System.nanoTime() - start;
}

private static long MidpointMethod()
{
    BigDecimal TWO = new BigDecimal(2);
    BigDecimal SQRT_TWO = new BigDecimal("1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727");
    BigDecimal TOLERANCE = BigDecimal.ONE.scaleByPowerOfTen(-100);

    long start = System.nanoTime();

    BigDecimal a = new BigDecimal(1);
    BigDecimal b = new BigDecimal(2);
    while(a.add(b).divide(TWO).subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) {
        if(a.multiply(a).subtract(TWO).abs().compareTo(b.multiply(b).subtract(TWO).abs()) == 1)
        {
            a = a.add(b).divide(TWO);
        }
        else
        {
            b = a.add(b).divide(TWO);
        }
    }
    return System.nanoTime() - start;
}
private static long SecantMethod()
{
    BigDecimal TWO = new BigDecimal(2);
    BigDecimal SQRT_TWO = new BigDecimal("1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727");
    BigDecimal TOLERANCE = BigDecimal.ONE.scaleByPowerOfTen(-100);

    long start = System.nanoTime();

    BigDecimal a = new BigDecimal(1);
    BigDecimal b = new BigDecimal(2);
    BigDecimal b_old = new BigDecimal(2);
    while(a.add(b).divide(TWO).subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) {
        b_old = b;
        b = a.multiply(b).add(TWO).divide(a.add(b), 100, BigDecimal.ROUND_HALF_UP);
        a = b_old;
    }

    return System.nanoTime() - start;
}

public static void main(String[] args) {
    double a = 0;
    int trials = 100;
    for(int i=1; i<= trials; i++)
    {
        a += (NewtonMethod() / 10e6);
    }
    System.out.printf("Newton's Method: %f\n", a/trials);
    a = 0;
    for(int i=1; i<= trials; i++)
    {
        a += (MidpointMethod() / 10e6);
    }
    System.out.printf("Midpoint Method: %f\n", a/trials);
    a = 0;
    for(int i=1; i<= trials; i++)
    {
        a += (SecantMethod() / 10e6);
    }
    System.out.printf("Secant Method: %f\n", a/trials);
}
}

is designed to run the Newton Method, the Midpoint Method, and the Secant Method to find the amount of time it takes to approximate the square root of two to 100 decimal places.

It runs 100 trials of each of them, and averages them to output the number of milliseconds taken.

The Midpoint method is always around 1.5 seconds. However, the Newton method and the Secant method vary greatly, ranging from 0.08 to 0.14 seconds (about double). Why is this happening?

Edit: Here is what I tried now (only for NewtonMethod)

public class ScienceFairTwo {
public static void main(String[] args) throws Exception {
Runnable NewtonMethod = new Runnable()          
 {
        public void run()
        {
                BigDecimal TWO = new BigDecimal(2);
                BigDecimal SQRT_TWO = new BigDecimal("1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727");
                BigDecimal TOLERANCE = BigDecimal.ONE.scaleByPowerOfTen(-100);

                long start = System.nanoTime();
                BigDecimal a = new BigDecimal(1);

                while(a.subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) {
                    a = a.add(TWO.divide(a, 100, BigDecimal.ROUND_HALF_UP)).divide(TWO);
                }
        }
    };
        System.out.println("Newton's Method: " + new Benchmark(NewtonMethod));
}
}

Try to run 1000 trials without measuring, then 1000 trials with measuring. The JIT plays a significant role, and it needs many executions to detect Hotspots and compile them. Also, your tests allocate many objects, so the GC could kick in a slow one of the tests. I suggest using a real micro-benchmarking framework like Caliper. — JB Nizet, Nov 02 '13 at 23:16

score 4 · Answer 1 · edited May 23 '17 at 12:13

In general, benchmarking Java code is difficult. Your simple benchmark is not reliable enough.

I can see three problems with your approach (there can be more):

You are not letting JVM to "warm up". When the same code runs many times, JVM starts to optimize things. For example inlining and JIT starts to kick off.
During your time measurement GC can turn on. It can mess up the results significantly.
JVM loads classes only when they're first used. So, the first method using java.math.BigDecimal is unlucky, because it wastes time for loading that class into memory. Other methods don't have this penalty - BigDecimal is already loaded.

I recommend you two things:

Reading this great article: Robust Java benchmarking.
Using reliable Java benchmarking framework - Caliper. It automatically generates nice reports visible online - an example referring to this question.

(When you do the benchmark correctly - post a link in the comment. I would like to see how your methods perform)

Hi. I tried only the Newton Iteration, and got an error saying Benchmark cannot be resolved to a type. See my edit in the question — Akshaj Kadaveru, Nov 03 '13 at 01:27
1. Make sure you imported Benchmark class properly and referenced Caliper jar. 2. Look at this [example](http://code.google.com/p/caliper/source/browse/tutorial/Tutorial.java), you should have methods `timeNewton`, `timeMidpoint`, `timeSecant`. — Adam Stelmaszczyk, Nov 03 '13 at 08:17

Why does the execution timing of certain functions vary greatly?

1 Answers1