Author: Gerd Isenberg
Date: 00:07:04 11/22/05
Go up one level in this thread
On November 21, 2005 at 18:10:54, Dieter Buerssner wrote:
>On November 20, 2005 at 16:38:38, Gerd Isenberg wrote:
>
>> [...] Here some branchless substitution may pay off:
>>
>>fm = (depth < 0) ? fm1 : fm2;
>
>I guess, you mean this as a substitution for
> if (depth < 0)
> fm = fm1;
> else
> fm = fm2;
Yes.
>
>I am surprised, that compilers are not able to do this themselves. I
>
>>fm = fm2 + (depth < 0) * (fm1-fm2);
>
>fm? are globals or constants? Why the need for the subtraction at the end?
>Wouldn't a new constant be sufficient. I fear, I did not understand this. (I
>believe I understand the "(depth < 0) * ..." part.
Let say fm is a temporary integer, and fm1 and fm2 are constants,
eg. fm1 == 200 and fm2 == 300.
if (depth < 0)
fm = 200;
else
fm = 300;
A boolean expression value range is {false,true} or {0,1} if interpreted as
integer. So the branchless subtitute with boolean multiplication
fm = 300 + (depth < 0) * (200-300);
If the condition is true, we have 300 + 1 * (-100) == 200.
If the condition is false, we have 300 + 0 * (-100) == 300.
Next optimization step is to replace boolean mul by and with a {0,-1} mask:
fm = 300 + (depth>>31) & (200-300);
If depth is negative (depth < 0), depth>>31 becomes -1.
In assembly something like three cheap instructions, which might be competitive
even for a good predicted branch:
sar eax, 31
and eax, -100
add eax, 300
The branchless substitute for statements like
if (depth < -1)
fm = fm1;
else if (depth < 0)
fm = fm2;
else
fm = fm3;
has the advantage to compute the two masks in "parallel" with two registers and
to do the final add by lea.
>
>>How do you understand the indirect jmp works on amd64?
>>I still found the qoute from amd optimization manual contradictory:
>>"To avoid a comparison chain and its undesirable effects on branch prediction,
>>replace the switch statement with a series of if-else statements..."
>
>I don't understand it at all. Doesn't seem to make any sense.
Yes, only if the dense of the branches generates more than three jcc in a
16-byte fetch. May be it was meant in the following manner:
"To avoid an indirect jump and its undesirable effects on branch prediction,
replace the switch statement with a series of if-else statements..."
Gerd
>
>Cheers,
>Dieter
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.