Photo by Alexandre Debiève on Unsplash
Branch Target Buffer: Indirect Jump Prediction
Modern CPUs don’t just execute instructions in order. They speculate aggressively, predicting which code will run next to keep the pipeline full. While conditional branches get most of the attention, indirect jumps—where the target address comes from a register or memory—pose a harder prediction problem. That’s where the branch target buffer comes in.
What BTB Solves
A conditional branch has two possible outcomes: taken or not taken. The CPU can predict the direction and prefetch the right instruction stream. An indirect jump or call, by contrast, can land anywhere. Virtual function calls in C++, function pointers in C, interface method calls in Java, and large switch statements all compile to indirect control flow.
Without prediction, the CPU would stall every time it hit an indirect jump, waiting for the target address to resolve. At 10-20 cycle branch misprediction penalties on modern processors, this would crater performance in object-oriented code.
The branch target buffer is a cache that maps instruction addresses to predicted jump targets. When the CPU encounters an indirect branch, it looks up the program counter in the BTB. If there’s a hit, it speculatively fetches from the predicted target and continues execution. If the prediction is wrong, it flushes the pipeline and restarts from the correct address.
How BTB Differs from Branch Prediction
The BTB works alongside but separately from the directional branch predictor. Directional predictors answer “will this branch be taken?” using pattern history and correlation. The BTB answers “where will this indirect jump go?” using recent target history.
A typical BTB is a set-associative cache indexed by the branch instruction address. Each entry stores the last observed target for that branch site. Some designs track multiple recent targets per entry to handle polymorphic call sites where a few different targets dominate.
The BTB has limited capacity—typically a few thousand entries. When a new indirect branch evicts an old entry, prediction accuracy for that evicted branch drops to zero until it’s relearned.
The Megamorphic Call Problem
Here’s where things get interesting for high-level languages. Consider a virtual function call in a tight loop iterating over a heterogeneous collection. If the objects have four different types, the call site sees four different targets interleaved unpredictably.
Most BTBs track one or maybe two recent targets per site. A call site with many targets thrashes the BTB entry, causing repeated mispredictions. This is the megamorphic call problem that plagues dynamic dispatch in performance-sensitive code.
JIT compilers handle this with inline caching and polymorphic inline caches. They generate code that checks the type against one or two common cases before falling back to a full virtual dispatch. This transforms a megamorphic site into a series of monomorphic branches that the BTB and branch predictor can handle.
BTB Pollution and Interaction Effects
BTB capacity matters more than you’d expect. A polymorphic call site doesn’t just hurt its own performance—it can evict entries for other indirect branches, spreading the damage.
Large switch statements compiled to jump tables cause similar issues. The compiler generates code that loads from a table of addresses, then jumps to the result. Each case is a different target for the same branch instruction, and a switch over many cases becomes unpredictable.
Modern compilers mitigate this by using binary search trees of comparisons for switches with many cases, trading ALU work for better branch prediction. The threshold where this becomes worthwhile depends on BTB size and the distribution of cases.
Return Address Prediction
Function returns are indirect branches—the target comes from the stack. But returns have structure: they follow a last-in-first-out pattern. CPUs exploit this with a dedicated return stack buffer, a small hardware stack that shadows function calls and returns.
The return stack buffer predicts return targets far more accurately than a BTB could, since it leverages call/return pairing. It’s typically 16-32 entries deep. Exceed that depth with a deep call chain, and return prediction falls back to the BTB with much worse accuracy.
Tail call optimization matters here. A tail-recursive function compiled to a loop doesn’t overflow the return stack buffer. Without TCO, deep recursion eventually exhausts the RSB and starts mispredicting returns.
Why This Matters Now
As software moves toward more dynamic, plugin-based architectures with interface-heavy designs, indirect control flow increases. Microservices written in high-level languages, browser engines executing JavaScript, and data processing pipelines with user-defined functions all depend on BTB performance.
Understanding BTB behavior helps explain why monomorphic call sites outperform polymorphic ones by 10x in microbenchmarks, why interface dispatch in tight loops shows up in profiles, and why some design patterns that look equivalent on paper have very different runtime characteristics.
The BTB is invisible in the ISA, but it shapes what “fast” actually means for indirect control flow. When designing performance-critical abstractions, the question isn’t just “how many instructions does this generate” but “can the CPU predict where this will jump?”