   branch prediction
  Could anyone explain to me how branch prediction works ?And what I can do as a programmer to avoid misspredictions ?Thanks for replysQuak   
  http://en.wikipedia.org/wiki/Branch_prediction   ;  If you worry about branch mispredictions, then use fewer if() and switch() statements that can't be proven by the compiler. You may be better off using a virtual dispatch (using a policy object) than an if(), for example.  if (blackAndWhite) { // bad if()    black_and_white_code();  }  else {    color_code();  }  policy = new appropriate_policy();  // avoid the if  policy->code();This, of course, only matters if the if() statements are within your inner loops.Note that a for() test will only mis-predict once (at the end) on modern CPUs, but an if() may mis-predict almost every time.;  As a programmer using a higher level language (IE: anything higher up then assembler), with a GOOD optimizing compiler, you typicaly will not have to worry about branch prediction at all.  Optimizing compilers handle all of this for you.Branch prediction is something done at the processor level, this is one of the "big things" that optimizing compilers do when you target a specific chip set.  What this then does is organize your application automaticaly, in such a way that branch prediction is most accurate for that particular chipset type (which coincidently could be different for another).The new profiling compilers can use some tricks to dynamicaly place functions so that each conditional is prefetched to the "most common" case.If you happen to be working in straight off assembler, you (most times) can get away with simply having putting less likely conditional jumps before the declaration of the conditional itself, and put the code that it is most likely to evaluate to afterword.  Its not as fast as a good optimized compiler would do you for though, and im not sure the other tricks you can do at that level (havent touched assembler in years, and only on x80 processors, where that worked spiffy.   ;Quote:Original post by hplus0603If you worry about branch mispredictions, then use fewer if() and switch() statements that can't be proven by the compiler. You may be better off using a virtual dispatch (using a policy object) than an if(), for example.  if (blackAndWhite) { // bad if()    black_and_white_code();  }  else {    color_code();  }  policy = new appropriate_policy();  // avoid the if  policy->code();Why is that better? In both cases, a branch/jump has to be executed. And in both cases, the branch predictor can guess where to jump to after the first iteration. Only difference I can see is you get rid of the comparison, which of course saves a bit of time, but doesn't affect the branch predictor.Quote:Note that a for() test will only mis-predict once (at the end) on modern CPUs, but an if() may mis-predict almost every time.Only if there's no pattern in when the if-branch is taken. Otherwise, it'll be about as good at if's (possibly missing the first iteration, and probably the last too, if at some point you stop taking the branch).But any half-decent branch predictor will be able to handle if's with no more than those two misses.[Edited by - Spoonbender on June 19, 2006 3:35:04 PM];Quote:Original post by PaulCesarAs a programmer using a higher level language (IE: anything higher up then assembler), with a GOOD optimizing compiler, you typicaly will not have to worry about branch prediction at all.  Optimizing compilers handle all of this for you.You typically won't have to worry about it, period. It's mainly a CPU feature. It's very limited how much the compiler can assist (although with profile-guided optimization it can perform a few tweaks)But generally speaking, the CPU will just guess what you want to do, and predict it damn well. And you need to have *a lot* of branches for this to make a difference.   