I get different running times for bubblesort in Java

Question

I have created a new bubble sort project and i want to know how much time it takes. Hence, I have added a getTime() method, which returns nanotime. I have also created an array with 9 static values. When I run my code i get different running times (ie: generally i get 3849 ns but sometimes 6432 or 4277 ns). How can this be?

My code is as follows:

long time2;
public void sort(int[] dizi){
    long time = System.nanoTime();
    for (int i = dizi.length-1; i >0; i--) {
        for (int j = 0; j < i; j++) {
            if(dizi[j]>dizi[j+1]){
                super.swap(dizi, j, j+1);
            }
        }
    }
    time2 = System.nanoTime() - time;
}
public long getTime(long time){
      return time;
}
main(){
      BubbleSort bubbleSort = new BubbleSort();
      int[] arr = {4,2,1,8,9,5,3,7,6};
      bubbleSort.sort(arr);
      Sysout(bubbleSort.getTime(time2));
}

There can be a lot of variables that could cause your times to be different such as the JVM doing garbage collection, your operating system performing some other task, etc. — blamonet, Mar 17 '13 at 23:49
easterbunny : nothing changed, first my trial 13204534055 second 13230923476 blamonet : if i see true, this situation related with my system and a normal exception — Emre Çıklatekerlio, Mar 18 '13 at 00:00
Java documentation for System.nanoTime() says: "... This method provides nanosecond precision, but not necessarily nanosecond accuracy. No guarantees are made about how frequently values change. ...". — naitoon, Mar 18 '13 at 00:24
Check this out: http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — Cory Kendall, Mar 18 '13 at 00:42

Chris Cooper · Answer 1 · 2013-03-18T00:39:49.060

Unless the hardware you are running on can accurately measure nanoseconds (hint - it can't), there is no way for Java to give you an accurate time stamp in ns.

On top of that, Java is not deterministic with regard to run time of code. At any time your code can be interrupted by a multitude of other house keeping tasks that the JVM is running, most notably garbage collection.

There is also the Hot Spot compiler, which will identify a piece of byte code being run very often, and will recompile it on the fly to native code, this causes a pause, but then performance is improved in later runs. If you want to remove the Hot Spot effect from the equation you need to soak test your code by running the code a few tens of thousands of times to make sure that it has been compiled to native code, then do the actual timed run to see how efficient the code is.

The end result as you have seen is that the code can be run several times, produce the same results but take differing amounts of time to return that result, and the bad news for OCD coders everywhere is that you will never make the number the same for each test run.

For performance testing like this, I would typically expect to run the code maybe 1,000 times and record fastest time, slowest time, mean time and standard deviation on my timings to get an accurate idea of the run time for a specific piece of code. If I get unexpected slow runs, I then look for full GC events in the logs when the verbose GC options are enabled on the VM.

Oh and don't forget that the OS your JVM is running on is providing a variable amount of runtime too, the OS has house keeping taks it is running too.

score 0 · Accepted Answer · answered Mar 18 '13 at 00:46

There are multiple factors that may affect the result.

JVM may start running garbage collection (that's definitely not your case), while running your program JVM may allocate some memory and the underlying OS service finds out that it should swap some memory, because it has run out of available RAM, etc...

None of available JVMs (for Mac, Windows and Linux/Unix) runs on a real time system, but even if one day it does - your JVM may decide that your program has lower priority compared to some JVM activity.

Try some lager array, the results will be more stable.

I get different running times for bubblesort in Java

2 Answers2