Author: Robert Hyatt
Date: 11:11:06 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? The problem is that this varies based on the particular processor. IE the PIV has a very long pipeline, which means a branch mispredict is going to be expensive when the pipeline gets dumped and re-started. How much extra work you can do to eliminate a branch is a lot of science and a little witchcrafty. If you end up stuffing enough extra crap into the pipeline so that your code actually takes longer overall than it does with the branch mispredict, then you lose. If your branches are pretty "stable" IE you take or don't take most of the time, consistently, then the mispredict is not as frequent. If your branches have patterns, ie taken taken, not taken, and then this repeats, the PIV will get 'em all right after a pass through to learn the pattern. > >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? Very possibly... > >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
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.