Every time your program reaches an if, the processor faces a problem it should not have: the answer to that question does not exist yet. The value that decides the branch may come from a memory read that will take hundreds of cycles to arrive. And still, the processor cannot stand idle, because its pipeline is twenty stages deep and stopping it costs more than being wrong. So it does the only thing it can do: it bets. And it bets billions of times per second, with an accuracy around 99%.
The problem: deciding before knowing
A modern core does not execute instructions one after another from start to finish; it works on several at once, each in a different stage: fetch, decode, rename registers, schedule, execute, write back and retire. That design only works if the instruction stream is known in advance. The trouble is that, in real code, one in five or six instructions is a jump: a compiled if, the end of a loop, a function call or a return. The moment one appears, the processor does not know which bytes it has to fetch next.
If it waited for the condition to resolve, the pipeline would drain every few instructions and throughput would halve or worse. The earliest pipelined processors solved it with a simple rule —backward jumps are taken, forward ones are not— because a backward loop usually repeats and a forward if usually means the exception. Those static hints still exist, and that is why compilers mark branches with __builtin_expect or C++20’s [[likely]] attribute: they do not change what the program does, they just give the hardware a hunch.
The bet is learned: saturating counters
Dynamic prediction began with a tiny idea: a two-bit counter per branch. Values 0 and 1 mean “not taken”, 2 and 3 mean “taken”, and the counter moves up or down according to what happened last time. The key insight is that one bit is not enough: with a single bit, a pattern such as taken, not taken, taken, not taken produces a miss on every iteration. With two bits, an isolated miss does not flip the prediction, and the predictor becomes resistant to noise.
That counter is indexed by the address of the jump instruction, which gives the pattern history table. But the real pattern of many branches depends on context, not just on their own history. Hence the most elegant correction: index the table with the branch address combined (XOR) with the global history register of the last taken or not-taken jumps. The scheme is called gshare, and its intuition is neat: if two branches share an index, it does not matter, because the global history disambiguates them in most cases.
TAGE: several memories of different lengths
The state of the art is called TAGE (TAgged GEometric history length). Instead of a single table, it keeps several, each specialised in a different history length: one looks at the last 5 jumps, another at the last 20, another at the last 80, and so on in geometric progression up to histories of hundreds of jumps. Each entry carries a tag that avoids collisions plus a confidence counter. When several tables hit, the one that used the longest history wins, because it holds the most information.
Complementary structures are added on top. The branch target buffer remembers not only whether the jump is taken but where it goes, so the fetch of the next instruction can start right there. A return address stack remembers the return addresses of calls, because ret instructions are trivial to predict if you track where each function came from. And indirect jumps —function pointers, virtual tables in object-oriented languages— need their own predictor (ITTAGE), which can combine a history of target addresses with program context.
All that machinery takes real silicon: tens of kilobytes of associative memories, tag comparators and update logic, running in parallel with the rest of the core. It is not free; every correct prediction is paid for in die area and power.
What a miss costs
When the predictor is right, the processor keeps working as if it knew the future: it decodes, it executes and it even writes results for instructions that might never have been meant to run. That is possible thanks to register renaming and the reorder buffer, which allow out-of-order execution while results are retired in strict order. If the bet fails, everything speculated is discarded and the program counter jumps back to the real branch: 15 to 20 lost cycles on a modern x86, around 10 on Apple cores.
The arithmetic is easy and explains a lot. A processor at 4 GHz with a 5% miss rate and a 17-cycle penalty loses some 3.4 billion cycles per second, close to one cycle per instruction in real workloads. And some patterns resist: random data, linked lists —each node depends on the previous one and its address is only known at the end— and anything driven by unpredictable input. A classic example: walking a vector and summing the elements above a threshold is much faster if the vector is sorted, because the outcome of the comparison stops being random.
Speculation is also a security hole
Here is the uncomfortable part. If the processor executes instructions it should not have executed before verifying the prediction, those instructions can read protected memory and leave a trace in the cache. That is the idea behind Spectre: it breaks no permission, it tricks the predictor so that the victim speculates down a path that was not its own, and the attacker then measures cache access times to infer the data. Meltdown exploited the same thing through out-of-order execution to read kernel memory.
Defences arrived in layers: separating the kernel and user page tables, barriers that prevent speculation across certain constructs, and retpoline, a compiler technique that turns indirect jumps into a sequence the predictor cannot use maliciously. They all work, and they all cost performance: disabling aggressive prediction in certain contexts is, literally, paying speed so as not to leak memory.
The upshot is that branch prediction is one of the quiet engines of the performance gains of the last three decades, and also a reminder that hardware does not execute only what the programmer writes: it executes what it believes you are about to write. When that belief is right, you gain an order of magnitude. When it is wrong, you lose it in the form of cycles, of milliseconds of queueing and, occasionally, of a vulnerability that takes years to close.
