Realistic examples of optimization through branch removal

Question

According to Intel, branch removal is one of the most effective ways of optimizing C code for use in tight loops. However, the examples in the linked page only cover loop unrolling and moving invariant branches outside of loops.

Are there additional and varied (before & after) examples of branch removal for optimization?

Answer 1

If eliminating branches is your goal, then you may wish to consider math, or some non-portable solutions.

Consider the following example:

if (a < b)
    y = C;
else
    y = D;

This can be re-written as ...

x = -(a < b);   /* x = -1 if a < b, x = 0 if a >= b */
x &= (C - D);   /* x = C - D if a < b, x = 0 if a >= b */
x += D;         /* x = C if a < b, x = D if a >= b */

For the above to work, it assumes that your processor can evaluate a < b without generating a branch instruction. It also kills readability.

Is it worth it? Sometimes, but usually not. If the branching or branch mis-prediction is costing you a lot because it is not biased towards one branch or the other it might be worth it. But probably not. As always, profile.

A little bit of math/arithmetic can go a long way in eliminating branches if that is your goal. Although it has been said a myriad of times before, just because you can do something, does not mean that you should.

Hope this helps.

Answer 2

This is tutorial has some more examples. Other than what is here, I can think of using switch statements or sentinel values. I also found this other tutorial of more obscure ways to avoid if statements.

If you are working on optimization, I would strongly recommend using a profiling tool such as callgrind/kcachegrind and focusing on the parts of the code where you spend the most time. Optimizing code in certain ways can obfuscate it or make it otherwise more difficult to maintain, and in my experience optimizing for optimization's sake is a really bad idea.

After using a profiler, you may discover that for your code using a better data structure or avoiding a certain algorithm may be the most effective way to optimize your C code, and not branch removal.

I don't mean to get preachy, I just disagree with the premise that removing branches is the best way to optimize code. I understand that this helps modern processors tremendously, but the first step to any optimization effort should be to find the slow parts of the code and then go from there.