Java curious Loop Performance

Question

I have a big problem while evaluate my java code. To simplify the problem I wrote the following code which produce the same curious behavior. Important is the method run() and given double value rate. For my runtime test (in the main method) I set the rate to 0.5 one times and 1.0 the other time. With the value 1.0 the if-statement will be executed in each loop iteration and with the value 0.5 the if-statement will be executed half as much. For this reason I expected longer runtime by the first case but opposite is true. Can anybody explain me this phenomenon??

The result of main:

Test mit rate = 0.5
Length: 50000000, IF executions: 25000856
Execution time was 4329 ms.
Length: 50000000, IF executions: 24999141
Execution time was 4307 ms.
Length: 50000000, IF executions: 25001582
Execution time was 4223 ms.
Length: 50000000, IF executions: 25000694
Execution time was 4328 ms.
Length: 50000000, IF executions: 25004766
Execution time was 4346 ms.
=================================
Test mit rate = 1.0
Length: 50000000, IF executions: 50000000
Execution time was 3482 ms.
Length: 50000000, IF executions: 50000000
Execution time was 3572 ms.
Length: 50000000, IF executions: 50000000
Execution time was 3529 ms.
Length: 50000000, IF executions: 50000000
Execution time was 3479 ms.
Length: 50000000, IF executions: 50000000
Execution time was 3473 ms.

The Code

public ArrayList<Byte> list = new ArrayList<Byte>();
public final int LENGTH = 50000000;

public PerformanceTest(){
    byte[]arr = new byte[LENGTH];
    Random random = new Random();
    random.nextBytes(arr);
    for(byte b : arr)
        list.add(b);
}

public void run(double rate){

    byte b = 0;
    int count = 0;

    for (int i = 0; i < LENGTH; i++) {

        if(getRate(rate)){
            list.set(i, b);
            count++;
        }
    }
    System.out.println("Length: " + LENGTH + ", IF executions: " + count);
}

public boolean getRate(double rate){
    return Math.random() < rate;
}

public static void main(String[] args) throws InterruptedException {
    PerformanceTest test = new PerformanceTest();

    long start, end;
    System.out.println("Test mit rate = 0.5");
    for (int i = 0; i < 5; i++) {
        start=System.currentTimeMillis();
        test.run(0.5);
        end = System.currentTimeMillis();
        System.out.println("Execution time was "+(end-start)+" ms.");

        Thread.sleep(500);
    }       
    System.out.println("=================================");
    System.out.println("Test mit rate = 1.0");      
    for (int i = 0; i < 5; i++) {
        start=System.currentTimeMillis();
        test.run(1.0);
        end = System.currentTimeMillis();
        System.out.println("Execution time was "+(end-start)+" ms.");
        Thread.sleep(500);
    }   
}

Answer 1

Very similar to Why is processing a sorted array faster than an unsorted array? And there are the same reasons behind the scenes.

Answer 2

Branch misprediction kills the performance in the first case. Although second case does some work it is somewhat straight-forward, so processor can easily predict the next step. Please see this Wikipedia page for more information.

Try testing with 0.7. If I'm correct then performance will be somewhere in between 0.5 and 1.0.

Answer 3

To confirm that you are seeing the effects of a branch misprediction as indicated in my comment, I have run some tests. Table shows the rate (input to your run method), number of if executed and time to run.

0.0   0             1162
0.1   5,000,892     1204.25
0.2   10,002,410    1236.8
0.3   14,998,226    1264
0.4   19,996,983    1278
0.5   24,998,455    1305.5
0.6   29,998,879    1263.25
0.7   34,999,821    1232.25
0.8   39,999,414    1203.5
0.9   44,998,674    1202
1.0   50,000,000    1176.75

The closer you get to 0.5, the more branch mis-predictions you get (roughly one every run). The closer you get to 0 or 1, the more accurate branch predictions you get (no mispredictions when rate is either 0 or 1).

And because a picture is worth a thousand words: