2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes the safeness aspect was one of the prime reasons I suspected could hold a compiler back from doing such optimizations on it own. Maybe there exist "skip evaluate" or "short circuit" if one of the multiplicands is exactly 0 and we can set it to zero with the logical expression. Maybe casting one of the operands logical value to a float or double will help the compiler help us do that. $\endgroup$ – mathreadler Apr 8 '16 at 17:48
  • $\begingroup$ A boolean value used as a number in an arithmetic expression will necessarily be promoted to the correct type. If you find yourself using optimizations like this frequently, it can be very helpful to learn to read LLVM IR or x86-64 assembly code to see what the compiler really does. Experiment will always tell you more than some guy on the internet :) $\endgroup$ – Daniel Shapero Apr 8 '16 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.