Skip to main content
GameDev.net gamedev.net
🔒 Locked

which if is better according to prediction of pipeline

Started by ccanan Dec 5, 2006 at 8:53 PM 4 replies 1.2k views
Original Post
ccanan
ccanan
for(int i=0;i<1000000000000;i++) if(i<90) kick A; else kick B; as you see, [kick B]happens most of the time; so if the branch prediction fall in predict taken, this kind of if-else is not effective; and on my pc: (intel p4,winxp), the form: if(i>90) Kick B; else Kick A; run %2 faster; so my question is: 1, does my test of if-else really tell me that I should put the thing that happens more often under the taken zone; can how the compiler and architecture work at this point be test simply in this way? 2, on pc(intel,AMD),xbox,ps3, what's the situation; thanks for advance!
blarn
blarn
this probably isn't the response that you wanted, but in my opinion, if your code has bottlenecks it's highly unlikely that it is because of branch prediction. More likely is that it's the result of some design choice or bug, so I don't think this is something that you should really worry about when writing code.
iMalc
iMalc
A faster option is of course this:
(Note: I assume that 'kick' is either a Macro or is psuedocode)
for(int i=0; i<90; i++)    kick A;for(int i=90; i<1000000000000; i++)    kick B;
That better be compiled with int as a 64-bit data type!

Your second example is different because for i=90 you 'Kick A' instead. You would need to use >= to make it the same.

In general the most likely case should come first. This works better on other processors such as the PowerPC in which I believe they assume that most of the time, conditional backwards branches are taken and conditional forward branches are not taken. However, "profile guided optimisation" (as in VS2005) can probably make this particular optimisation for you, if appropriate.
Spoonbender
Spoonbender
The fastest solution is to execute the smallest amount of code (and the smallest amount of branches. With iMalc, you save 1000000000000 branches, so yes, I'd say that's the most efficient.

Otherwise, it won't make any different in practical terms. As iMalc said, there are conventions for how a branch is handled "by default". But after a couple of iterations, it'll have adapted, so overall, it won't get a mispredict more than a couple of times in your code.
Skizz
Skizz
A 2% difference is not enough to determine which is quicker - don't forgat that the OS is doing task switching whilst the program is running and you could experiance a much bigger variation in timings than 2%. Doing profiling is not easy. In your case, I would say that
for(int i=0;i<1000000000000;i++)  if(i<90)    kick A;  else    kick B;

is going to be the quicker way to order the code (by only a few cycles). On most Pentium processors (from II onwards) there are two types of branch prediction: static and dynamic. There is also a thing called the Branch Target Buffer (BTB) which is used for dynamic branch prediction. The method for prediction is:
if target address not in BTB  // use static prediction  create entry in BTB  if forward jump     don't take branch  else    take branchelse  // use dynamic prediction  if history of branches in BTB indicate a branch taken    take branch  else    don't take branch

So, in your code, the first time the 'if' branch is encountered the branch is not taken (which is correct in the original form). Subsequent branches will then depend on previous branches so you'll get a dip in speed around the i==90 point as the BTB sorts itself out, after which the BTB will correctly predict the branch (always taken). Swapping the if-else around only changes the initial static prediction which would be an incorrect predication, thus a few cycles slower. The transition would be the same hit regardless of the order.

Skizz
ccanan
ccanan
thank you guys!
so happy to learn this!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.