Portable branch prediction hints

Question

Is there any portable way of doing branch prediction hints? Consider the following example:

  if (unlikely_condition) {     /* ..A.. */   } else {     /* ..B.. */   } 

Is this any different than doing:

  if (!unlikely_condition) {     /* ..B.. */   } else {     /* ..A.. */   } 

Or is the only way to use compiler specific hints? (e.g. __builtin_expect on GCC)

Will compilers treat the if conditions any differently based on the ordering of the conditions?

Answer 1

The canonical way to do static branch prediction is that if is predicted not-branched (i.e. every if clause is executed, not else), and loops and backward-gotos are taken. So, don't put the common case in else if you expect static prediction to be significant. Getting around an untaken loop isn't as easy; I've never tried but I suppose putting it an an else clause should work pretty portably.

Many compilers support some form of #pragma unroll, but it will still be necessary to guard it with some kind of #if to protect other compilers.

Branch prediction hints can theoretically express a complete description of how to transform a program's flow-control graph and arrange the basic blocks in executable memory… so there are a variety of things to express, and most won't be very portable.

As GNU recommends in the documentation for __builtin_expect, profile-guided optimization is superior to hints, and with less effort.

Answer 2

In most cases, the following code

if (a) {    ... } else {     ... } 

is actually

evaluate(A)  if (!A) {    jmp p1 }  ... code A     jmp p2  p1:  ... code !A  p2: 

Note that if A is true, "code A" is already in the pipeline. The processor will see the "jmp p2" command ahead, and will load p2 code to the pipeline.

If A is false, the "code !A" may not be in the pipleline, therefore it may be slower.

Conclusions:

1. do If(X) if X is more likely than !X
2. try to evaluate A as early as possible, so that the CPU can dynmically optimize the pipeline.

:

evaluate(A)  do more stuff  if (A)    ...