Branch avoidance for performance with modern compilers?

Question

Hello I hope I'm asking this in the right community, please feel free to redirect me some better place if you don't think it fits here.

As I learned when I went to university half an eternity ago, modern CPUs typically have large pipelines for instructions to gain performance by being able to do many simple things in parallell.

 // A typical code block inside a loop that I fear would clog up a pipeline.
 if(l1)     a = ...;
 elseif(l2) a = ...;
 ...
 else        a = ...;

 // A different way to write it as a sum that would avoid
 //  branching but at a possible cost of more instructions (?)
 a = (!!l1)*... + (!!l2)*... + ()*...;

Would modern compilers know how to (and allow themselves to) avoid branching in the first case or should I as an implementer put effort into helping the compiler by planning and rewriting my code as logical arithmetic expressions?

My goal is optimization for speed for number-crunching applications.

Answer 1

Yes, modern compilers use branch avoidance if possible. For example, they would pull common subexpressions in the assignments to the variable a out of the if/else branches; they would then see if perhaps what remains in the computation of the assignments is simple enough to have a formulaic expression that allows computation without branching, or through a conditional assignment that depends on a condition flag rather than an executed branch instruction. If expressions are simple enough, the compiler could also employ techniques such as the one you suggest, but that's clearly only a win if what you multiply with is cheap enough to compute for all possible branches.

But like all optimizations, what compilers can do is, in reality, rather limited. It often frees you from purposefully obscuring code using micro-optimizations, but it does not free you from thinking about the bigger picture.

Answer 2

To add to Wolfgang's answer, there are many expressions which look like they could be optimized by a Sufficiently Smart Compiler, but for which a general use of this optimization would be unsafe. As you have pointed out, rewriting a conditional to use boolean arithmetic involves computing every possible branch, then computing a kind of weighted sum; this does more computing but won't slow you down due to branching. As a silly example, this code:

if (x > 0)
    return x;
return -x;

can be trivially transformed into

bool b = (x > 0);
return b * x + (!b) * (-x);

But what about this:

if (fabs(x) > eps)
    return sin(x) / x;
return 1.0;

The branch is there to avoid dividing by zero, so you would not want the compiler to perform the same optimization here. Pretty much any operation can, in principle, trigger a floating-point exception; adding or multiplying two doubles can overflow. So a reasonable optimizing compiler might choose not to eliminate a branch, even if you as the programmer know that the expression inside is innocuous. You would then have to optimize it yourself.

Finally, while using boolean arithmetic to get rid of conditionals can be a useful trick, it makes your code much less readable and the intent should be in comments or documented somewhere.