[HN Gopher] How many branches can your CPU predict?
___________________________________________________________________
How many branches can your CPU predict?
Author : ibobev
Score : 119 points
Date : 2026-03-19 12:49 UTC (10 hours ago)
(HTM) web link (lemire.me)
(TXT) w3m dump (lemire.me)
| withinboredom wrote:
| 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.
| stephencanon wrote:
| 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).
| pbsd wrote:
| 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.
| stephencanon wrote:
| That would fall under "more constrained", due to process
| limits.
| bee_rider wrote:
| 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.
| bluGill wrote:
| 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.
| bee_rider wrote:
| 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.
| IcePic wrote:
| 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.
| rayiner wrote:
| 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.
| dundarious wrote:
| 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".
| gpderetta wrote:
| The author is running the benchmark multiple times with the
| same random seed to discover how long a pattern can the
| predictor learn.
| OskarS wrote:
| 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"?
| gpderetta wrote:
| 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).
| jeffbee wrote:
| They can't. The data that would be needed isn't available at
| the time the prediction is made.
| 1718627440 wrote:
| Yeah, otherwise you wouldn't need to predict anything.
| LPisGood wrote:
| 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.
| rayiner wrote:
| 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.
| jcalvinowens wrote:
| 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
| Night_Thastus wrote:
| 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.
| jeffbee wrote:
| He isn't trying to determine how well it works. He's trying to
| determine how large it is.
| Night_Thastus wrote:
| 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.
| vlovich123 wrote:
| 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.
| bee_rider wrote:
| 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.
| user070223 wrote:
| 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
| BoardsOfCanada wrote:
| 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.
| piinbinary wrote:
| How does the benchmark tell how many branches were mispredicted?
| Is that something the processor exposes?
___________________________________________________________________
(page generated 2026-03-19 23:01 UTC)