1

I'm testing branch prediction, the code like this:

//first loop
int sortedSum = 0;
long sortedStartTime = System.nanoTime();
for (int i = 0; i < sortedArray.length; i++) {
    if (sortedArray[i] < 0) {
        sortedSum += sortedArray[i];
    }
}
long sortedTime = System.nanoTime() - sortedStartTime;

//second loop
int randomSum = 0;
long randomStartTime = System.nanoTime();
for (int i = 0; i < randomArray.length; i++) {
    if (randomArray[i] < 0) {
        randomSum += randomArray[i];
    }
}
long randomTime = System.nanoTime() - randomStartTime;

System.out.println("random time: " + randomTime);
System.out.println("sorted time: " + sortedTime);

It's simple print the time about each for loop.

Note that the sortedSum and randomSum is assigned in the loop but never accessed.

We don't talk about the branch prediction here, but the output result. The output is:

random time: 32
sorted time: 1595942

Then, I put the second for loop before the first(first randomArray loop, second sortedArray). The output is:

random time: 1541919
sorted time: 40

It seems the JVM doesn't execute the second loop. I decompile the class file, the decompiler doesn't erase anything.

Why? And why JVM DO execute the first loop?

P.S. environment is:

Ubuntu 12.04 LTS
java version "1.7.0_11"
Java(TM) SE Runtime Environment (build 1.7.0_11-b21)
Java HotSpot(TM) 64-Bit Server VM (build 23.6-b04, mixed mode)
HUA Di
  • 901
  • 8
  • 11
  • During your first loop, the JVM is just warming up. Make a third loop to warm up the JVM before you measure the other two. – Ingo Mar 06 '14 at 11:44
  • http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java – kiheru Mar 06 '14 at 11:45
  • The question topic is wrong as JVM is actually executing both loops. It is timings that are under question. – Paul Verest Mar 07 '14 at 11:58

3 Answers3

2

When you runtime code enough it triggers the whole method to be optimised (in the background)

This means if you have a loop which iterates over 10K times and it doesn't do anything, you are actually timing how long it takes to detect the loop doesn't do any thing and replace it.

In the case of the second loop, the method has already been optimise away, in either case.

I suggest you have an outer loop which runs this test 3 times and you should see what I mean.

The reason it can drop the loop is;

  • and you don't use the value calculated, so the calculateSum can be dropped
  • then the array access isn't needed
  • then the loop itself isn't need.
Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • Yes, running the test several times (like puting the code inside function to cal) – Paul Verest Mar 06 '14 at 12:02
  • @PaulVerest Running the test from the start several times, is not like running it several times in a loop. For performance it can be very different. – Peter Lawrey Mar 06 '14 at 12:07
0

I suppose this:

We are talking about Just-In-Time Compilation here. The compiler optimizes only some time after he started executing. I would guess that he optimizes everything away. The first loop is executed as long as the JIT compiler didn't kick in yet.

kutschkem
  • 7,826
  • 3
  • 21
  • 56
0

I think it has nothing to do with Java, but CPU, memory and caches:

At first System.nanoTime() app is in memory, the executing code in CPU cache level 1 (at the speed of CPU). When program starts to execute, CPU will start putting memory blocks ahead in level 1 or 2 cashes, so sequential read/write will see increase in speed.

Try using arrays of size much larger then CPU level 3 cache, e.g. 10MB and randomized indexes, that is prepare array of indexes in random order. That will eliminate CPU cashing effects.

Paul Verest
  • 60,022
  • 51
  • 208
  • 332