Author: Gerd Isenberg
Date: 01:57:50 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
Hi Russell,
as Eugene already mentioned, an indirect call costs *at least* the same as
conditional branch, because no anticipatory instruction prefetching/decoding is
possible.
I use this technique, calling indirect via (member) function pointer arrays as a
replacement of a switch statement, which is the main structure of one routine.
But may this approach is a bit anachronistical and one should trust the
compilers and use standard switch statement.
Another way to avoid branches is the use of conditional move, cmovxx, at least
in assembler, eg. for inlined or intrinsic functions like max(a,b).
Often one can use the c-property, that a boolean expression with true or false
results may be interpreted as arithmetic integer values 1 (true) or 0 (false).
Therefore it is often possible to replace some conditional assignments or simple
if[else] statements by some cheap test,cmp,setcc,shift,add or lea instructions:
c = a > b ? 32 : 16;
c = 16 + 16*(a>b);
// color [0,1] ==> white,black
delta = color == WHITE ? 8 : -8;
delta = pawnDelta[color]; // no conditional jumps but memory access
delta = 8 - 16*color; // should procuce the fastest code
See also amd's Optimization Guide, Chapter 6, Branch Optimizations:
http://www.amd.com/us-en/Processors/DevelopWithAMD/0,,30_2252_739_2983,00.html
http://www.amd.com/us-n/assets/content_type/white_papers_and_tech_docs/22007.pdf
Cheers,
Gerd
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.