If you're like me, you need to stop thinking of it as "99% of call sites" and start thinking of it as "99% of iteration loops". I know it's super obvious on the face of it, but the implications is that most call sites can repeatedly fail but are totally overshadowed by insanely high frequency hot loops that it almost always predicts right (it's skewed, just like avg vs median)
This is the 1% of cases. As I understand it, most branches take the same path most of the time. Think of a loop for instance. With purely statistical prediction (go whichever direction the branch takes more often), loops will be predicted with extreme accuracy and the result is a huge number of correct branches. Then think about error handling code which isn't triggered most of the time due to input being valid. Between these two easy cases, I think you cover the majority of branches is programs which is why so many of them are predictable.
Only branches that capture exceptional events, e.g. error checks, show 99% hit rate.
Branches that are part of an algorithm are driven by the data you feed to them. For example in a classical binary search, the prediction is right only 50% of the time.
But there's an overall loop which branches backward to the same spot, regardless whether the iteration went left or right. At least that's predictable.
If we have an instruction that will conditionally load one of two pointers from memory, the left or right traversal can be made branch-free.
The only reason we need to switch between two code paths in the binary tree descent is that we have two different pieces of code for loading the left or right pointer to the different offsets used in the load instruction.
If we use a two element array for left and right, the indices [0] and [1] select between them. We make the comparison condition calculate a 0 or 1 result and use it as an index.
It may be true in some cases, but not in general. I think of it as an observation that for large swathes of code the branch is predictable. Eg, we usually don't go down the error checking codepath. Faced with flow control that depends on random data, such as "is this random number even", the branch predictor will have a hard time doing better than 50%.
Run a profiler on your code sometime and see how many branches it reports taking. You can easily get millions of branches per second, so 1% events happen hundreds of thousands of times.
