The Indirect Branch Predictor's BTB Collision Problem: Why Two Unrelated Function Pointers Can Fight for the Same Slot

2026-08-22

The Branch Target Buffer (BTB) is a hash table indexed by the low bits of an instruction's address. When two indirect branches — say, two call rax instructions at different addresses — happen to hash to the same BTB set, they alias. Each one overwrites the other's prediction, and both suffer mispredictions they wouldn't suffer in isolation. This is BTB collision, and it's one of the sneakiest performance cliffs in modern CPUs.

The problem is amplified for indirect branches because their targets aren't encoded in the instruction — the CPU has no fallback. When the BTB misprediction fires, the pipeline flushes 15–20 stages of speculative work. That's ~20 cycles wasted per collision, and if the collision happens in a hot loop, you're bleeding IPC continuously.

Concrete example: A JIT-compiled interpreter (JavaScript, Python via PyPy, Lua) dispatches bytecodes via a computed jump table — one jmp [rax*8 + table] per bytecode. Modern engines use threaded dispatch, replicating the dispatch instruction at the end of every handler, precisely so each dispatch site gets its own BTB entry and learns its own local transition pattern. LuaJIT saw a 20–40% speedup switching from a single centralized dispatch to threaded dispatch — same instructions, same targets, just spread across the BTB instead of aliasing into one slot.

Why aliasing is worse than a cold miss: A cold BTB entry gets filled on first execution and starts predicting. An aliased entry gets trained wrong — every visit from function A poisons the prediction for function B, and vice versa. The predictor never converges. It's the difference between "unknown" and "actively lied to."

Rule of thumb: A typical Skylake/Zen BTB has ~4K entries with 4-way associativity, indexed by bits [13:4] of the PC (cache-line-aligned). Two indirect branches whose addresses differ by exactly 16KB (or any multiple) will collide. If you have N hot indirect branches, expect meaningful aliasing once N approaches ~1000 — well below the nominal capacity, because hash collisions kick in early (birthday paradox: √4096 ≈ 64 before first collision becomes likely).

Mitigations in the wild: Compilers align hot indirect-call sites to spread them across BTB sets. LLVM's -falign-functions=32 helps. Intel's ITA (Indirect Target Array), a separate structure for indirect branches with tagged entries, reduces aliasing by making entries distinguishable — an alias no longer overwrites, it fails to match and falls back to a default predictor.

Key Takeaway: Indirect branches sharing a BTB set actively poison each other's predictions — threaded dispatch works because it gives each call site its own BTB home instead of forcing them to fight.

All newsletters