CODEWITHSUNDEEP
javaperformance-testing
Akshaj Kadaveru
Akshaj Kadaveru

Reputation: 135

Why does the execution timing of certain functions vary greatly?

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));
}
}

Upvotes: 1

Views: 161

Answers (1)

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19837

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):

  1. 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.
  2. During your time measurement GC can turn on. It can mess up the results significantly.
  3. 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:

  1. Reading this great article: Robust Java benchmarking.
  2. 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)

Upvotes: 4

Related Questions