Code faster with unnecessary conditional?

Question

I have the following java function, to count common elements in two sorted arrays. Note the line with the question mark.

public static int overlap(int[] a, int[] b)
{
    int i = 0, j = 0;

    int res = 0;

    while(i < a.length && j < b.length)
    {
        if(a[i] > b[j])
            j ++;
        else if(a[i] < b[j])
            i ++;
        else if(a[i] == b[j])  // ?
        {
            res ++;
            i ++;
            j ++;
        }
    }

    return res;
}

Clearly, that last if-statement doesn't need to be there: at that point we know that the two values are equal. However, when I test the speed (I was checking whether the order of the checks made any difference), the method with the superfluous check is invariably faster than the one without (sometimes by a factor of two).

What is going on here? Some mysterious optimization? Am I overlooking something obvious? I'm using the stand compiler, version 1.8. I can't read bytecode, so I don't know what's going on under the hood.

Here is a full test class: https://gist.github.com/pbloem/1523283211454ec58ce9c5b45204eebd

Bytecode: https://gist.github.com/pbloem/ce4f6758f0bb1424c155c26e83ca88a1

Answer 1

Possibly JIT swapping order of "if"s to get best performance but cannot swap order of just "else"(without an "if") with another "if" at the beginning, so when you added "if" after "else", it tried it as a first check, and if array overlapping is like %90, then it could keep that last "if" at the first place.

    if(a[i] == b[j])  // say %70 probability after N iterations
    {                 // or less randomized branching
        res ++;
        i ++;
        j ++;
    }
    else if(a[i] > b[j]) // %20 probability, medium branching
        j ++;
    else if(a[i] < b[j]) // %10, totally random branching, not predictable
        i ++;

is possible when arrays ordering

a > b or b < a

are more randomized than arrays overlapping.

When there is if+if+else, JIT may not predict what you mean in that. By adding an equalty, you are elliminating many cases except the equation.

Could you please try with an ordered array and totally randomized array?

Or it is just helping cpu's branch predictor as @noahnu said in comments.