Author: Tony Werten
Date: 23:37:31 02/27/03
Go up one level in this thread
On February 26, 2003 at 15:10:58, Russell Reagan wrote:
>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);
>
>Whether or not you use 'target=64' or 'break', it doesn't matter.
>
>
>>My questions are
>>1)How can I write the code as branchless code without target=64 that is a waste
>>of time?
>
>Having one extra 'target=64' in your program isn't going to make any difference
>at all. It is one instruction in many millions.
>
>
>>2)I understood from previous discussion that for some reason ? is considered
>>branchless code.
>>What is the reason for it.
>
>I think the ? operator is just a shorthand for 'if-then-else', so it should be a
>branch.
Doesn't have to be.
Consider x = (a<b) ? a : b;
translated (for clearancy) to:
x = b
if (a<b) x = a
In assembly this translates (with a good/new compiler) to:
move x,b
compare a,b
conditional move x,a
This last instruction (cmov) is the big win since it is branchless.
Tony
>
>It looks like you're looping over the board, and I don't think there's a way to
>do that without branches, unless you want to do some bitboard stuff. Then you
>have fewer branches, but you have more instructions (at least on a 32-bit
>machine). Fewer branches is only one means to an end, not the end.
>
>One thing you might try is to create a function (like a mathematical function)
>to replace a conditional. I use this method in my bitboard program. If I want to
>generate pawn attacks, I could do this:
>
>typedef unsigned __int64 Bitboard;
>
>#define NotFileA ((Bitboard)0xfefefefefefefefe)
>#define NotFileH ((Bitboard)0x7f7f7f7f7f7f7f7f)
>
>#define ShiftUpRight(b) (((b) << 9) & NotFileA)
>#define ShiftUpLeft(b) (((b) << 7) & NotFileH)
>#define ShiftDownRight(b) (((b) >> 7) & NotFileA)
>#define ShiftDownLeft(b) (((b) >> 9) & NotFileH)
>
>#define WHITE 0
>#define BLACK 1
>
>if (side_to_move == WHITE)
> pawn_attacks = ShiftUpLeft(white_pawns) | ShiftUpRight(white_pawns);
>else
> pawn_attacks = ShiftDownLeft(black_pawns) | ShiftDownRight(black_pawns);
>
>And then I would have pawn attacks for the side to move, and I could use them
>for move generation, or whatever. But, as you will notice, there is an ugly
>branch. So in my program I did this:
>
>pawn_attacks = (ShiftUpLeft(friendly_pawns) | ShiftUpRight(friendly_pawns)) >>
>(side_to_move * 16);
>
>And we have no branches. If the side to move is white, then 'side_to_move' is
>zero, so the pawn attacks get shifted by a value of zero. If black is to move,
>then side_to_move is 1, and so the attacks get shifted by 16. If it's not clear
>what I'm doing, I'll explain more.
>
>Russell
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.