Realistic examples of optimization by removing branches

Question

According to Intel , branch removal is one of the most efficient ways to optimize C code for use in narrow loops. However, the examples on the linked page only cover the cycle of expanding and moving invariant branches outside the loops.

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

Answer 1

If branch elimination is your goal, you might consider math or some intolerable solutions.

Consider the following example:

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

It can be rewritten 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 solution to work, it is assumed that your processor can evaluate a <b without generating a jump instruction. It also kills readability.

Is it worth it? Sometimes, but usually not. If the wrong prediction of branching or branching cost you dearly because it is not biased towards one branch or another, maybe . But probably not. As always, profile.

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

Hope this helps.

Answer 2

This tutorial contains some more examples. Besides what's here, I can think of using switch statements or sentinel values . I also found this other tutorial from more obscure ways to avoid utterances.

If you are working on optimization, I highly recommend using a profiling tool like callgrind / kcachegrind and focus on the parts of the code where you spend the most time. Optimizing the code in certain ways can confuse it or make it otherwise more difficult to maintain, and in my experience optimizing for optimization is a really bad idea.

After using the profiler, you may find that for your code using a better data structure or avoiding a certain algorithm, it may be the most efficient way to optimize your C code rather than deleting a branch.

I don’t want to receive a sermon, I just don’t agree with the premise that removing branches is the best way to optimize the code. I understand that this is very convenient for modern processors, but the first step towards optimizing efforts should be to find the slow parts of the code, and then move from there.

Answer 3

Optimal block ordering can make very little difference and is found in every piece of code. And I would not simply reject the examples given by Intel as "unrealistic."