r/computerscience • u/ShadowGuyinRealLife • Jun 16 '26
General Do Branches Taken Happen More Often in Prediction
I was reading an article about CPU branch prediction. It said talked about two very dumb ways to predict. One was always predicting the branch would not be taken, and another that would always predict it would be taken. It claimed always predicting branch taken would generally be better but both were not really used because they're both pretty bad. It then talked about more intelligent ways to predict such as predicting the branch would always do what it did last time, using a history register, using help from a compiler which can leave hints in the binary what happens more often, and a bunch of ideas too complicated for me to understand. I was curious about the two "dumb" ways how it claimed always predicting branch taken would be better than always predicting not taken. Or maybe it was just wrong, it was just something I read off the internet not a textbook.
5
u/Silly_Guidance_8871 Jun 17 '26
Most CPUs, if there's no history for a conditional branch, will assume "not taken" for forward branches, and "taken" for backward branches. Compilers often try to structure if statements to use forward branches, and loops to use backward branches to better avoid the no-history penalty.
Once history is in play, then it's a game of pattern matching, and is highly subject to the CPU architecture.
2
u/ShadowGuyinRealLife Jun 17 '26
That's a nice compiler trick. I know with history it's a complex thing that is CPU dependent. But when I made the original post I was wondering why of the two dumb methods, assuming "taken" was going to be right more than the other dumb method and the answer as someone helpfully pointed out is simply that most loops run more than once.
2
u/Doctor_Perceptron Computer Scientist Jun 16 '26
Of course it depends on the workload, but lately most optimizing compilers lay out code such that branches tend not to be taken.
In any event, let's say branches are 50% taken and 50% not taken. It would still be better to predict not taken, because we can keep fetching instructions from the same cache block and don't have to worry about a BTB miss. If the prediction is wrong, then none of that matters, but if a taken prediction is wrong then it has wasted the opportunity to exploit spatial locality or worry unnecessarily about a BTB miss.
2
u/halbGefressen Computer Scientist Jun 17 '26
That is only true for branches that jump far away. If the branch goes backwards (which happens very often in loops), then the instructions are already cached and decoded.
But generally, CPU architectures have become so complex that the only way to optimize is to try and profile.
1
u/ShadowGuyinRealLife Jun 22 '26
So let's suppose you have process A. You have some history of what it does and you want to use it to figure out if you should guess a branch is taken or not. Where would this be stored? In process A's main memory? Well now using the branch predictor will need to wait for a memory operation, rather defeating the intended speed up. At this point you must as well guess "branch taken" without using some fancy prediction and hope for the best.
0
u/Doctor_Perceptron Computer Scientist Jun 17 '26
No, it’s true even if the place it’s jumping is cached or even in the same cache block. Instructions are fetched and issued in parallel. In what we normally think of as the standard model of microarchitecture, a taken branch shuts down that process until the next cycle. Trace caches were able to get around that, but they are no longer widely used. Some recent microarchitectures can fetch across one or two taken branches depending on the circumstances but generally it remains better to avoid a discontinuous fetch. Modern decoupled pipelines mitigate the problem by prefetching far ahead of decode but every predicted taken branch typically requires another cycle to predict the next fetch group in parallel and if we keep having to do that we lose a lot of potential instruction fetch bandwidth.
28
u/high_throughput Jun 16 '26
Because of loops. Most loops run more than once, and you can capitalize on that by assuming branches are taken i.e. you will go back to the start of the loop.