Hmm, that's interesting. The code as written only has one branch, the if statement (well, two, the while loop exit clause as well). My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times.
But that's clearly not right, because apparently the specific data it's branching off matters too? Like, "test memory location X, and branch at location Y", and it remembers both the specific memory location and which specific branch branches off of it? That's really impressive, I didn't think branch predictors worked like that.
Or does it learn the exact pattern? "After the pattern ...0101101011000 (each 0/1 representing the branch not taken/taken), it's probably 1 next time"?
Your mental model is close. Predictors generally work by having some sort of table of predictions and indexing into that table (usually using some sort of hashing) to obtain the predictions.
The simplest thing to do is use the address of the branch instruction as the index into the table. That way, each branch instruction maps onto a (not necessarily unique) entry in the table. Those entries will usually be a two-bit saturating counter that predicts either taken, not taken, or unknown.
But you can add additional information to the key. For example, a gselect predictor maintains a shift register with the outcome of the last M branches. Then it combines that shift register along with the address of the branch instruction to index into the table: https://people.cs.pitt.edu/~childers/CS2410/slides/lect-bran... (page 9). That means that the same branch instruction will map to multiple entries of the table, depending on the pattern of branches in the shift register. So you can get different predictions for the same branch depending on what else has happened.
That, for example, let’s you predict small-iteration loops. Say you have a loop inside a loop, where the inner loop iterates 4 times. So you’ll have a taken branch (back to the loop header) three times but then a not-taken branch on the fourth. If you track that in the branch history shift register, you might get something like this (with 1s being taken branches):
11101110
If you use this to index into a large enough branch table, the table entries corresponding to the shift register ending in “0111” will have a prediction that the branch will be not taken (i.e. the next outcome will be a 0) while the table entries corresponding to the shift register ending in say “1110” will have a prediction that the next branch will be taken.
So the basic principle of having a big table of branch predictions can be extended in many ways by using various information to index into the table.
Check out [1]: it has the most thorough description of branch prediction I've ever seen (chapter 3), across a lot of historical and current CPUs. It is mostly empirical, so you do have to take it with a grain of salt sometimes (the author acknowledges this).
Supposedly the branch prediction on modern AMD CPUs is far more sophisticated, based on [2] (a citation pulled from [1]).
There are many branch prediction algorithms out there. They range from fun architecture papers that try to use machine learning to static predictors that don’t even adapt to the prior outcomes at all.
Typical branch predictors can both learns patterns (even very long patterns) and use branch history (the probability of a branch being taken depends on the path taken to reach that branch). They don't normally look at data other than branch addresses (and targets for indirect branches).
I guess the generate_random_value function uses the same seed every time, so the expectation is that the branch predictor should be able to memorize it with perfect accuracy.
But the memorization capacity of the branch predictor must be a trade-off, right? I guess this generate_random_value function is impossible to predict using heuristics, so I guess the question is how often we encounter 30k long branch patterns like that.
Which isn’t to say I have evidence to the contrary. I just have no idea how useful this capacity actually is, haha.
30k long patterns are likely rare. However in the real world there is a lot of code with 30k different branches that we use several times and so the same ability memorize/predict 30k branches is useful even though this particular example isn't realistic it still looks good.
Of course we can't generalize this to Intel bad. This pattern seems unrealistic (at least at a glance - but real experts should have real data/statistics on what real code does not just my semi-educated guess), and so perhaps Intel has better prediction algorithms for the real world that miss this example. Not being an expert in the branches real world code takes I can't comment.
Yeah, I’m also not an expert in this. Just had enough architecture classes to know that all three companies are using cleverer branch predictors than I could come up with, haha.
Another possibility is that the memorization capacity of the branch predictors is a bottleneck, but a bottleneck that they aren’t often hitting. As the design is enhanced, that bottleneck might show up. AMD might just have most recently widened that bottleneck.
Super hand-wavey, but to your point about data, without data we can really only hand-wave anyway.
AMD CPUs have been killing it lately, but this benchmark feels quite artificial.
It's a tiny, trivial example with 1 branch that behaves in a pseudo-random way (random, but fixed seed). I'm not sure that's a really good example of real world branching.
How would the various branch predictors perform when the branch taken varies from 0% likely to 100% likely, in say, 5% increments?
How would they perform when the contents of both paths are very heavy, which involves a lot of pipeline/SE flushing?
How would they perform when many different branches all occur in sequence?
How costly are their branch mispredictions, relative to one another?
Without info like that, this feels a little pointless.
It is a tiny example, but it measures something. It doesn’t handle the other performance characteristics you mention, but it has the advantage of being a basically pure measurement of the memorization ability of the branch predictors.
The blog post is not very long—not much longer than some of the comments we’ve written here about it. So, I think it is reasonable to expect the reader to be able to hold the whole thing in their head, and understand it, and understand that it is extremely targeted at a specific metric.
Their post gives the impression that clearly AMD's branch prediction is better, because this one number is bigger. "Once more I am disappointed by Intel"
While it could very well be true that the AMD branch predictor is straight-up better, the data they provided is insufficient for that conclusion.
You may want to look up who Daniel Lemire is and the work he's done. What he's basically saying is "in the totality of things I've examined where Intel has come up short, this is another data point that is in line with their performance across the board". It's not "this one benchmark proves Intel sucks hurr hurr" - it's saying it's yet another data point supporting the perception that Intel is struggling against the competition.
Before switching to a hot and branchless code path, I was seeing strangely lower performance on Intel vs. AMD under load. Realizing the branch predictor was the most likely cause was a little surprising.
Enlarging a branch predictor requires area and timing tradeoffs. CPU designers have to balance branch predictor improvements against other improvements they could make with the same area and timing resources. What this tells you is that either Intel is more constrained for one reason or another, or Intel's designers think that they net larger wins by deploying those resources elsewhere in the CPU (which might be because they have identified larger opportunities for improvement, or because they are basing their decision making on a different sample of software, or both).
I mean, he's comparing 2024 Zen 5 and M4 against two generations behind 2022 Intel Raptor Lake. The Lion Cove should be roughly on par with the M4 on this test.
Does any JIT/AOT/hot code optimization/techniques/compilers/runtime takes into account whether the branch prediction is saturated and try to recompile to go branchless
In general branchless is better for branches that can't be predicted 99.something %, saturating the branch prediction like this benchmark isn't a concern. The big concern is mispredicting a branch, then executing 300 instructions and having to throw them away once the branch is actually executed.
Using random values defeats the purpose of the branch predictor. The best branch predictor for this test would be one that always predicts the branch taken or not taken.
There will be runs of even and runs of odd outputs from the rng. This benchmark tests how well does the branch predictor "retrain" to the current run. It is a good test of this adaptability of the predictor.
The benchmark is still narrow in focus, and the results don't unequivocally mean AMD's predictor is overall "the best".
Hmm, that's interesting. The code as written only has one branch, the if statement (well, two, the while loop exit clause as well). My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times.
But that's clearly not right, because apparently the specific data it's branching off matters too? Like, "test memory location X, and branch at location Y", and it remembers both the specific memory location and which specific branch branches off of it? That's really impressive, I didn't think branch predictors worked like that.
Or does it learn the exact pattern? "After the pattern ...0101101011000 (each 0/1 representing the branch not taken/taken), it's probably 1 next time"?
Your mental model is close. Predictors generally work by having some sort of table of predictions and indexing into that table (usually using some sort of hashing) to obtain the predictions.
The simplest thing to do is use the address of the branch instruction as the index into the table. That way, each branch instruction maps onto a (not necessarily unique) entry in the table. Those entries will usually be a two-bit saturating counter that predicts either taken, not taken, or unknown.
But you can add additional information to the key. For example, a gselect predictor maintains a shift register with the outcome of the last M branches. Then it combines that shift register along with the address of the branch instruction to index into the table: https://people.cs.pitt.edu/~childers/CS2410/slides/lect-bran... (page 9). That means that the same branch instruction will map to multiple entries of the table, depending on the pattern of branches in the shift register. So you can get different predictions for the same branch depending on what else has happened.
That, for example, let’s you predict small-iteration loops. Say you have a loop inside a loop, where the inner loop iterates 4 times. So you’ll have a taken branch (back to the loop header) three times but then a not-taken branch on the fourth. If you track that in the branch history shift register, you might get something like this (with 1s being taken branches):
11101110
If you use this to index into a large enough branch table, the table entries corresponding to the shift register ending in “0111” will have a prediction that the branch will be not taken (i.e. the next outcome will be a 0) while the table entries corresponding to the shift register ending in say “1110” will have a prediction that the next branch will be taken.
So the basic principle of having a big table of branch predictions can be extended in many ways by using various information to index into the table.
Check out [1]: it has the most thorough description of branch prediction I've ever seen (chapter 3), across a lot of historical and current CPUs. It is mostly empirical, so you do have to take it with a grain of salt sometimes (the author acknowledges this).
Supposedly the branch prediction on modern AMD CPUs is far more sophisticated, based on [2] (a citation pulled from [1]).
[1] https://www.agner.org/optimize/microarchitecture.pdf
[2] https://www.cs.utexas.edu/%7Elin/papers/hpca01.pdf
There are many branch prediction algorithms out there. They range from fun architecture papers that try to use machine learning to static predictors that don’t even adapt to the prior outcomes at all.
Typical branch predictors can both learns patterns (even very long patterns) and use branch history (the probability of a branch being taken depends on the path taken to reach that branch). They don't normally look at data other than branch addresses (and targets for indirect branches).
They can't. The data that would be needed isn't available at the time the prediction is made.
Yeah, otherwise you wouldn't need to predict anything.
I guess the generate_random_value function uses the same seed every time, so the expectation is that the branch predictor should be able to memorize it with perfect accuracy.
But the memorization capacity of the branch predictor must be a trade-off, right? I guess this generate_random_value function is impossible to predict using heuristics, so I guess the question is how often we encounter 30k long branch patterns like that.
Which isn’t to say I have evidence to the contrary. I just have no idea how useful this capacity actually is, haha.
30k long patterns are likely rare. However in the real world there is a lot of code with 30k different branches that we use several times and so the same ability memorize/predict 30k branches is useful even though this particular example isn't realistic it still looks good.
Of course we can't generalize this to Intel bad. This pattern seems unrealistic (at least at a glance - but real experts should have real data/statistics on what real code does not just my semi-educated guess), and so perhaps Intel has better prediction algorithms for the real world that miss this example. Not being an expert in the branches real world code takes I can't comment.
Yeah, I’m also not an expert in this. Just had enough architecture classes to know that all three companies are using cleverer branch predictors than I could come up with, haha.
Another possibility is that the memorization capacity of the branch predictors is a bottleneck, but a bottleneck that they aren’t often hitting. As the design is enhanced, that bottleneck might show up. AMD might just have most recently widened that bottleneck.
Super hand-wavey, but to your point about data, without data we can really only hand-wave anyway.
https://chromium.googlesource.com/chromiumos/third_party/gcc... has some looong select/case things with lots of ifs in them, but I don't think they would hit 30k.
AMD CPUs have been killing it lately, but this benchmark feels quite artificial.
It's a tiny, trivial example with 1 branch that behaves in a pseudo-random way (random, but fixed seed). I'm not sure that's a really good example of real world branching.
How would the various branch predictors perform when the branch taken varies from 0% likely to 100% likely, in say, 5% increments?
How would they perform when the contents of both paths are very heavy, which involves a lot of pipeline/SE flushing?
How would they perform when many different branches all occur in sequence?
How costly are their branch mispredictions, relative to one another?
Without info like that, this feels a little pointless.
It is a tiny example, but it measures something. It doesn’t handle the other performance characteristics you mention, but it has the advantage of being a basically pure measurement of the memorization ability of the branch predictors.
The blog post is not very long—not much longer than some of the comments we’ve written here about it. So, I think it is reasonable to expect the reader to be able to hold the whole thing in their head, and understand it, and understand that it is extremely targeted at a specific metric.
He isn't trying to determine how well it works. He's trying to determine how large it is.
Their post gives the impression that clearly AMD's branch prediction is better, because this one number is bigger. "Once more I am disappointed by Intel"
While it could very well be true that the AMD branch predictor is straight-up better, the data they provided is insufficient for that conclusion.
You may want to look up who Daniel Lemire is and the work he's done. What he's basically saying is "in the totality of things I've examined where Intel has come up short, this is another data point that is in line with their performance across the board". It's not "this one benchmark proves Intel sucks hurr hurr" - it's saying it's yet another data point supporting the perception that Intel is struggling against the competition.
Before switching to a hot and branchless code path, I was seeing strangely lower performance on Intel vs. AMD under load. Realizing the branch predictor was the most likely cause was a little surprising.
How does the benchmark tell how many branches were mispredicted? Is that something the processor exposes?
Enlarging a branch predictor requires area and timing tradeoffs. CPU designers have to balance branch predictor improvements against other improvements they could make with the same area and timing resources. What this tells you is that either Intel is more constrained for one reason or another, or Intel's designers think that they net larger wins by deploying those resources elsewhere in the CPU (which might be because they have identified larger opportunities for improvement, or because they are basing their decision making on a different sample of software, or both).
I mean, he's comparing 2024 Zen 5 and M4 against two generations behind 2022 Intel Raptor Lake. The Lion Cove should be roughly on par with the M4 on this test.
That would fall under "more constrained", due to process limits.
Does any JIT/AOT/hot code optimization/techniques/compilers/runtime takes into account whether the branch prediction is saturated and try to recompile to go branchless
In general branchless is better for branches that can't be predicted 99.something %, saturating the branch prediction like this benchmark isn't a concern. The big concern is mispredicting a branch, then executing 300 instructions and having to throw them away once the branch is actually executed.
Using random values defeats the purpose of the branch predictor. The best branch predictor for this test would be one that always predicts the branch taken or not taken.
The author is running the benchmark multiple times with the same random seed to discover how long a pattern can the predictor learn.
There will be runs of even and runs of odd outputs from the rng. This benchmark tests how well does the branch predictor "retrain" to the current run. It is a good test of this adaptability of the predictor.
The benchmark is still narrow in focus, and the results don't unequivocally mean AMD's predictor is overall "the best".