Branchless code has the potential to run faster than the equivalent code that uses conditionals, or so I''ve heard. I was wondering about how people go about getting rid of conditional code, since it would seem to make a significant difference in some cases (such as frequently used code). One idea that came to mind is to use an array of function pointers instead of a conditional. For example, instead of something like (in my chess program): if (side_to_move == WHITE) { // do white stuff here } else { // do black stuff here } You could do something like: // Forgive me if my syntax for using function pointers is wrong typedef ... Function; Function do_stuff[] = { DoWhiteStuff, DoBlackStuff }; do_stuff[side_to_move](); That would eliminate the potential branch misprediction penalty, and only cost a call and ret instruction. So as long as the call+ret instructions don''t cost more than 10-20 cycles that you would suffer for a branch misprediction, you win here. In thinking about this, it sounded similar to the OOP refactoring technique known as "replace conditional with polymorphism". Is that essentially what is happening when I replace a conditional with a lookup table of function pointers? Anyway, I was wondering if someone more knowledgable than myself about these things could shed some light on which method would be more efficient, and about the real worth of branchless code. Is it worth a great amount of extra work to achieve branchless code? Or is it only going to provide minimal speedups? Thanks, Russell

Only optimize places where you need increased efficiency. The example the original poster gave works in theory, aside from a few syntax issues. The trade-off is a taking a possible branch-prediction failure and turning it into an indirect jump. Determing whether or not it''s worth it is the difficlt part, but it works something like this.

x -- the time the original code took to execute
y -- the time addition incurred by a branch-prediction failure
z -- the time of an indirect jump
A -- the percent of the time you expect a branch-prediction failure to occur

So if x+y*A >= z, then you can argue that in most cases the function-pointer method is more efficient. You wouldn''t want to apply this method to anything but some portion of code that is executed repeatedly though, as the average case argument falls apart. You would never want to do this on code that will be executed only a few times or simply not very often. The other drawback to this is that since C and C++ do not support heterogenous arrays, the function signature is limited to one case. This may or may not pose a problem for your design.

quote:
the time the original code took to execute

By this I meant the time it takes for a regular if-statement to be executed, which is just a direct jump or executed the next instruction of code, not the code contained in the if-statement itself. Anyway, it depends mostly on the percentage of time that you expect a branch-predition failure to occur.

Calls/ret *also* need to be predicted, just like branches. If the CPU can''t predict a call, because the call will depend on the value of a register (or variable), then it ends up being as expensive (if not more) than a mispredicted branch.

The same applies to the ret too, so don''t think about messing up stack values to go around this.

Unless the code inside if (color == WHITE) {} else {} is dead simple, don''t think for a second that it will run faster without the branch. It most likely won''t. Your best bet is to move the conditionals outside of the inner loop (assuming your code is inside an inner loop). If that code isn''t inside an inner loop, then you are most likely trying to optimize the wrong code.

As always, profile before you decide to optimize. Think before you code

two refactorings

replace conditional with polymorphism

replace conditional with visitor see more information

[edited by - petewood on November 19, 2002 3:22:21 AM]

Like the lowermost AP said, compiler can''t predict the jump until it has fetched the address from a register.. This efficiently halts the pipeline and is much harder to predict than a normal conditional branch which can only go to two fixed addresses.

No; branchless code really means you don't jump - at all!

You'll probably need to do this kind of thing at assembly level (to derive any befit from it, anyhow). It's fairly common in MMX code for example. The basic principle is that you have multiple answers to a formula (say, you wish to get the absolute value of an integer, where you would have the original number and it's negative). You'd then generate a mask that when anded would eliminate the incorrect answer(s).




Of course, as I'm sure someone will point out this could be done faster by doing using the P6 instruction CMOVcc - but this is just to illustrate the idea! as you can see this has no jumps or calls in it - my guess is that this should execute in about 6 cycles or so.




Hope that gives you an idea of what it's about

[EDIT: I'll try to actually put the correct code in this time!]

[edited by - NickB on November 19, 2002 5:25:57 AM]