Branch prediction: Does avoiding “else” branch for simple operations makes code faster (Java example)?

Question

Options 1:

  boolean isFirst = true;
  for (CardType cardType : cardTypes) {
    if (!isFirst) {
      descriptionBuilder.append(" or ");
    } else {
      isFirst = false;
    }
    //other code not relevant to this theoretical question
  }

Option 2:

boolean isFirst = true;
for (CardType cardType : cardTypes) {
  if (!isFirst) {
    descriptionBuilder.append(" or ");
  } 
  isFirst = false;
  //other code not relevant to this theoretical question
}

My analysis: Both code has same semantic.

1st code) I'm not sure if this code has two branches (in terms of branch predictor) or one branch. I was looking into http://en.wikipedia.org/wiki/X86_instruction_listings but couldn't figure out that there is a X86 instruction something like "if previous condition value was false jump there", to avoid two branch predictions (very bad)

2nd code) most likely to always perform simple MOV (to register or element most likely already in the cache), which is relatively inexpensive (few cycles at most)

So, my opinion is that unless processor decode into microcode instructions can do something smart or X86 instruction exist to avoid necessary branch predictions, 2nd code is faster.

I understand that this is purely theoretical question, since in practice, this branch can make an application 0.000000002% faster or something like that.

Did I miss something?

EDIT: I added a loop for giving more "weight" to branch in question

EDIT2: The question is about Intel architecture for branch prediction (Pentium and newer processors).

Answer 1

The code has the same effect but won't produce the same byte code or assembly (probably).

How much difference this makes in terms of performance, is unclear and likely to be trivial.

What is far, far more important is the clarity of the code. I have seen more bugs and performance issues due to code being harder to reason about in simple cases like this.

In short, what is clearest and simplest to you is also likely to be fast enough, or the easiest to fix.

Answer 2

Using JMH gives the following numbers with cardTypes array of size 10 and integer increment as the logic (Java 15 / AMD 3950X / Windows 10):

Benchmark          Mode  Cnt          Score         Error  Units
Benchmark.option1  thrpt   25  273369417.720 ± 1618952.179  ops/s
Benchmark.option2  thrpt   25  273415784.192 ±  852618.585  ops/s

Average performance of "Option 2" is about 0.017% faster (YMMV).

See also: branch prediction, method dispatch, memory access, throughput and latency, garbage collection.

Answer 3

Different hardware has different costs for each of the assembler instruction, and on modern hardware even the cost of an instruction is difficult to predict due to the effects of pipelining and caches.

The difference between an if and an if/else on pipelining and caches is not clear from your isolated example. If you ran that code once, it is unlikely that you will see any difference at all. Repeatedly run it in a tight loop, and the performance of the if itself will become dominated by a) the cost of the check and b) the predictability of the result of the check. In other words, branch prediction will become the dominating factor and that will not be affected by having an if or an if/else block of code.

An excellent discussion on the effects of branch prediction can be read here Why is it faster to process a sorted array than an unsorted array? (see the top scoring answer).

Answer 4

Assuming that your code snippet is an if block from within a for loop. Hotspot has the ability to unroll for loops, this includes taking the common 'is first iteration of a loop' check and inlining it outside of the loop. Thus avoiding the costs of rechecking the condition on every iteration of the loop. Thus avoiding the concern of which is faster, if or if/else.

Oracle documents this behavior here

Answer 5

Both code has same semantic.

No Both code are different,

first code app isFirst = false; set flag to false if your condition if (!isFirst) not match.

Second code each time change your flag to false even condition satisfied or not.

Answer 6

There are two branches in an if/else construct: the conditional branch at the top, and the branch around the else part at the end of the if part. There are no branches in the else part, at least not in any even moderately competently implemented compiler.

Against that you have to balance the cost of always executing the isFirst = false; line.

In the specific case you mention, it isn't likely to make the slightest difference, compared to the cost of the method call.