Author: Ricardo Gibert
Date: 12:08:18 02/26/03
Go up one level in this thread
On February 26, 2003 at 14:04:16, Uri Blass wrote:
>I had the following code in my program
>
>do
>{
>...
>if (info[target]==EMPTA)
> target+=8;
>else
> target=64;
>}
>while (target<64)
>
>I found that changing it to else break did not do my program faster.
>
>I think that with break I have branches and without break the compiler can
>translate it to
>
>target=((info[target]==EMPTA)?target+8:64);
>
>My questions are
>1)How can I write the code as branchless code without target=64 that is a waste
>of time?
The usual way to eliminate one of the tests is with sentinels. However, this may
or may not be compatible with the rest of your program.
http://www.webreference.com/programming/optimize/speedup/chap10/3/
>
>2)I understood from previous discussion that for some reason ? is considered
>branchless code.
>What is the reason for it.
If you thought about it carefully, you would realize this can't possibly be
true. For one thing, if you read the specification for the C language, this is
not promised. Consider the following:
p = some_boolean_expression ? some_complex_expression_without_side_effects :
some_other_complex_ expression_without_side_effects;
One way to evade a branch is as follows:
t[0] = some_complex_expression_without_side_effects;
t[1] = some_other_complex_ expression_without_side_effects;
p = t[some_boolean_expression];
but this solution computes *both* complex_expressions which may take much longer
than computing only *one* with a branch. The situation gets even worse if the
complex expressions have side effects. This problem can be avoided with a jump
table solution, but I would not expect this to be an improvement.
What you may be thinking about is some simple expression like:
p = (a < b) ? x : y;
This has a branchless interpretation as in above or as:
p = ((((a-b) >> (WORDBITS-1)) & (x^y)) ^ y).
This assumes that (a - b) is signed and the shift is signed (which C does not
promise).
Other expressions can have an even simpler solution, but it depends on the
underlying architecture. There can be no portable guarantee that the branch is
always avoidable or that it is efficient to do so.
>
>It seems to me that using ? is the same as using if.
>If it is not the case then what is the difference?
>
>Uri
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.