Multiplication time in BigInteger

Question

My mini benchmark:

import java.math.*; import java.util.*; import java.io.*; public class c {     static Random rnd = new Random();     public static String addDigits(String a, int n)     {         if(a==null) return null;         if(n<=0) return a;         for(int i=0; i<n; i++)             a+=rnd.nextInt(10);         return a;     }     public static void main(String[] args) throws IOException     {         int n = 10000; \\number of iterations         int k = 10;    \\number of digits added at each iteration          BigInteger a;         BigInteger b;          String as = "";         String bs = "";         as += rnd.nextInt(9)+1;         bs += rnd.nextInt(9)+1;         a = new BigInteger(as);         b = new BigInteger(bs);         FileWriter fw = new FileWriter("c.txt");         long t1 = System.nanoTime();         a.multiply(b);         long t2 = System.nanoTime();         //fw.write("1,"+(t2-t1)+"\n");         if(k>0) {             as = addDigits(as, k-1);             bs = addDigits(as, k-1);         }         for(int i=0; i<n; i++)         {             a = new BigInteger(as);             b = new BigInteger(bs);             t1 = System.nanoTime();             a.multiply(b);             t2 = System.nanoTime();             fw.write(((i+1)*k)+","+(t2-t1)+"\n");             if(i < n-1)             {                 as = addDigits(as, k);                 bs = addDigits(as, k);             }             System.out.println((i+1)*k);         }                 fw.close();     } } 

It measures multiplication time of n-digit BigInteger

Result:

You can easily see the trend but why there is so big noise above 50000 digits? It is because of garbage collector or is there something else that affects my results? When performing the test, there were no other applications running.

Result from test with only odd digits. The test was shorter (n=1000, k=100)

Odd digits (n=10000, k=10)

As you can see there is a huge noise between 65000 and 70000. I wonder why...

Odd digits (n=10000, k=10), System.gc() every 1000 iterations Results in noise between 50000-70000

Answer 1

I also suspect this is a JVM warmup effect. Not warmup involving classloading or the JIT compiler, but warmup of the heap.

Put a (java) loop around the whole benchmark, and run it a number of times. (If this gives you the same graphs as before ... you will have evidence that this is not a warmup effect. Currently you don't have any empirical evidence one way or the other.)

---

Another possibility is that the noise is caused by your benchmark's interactions with the OS and/or other stuff running on the machine.

• You are writing your timing data to an unbuffered stream. That means LOTS of syscalls, and (potentially) lots of fine-grained disc writes.
• You are making LOTS of calls to nanoTime(), and that might introduce noise.
• If something else is running on your machine (e.g. you are web browsing) that will slow down your benchmark for a bit and introduce noise.
• There could be competition over physical memory ... if you've got too much running on your machine for the amount of RAM.

---

Finally, a certain amount of noise is inevitable, because each of those multiply calls generates garbage, and the garbage collector is going to need to work to deal with it.

---

Finally finally, if you manually run the garbage collector (or increase the heap size) to "smooth out" the data points, what you are actually doing is concealing one of the costs of multiply calls. The resulting graphs looks nice, but it is misleading:

• The noisiness reflects what will happen in real life.
• The true cost of the multiply actually includes the amortized cost of running the GC to deal with the garbage generated by the call.

To get a measurements that reflect the way that BigInteger behaves in real life, you need to run the test a large number of times, calculate average times and fit a curve to the average data-points.

Remember, the real aim of the game is to get scientifically valid results ... not a smooth curve.

Answer 2

If you do a microbenchmark, you must "warm up" the JVM first to let the JIT optimize the code, and then you can measure the performance. Otherwise you are measuring the work done by the JIT and that can change the result on each run.

The "noise" happens probably because the cache of the CPU is exceeded and the performance starts degrading.