Author: Gerd Isenberg
Date: 05:55:41 04/20/03
Go up one level in this thread
On April 20, 2003 at 07:36:01, Albert Bertilsson wrote: >Hi! > >When the topic is already discussed, I have a question about branches... > >The previous posted answer makes me belive that branching is a bad thing and >should be avoided if possible, I guess that has something to do with branch >prediction and stuff. > >The question is, how much extra code is it worth to get rid of a branch? Is >there any rule of thumb? > >For example the following code: > >if (dir1 == 1 || dir1 == -1 || dir1 == 16 || dir1 == -16) > >004025BB cmp edi,1 >004025BE je Board::UpdateCheckers+74h (4025D4h) >004025C0 cmp edi,0FFFFFFFFh >004025C3 je Board::UpdateCheckers+74h (4025D4h) >004025C5 cmp edi,10h >004025C8 je Board::UpdateCheckers+74h (4025D4h) >004025CA cmp edi,0FFFFFFF0h >004025CD je Board::UpdateCheckers+74h (4025D4h) > >Four branches, not a surprise... > >But it can be changed into: > >if (((dir1 == 1) | (dir1 == -1) | (dir1 == 16) | (dir1 == -16))) > >004025D2 xor eax,eax >004025D4 cmp esi,10h >004025D7 sete al >004025DA xor edx,edx >004025DC cmp esi,0FFFFFFF0h >004025DF sete dl >004025E2 or eax,edx >004025E4 xor edx,edx >004025E6 cmp esi,1 >004025E9 sete dl >004025EC or eax,edx >004025EE xor edx,edx >004025F0 cmp esi,0FFFFFFFFh >004025F3 sete dl >004025F6 or eax,edx > >This code is obviously longer, but it has no branches, so is it better? > >The assembler code was generated by VC++ 7.0, which seems to be good when >compared to other compilers. My own assembler knowledge is very basic. > >/Regards Albert Hi Albert, at least one final branch you need here too, instead of the four. It depends on the probability of correct branch predictions. To minimize branch mispredictions, which are rather expensive, it is good to have the register ready some instructions before the compare instructions occurs. I often use bitwise or arithmetic operators instead of boolean to combine boolean expressions with "random" probability until a final compare and found it superiour. But one has to try it from case to case. In your case with symmetric positive and negative values, you may even try an branchless abs-function before. Another way is to use a preinitialized boolean array indexed by the direction + some offset to make all indizies positive - or an switch statement with the same intention - a jump table. Regards, 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.