Author: Anthony Cozzie
Date: 14:47:43 11/19/02
Go up one level in this thread
On November 18, 2002 at 20:04:23, Russell Reagan wrote:
>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 in move generation or evaluation).
>
>One idea that came to mind is to use an array of function pointers instead of a
>conditional. For example, instead of something like:
>
>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
>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
A note here:
The problem is really with *unpredictable* branches. For example, if I have
if(error_code)
{
blah
}
this is not too bad: the error happens once every thousand times through the if,
the processor predicts not taken, and boom.
The problem is when you have branches depending on random user input stuff,
because the processor can't make a good guess. Also note that sometimes it may
be cheaper to simply do both, and (as Gerd said) use CMOV.
anthony
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.