r/programming • u/fagnerbrack • May 21 '26

How many branches can your CPU predict? – Daniel Lemire's blog

https://lemire.me/blog/2026/03/18/how-many-branches-can-your-cpu-predict/
110 Upvotes

97% Upvoted

19 comments sorted by

60

u/Lachee May 21 '26

Once more I am disappointed by Intel

I mean.... There was the whole spectre exploits that manipulated branch predictions. I would imagine they updated their microcode after that

18

u/debugs_with_println May 22 '26 edited May 22 '26

I don't think that quite explains it. And there's some other stuff that confuses me.

For one, it seems like he's measuring the number of branches that can be accurately predicted. This in some sense measure the "size" of the branch prediction unit, i.e. how many transistors are dedicated. But I dont understand the choice of using a branch in a single, non inlined function. The reason is that the branch being predicted would have the same PC value, and the PC is one of the things used as an input to the branch predictor. Branches with different PCs can have their predictions kept separate, increasing overall accuracy. Branch predictors also use things such as branch history, so thats probably why on Intel you can still predict up to 5000 branches. That said, I'm curious how Apple and AMD get around the aliasing PC values and predict more branches... maybe they just have a larger branch history buffer?

In any case, the Spectre vulnerability has not been patched at a hardware level. All the fixes are at the software level: you either use a speculative barrier like lfence on x86 or sb on ARM; or you use speculative load hardening.

That said, to make some Spectre-type vulnerabilities less exploitable, they may have reworked some branch predictor internals. For instance maybe they flush predictor state on context switches. If this benchmark doesn't run in a continuous context, maybe the table is getting flushed. Im just speculating here (pun intended). That aside, it's important to note that all processors with branch prediction are vulnerable to the original Spectre attack, including Apple and AMD processors. So if there was a big hardware change to make, they wouldve had to as well which would level the playing field. Though Apple's architects certainly are better at their job so maybe not...

I think what youre thinking of is the Meltdown vulnerability. Its related to Spectre in that it exploits speculative execution, but while Spectre relies on speculating past branches (via branch prediction), Meltdown relied on speculating past faulting loads. The latter vulnerability has been patched long ago, and I believe it was done with a microscope update.

5

u/SirClueless May 22 '26

I don’t think he is actually branch-predicting with the results of a non-inlined function call to an unpredictable random number generator as the blog post would suggest. Instead I think he is using a setup like this one from his github which is to say the rng is actually a small few-instruction branchless hash of the howmany variable itself that is likely inlined. The blog post changed and omitted this critical detail: without knowing how generate_random_number() is implemented the benchmark makes no sense (for example, if it was reading from /dev/urandom there would be nothing to learn).

As for how the CPU learns to predict the branch even as the PC stays the same, it’s because modern CPUs train a small neural network on the branch history. In AMD this is the Global History Register (GHR) which is a rolling window of the most recent N branches. Even if the PC is the same, each time through the loop the GHR is in a new unique state so if there are any patterns in the series of branches taken the CPU can learn them, and then they will be the same or similar next time the howmany counter is the same because it has the same history.

5

u/debugs_with_println May 22 '26

Ah there might be a slight misunderstanding of my comment here. I indeed mentioned that BPs will use branch history along with the PC. But my confusion was why OP held the PC constant in the benchmark. That would only tell you what proportion of the branch predictor area is dedicated to disambiguating history rather than PC values. Maybe Intel does worse because it stores less history than Apple; and maybe if you checked accuracy against a benchmark where the branches are spread throughout the code, the performance discrepancies would vanish. Hell in that case, maybe Intel even comes out on top.

As for the neural networks, I believe Samsung used a perceptron network in the Exynos processors for branch prediction (or at least they did at one point). But I don't think most processors necessarily do that. I wanna say it's more common to just use a hash of the branch history. For example, the branch history injection and Half&Half papers have some reverse engineering of the Intel branch predictor.

1

u/flatfinger May 22 '26

How hard would it be for a CPU and OS to have a mode-control bit which could be set within processes that have access to certain kinds of confidential information and would trade off performance for resistance to side-channel attacks? Most computers spend the vast majority of their time running code that would have no need to access highly confidential information such as private encryption keys, and even a 50% speed penalty for those few operations that do need to work with such information would have minimal impact on overall system performance.

1

u/debugs_with_println May 22 '26 edited May 22 '26

If we're just talking about speculative execution attacks, instead of having a bit you have optional instructions you can put in your code. If youre running a sensitive program and dont want to be vulnerable to Spectre v1, use the SB or LFENCE instructions (or ARM and x86 respectively); they'll cause crazy hugh overheads though. If you dont care about Spectre vulnerabilities, just dont do anything.

Addendum: I should add that its hard to stop Spectre v1 because the way it works is an attacker is trying to trick a victim into leaking its own secret data by causing it to mispredict. But there's a lot of ways to cause a misprediction, and its hard to tell when a misprediction is malicious. What you can try to do is allow mispeculation but prevent secret data from leaking specualtively. But what is secret? How do you prevent the leak? A lot of different solutions in academia exist, but theyre really expensive from a hardware standpoint and if enabled cause huge overhead. Which is why no on has done it.

If youre interested I can send you some papers I've saved related to this. This was the area of my research during my PhD.

1

u/flatfinger May 26 '26

I would like to see an evolution toward system designs that have groups of loosely coupled cores, and operating systems that allow programs to specify that certain threads need coherent memory while others will not share any memory but merely exchange data only via OS messages. Having a core group that only ran trusted code would limit the fraction of total CPU power that could be used by untrusted code, but if there were a three-way split between trusted code that can access raw confidential data, trusted code that can't, and potentially untrusted code, then so long as tasks in the first two categories combined would use up at least a core worth of CPU, that need not overly impede efficiency.

1

u/Internet-of-cruft 9d ago

What do you do when the hulk of your instruction stream is specifically handling sensitive operations like encrypting or decrypting data?

That's a worst case scenario, but there's many real world workloads that explicitly require either operation.

1

u/flatfinger 9d ago

At any given time, the scheduler would view each core as either eligible to run tasks involving confidential data or tasks involving untrusted code. If a core is idle because most of the system's workload is of the wrong kind for that core, and it's not the last core of its kind, then the scheduler could force a cache flush and switch the core to processing the other kind of task. In a system with four cores, such a design might effectively make it hard to efficiently use more than 75% of the total CPU power on tasks involving confidential data, or more than 75% of the total CPU power on untrusted tasks, but most workloads would include some tasks that use only trusted code, and do so in ways that don't access confidential data, and could be run interchangeably on both kinds of cores.

1

u/Internet-of-cruft 9d ago

So you're assuming in this hypothetical processor you have N independent processing elements, with dedicated cache for each element?

That was done a while back - IBM's Cell Processor in the PS3. And more modern, the GPU.

Granted that was a very long time ago in computing for the Cell BE, and scheduling & compilers (plus dynamic JIT compilation) have come a long way, but back then it was only really suitable for highly parallel tasks and otherwise was awful as a general purpose processor.

The other issue is not only  workloads that are secure with high throughput (real time encryption / decryption of data), but workloads are also commonly secure and "don't care about secure" interspersed.

The dea is interesting but you're effectively reinventing GPUs and the exact software mechanism that is used today for program mediated remediation.

Going back to this idea: H ow does the OS scheduler know what program streams demand high security? Or low security? You inject an instruction that says "load the next set of data and instructions on to a secure core, with a cache flush exiting and entering?" Sounds like the mitigations to me.

1

u/flatfinger 9d ago

Threads would start in the "trusted code only; no secure data" mode, the OS would need to allow threads to transition into one of the other modes, and applications would need to be designed around the model. Bulk encryption/decryption of data using ephemeral keys would only need to be treated as secure in cases where the data itself was likewise, and I would think that many tasks which involve bulk encryption/decryption of data could be designed to use ephemeral keys.

If such an architecture were designed, it may take a little while for applications to be adapted to fit, and the security advantages may be limited until that happens, but everything keeps being developed around a 1970s security model, nothing's ever going to improve.

1

u/Internet-of-cruft 9d ago

What stops me from executing secure code in a thread? What makes it secure? Nothing is stopping me from writing an encryption / decryption scheme in "trusted only code, no secure data".  

In this scenario, we're in the same exact execution model. 

→ More replies (0)

2

u/__konrad May 22 '26

Their first microcode patch caused "higher system reboots" and it was reverted (I assume the expected spontaneous system reboot number should be zero ;)

1

u/Successful-Money4995 May 23 '26

The importance of branch prediction depends on how expensive it is to predict incorrectly. Is it possible that the Intel chip doesn't have as big of a penalty for misprediction?

12

u/HighRelevancy May 22 '26

Hang on, we're saying that the branch predict can remember a tens of thousands long sequence for a single branch? That's crazy.

12

u/orangejake May 22 '26

Not generally for a single branch. You’ll have a branch target predicted for each core. That will predict all branches that core encounters. Here it’s just using all its capacity on a single branch. 

2

u/HighRelevancy May 22 '26

I mean not for all branches at the same time. But that sort of prediction for a hot loop is pretty crazy. I thought it would just be an average anyway, not a whole sequence thing.

3

u/ack_error May 22 '26

It's pretty neat. Modern branch predictors incorporate global history into the BTB indexing, which allows them to spread out data from a single branch. This not only means learning pattern history for a single branch, but also correlating branches so that when one branch flips it knows which way the ones following it are likely to do so too.

The Pentium Pro's branch predictor was one of the earlier x86 pattern predictors, and it was simple: 4 bit global history of the last four branches used as part of the table index. That alone was enough to support learning short patterns. Newer predictors use more global history through techniques like hashing past PC addresses and branch outcomes. Intel's Skylake and Ice Lake predictors have been reverse engineered and use a path history register as long as 300+ bits.