Performance impact of short-circuit evaluation

Question

Disclaimer: I don't have much experience with reverse-engineering byte-code, so please don't be too harsh on me if that could "easily" answer my question.

On modern processors, branching can be extremely expensive if prediction fails (see Why is it faster to process a sorted array than an unsorted array?).

Let's say I have some short-circuit evaluation in Java like this:

if (condition && (list!=null) && (list.size()>0)) /* Do something */ ;

Is that basically equivalent to a bunch of branches like this:

if (condition) {
    if (list!=null) {
        if (list.size()>0) {
            // Do something
        }
    }
}

or does Java have some other way to do the short-circuiting more cleverly?

In other words, would it be better to avoid at least one branching by rewriting the line like this:

if ((condition & (list!=null)) && (list.size()>0)) /* Do something */ ;

since the simple list!=null-check is much less expensive than a potentially ill-predicted branching?

(Clearly I can't get rid of the second && without risking a NullPointerException.)

Now, before I get ripped to shreds with statements like "premature optimization is the root of all evil!", please keep in mind that this is a choice between general coding habits (always use short-circuiting vs. never use short-circuiting unless required), that will affect pretty much all of my code, so making sure that I use the right habit here is definitely worth spending some thought on.

Answer 1

I made a simple test

int sum = 0;
Random rnd = new Random(1);

int[] a = new int[1000];
int[] b = new int[1000];
for (int i = 0; i < 1000; ++i)
{
    a[i] = rnd.nextInt(100);
    b[i] = rnd.nextInt(100);
}

long started = System.nanoTime();

for (int i = 0; i < 1000000; ++i)
{
    for (int j = 0; j < 1000; ++j)
    {
        if (a[j] < 50 && b[j] < 5)// change "&& b[j] < 5"
        {
            sum++;
        }
    }
}

long ended =  System.nanoTime();
System.out.println((ended - started)/1000000 + "  " + sum);

The results are quite random:

            &&      &
b[j] < 5    1450    1360
b[j] < 50   1330    1610
b[j] < 500  1310    1450
j < 50      2200    920
j < 500     1410    1730
j < 5000    1180    1040
j < i       1180    2050
i < j       2290    1450

Those are lowest values from more runs and I made sure they were repeatable. The actual times vary from run to run. As a rule of thumb, I would avoid being too fancy, stick to the && and hope for optimizations "down there" do the best. There is nice video about optimizations

EDIT

As Dici pointed out, JVM warm up should be done. It seems first and second call of the function is different from the rest. The rule apply consistently even I when increased loop count. So I retested that and... got another mess. About 2x faster on average, but mess again. And the optimizations vere more unstable, there were often not one, but two typical time values even 50% different one from another. I looked at JMH, nice framework. I could probably measure if & is faster than && if I really tried (on different systems, different hardware and so on, a lot of work). But it is not the question. The question is, if I replace && for & in my program can I expect it to be faster or slower? And the answer is - You can not expect anything, You have to measure it.

EDIT2

I see it as a waste of time in this case, but to uphold my credibility I measured standard deviations (aka one sigma). Values behaved well enough in few runs and they behave well in thousand of runs, no surprise here (I did not show result after JVM warm up as they did not behave well and statistics would be inevitable). Funny thing is that all results are about 7% faster than those I measured previsously, which is beyond five sigma for most values. From few tries it seems that web browser tabs affect the whole system speed, by no, I am not going to make statistics to confirm my observation.

            &&          &
b[j] < 5    1333(14)    1265(25)
b[j] < 50   1231(11)    1514(13)
b[j] < 500  1223(9)     1360(13)
j < 50      2069(74)    842(11)
j < 500     1294(12)    1631(17)
j < 5000    1089(9)     957(8)
j < i       1086(8)     1907(23)
i < j       2164(16)    1357(14)

Answer 2

Nothing here mentions any kind of branching. This is a mere expression evaluation, a && in an if statement is no different from a && in an expression. Would you ask the same question with the following code ?

boolean isValid = condition && (list!=null) && (list.size()>0);
if (isValid) {
    ...
}

This is basically what happens, the expression gets evaluated and then the branching happens.