The ITTAGE indirect branch predictor

Summary

While investigating the performance of the new Python 3.14 tail-calling interpreter, I learned (via this very informative comment from Sam Gross) new (to me) piece of performance trivia: Modern CPUs mostly no longer struggle to predict the bytecode-dispatch indirect jump inside a “conventional” bytecode interpreter loop. In steady-state, assuming the bytecode itself is reasonable stable, modern CPUs achieve very high accuracy predicting the dispatch, even for “vanilla” while / switch-style interpreter loops! Intrigued, I spent a bit of time reading about just how branch predictors achieve this feat. I found the answer pretty fascinating, so I’m going to try to share the salient high-level features – as I understand them – as well as some interesting connections and ideas that came up in response. A quick caveat: I am not a hardware engineer or CPU designer, and I’m mostly going to be focused on some high-level ideas I find interesting. I’ll probably get some things wrong. If you want an introduction to CPU branch prediction by someone who actually knows what they’re talking about, I’ll refer you to Dan Luu’s piece on the topic. The TAGE and ITTAGE branch predictors 🔗︎ In general, modern state-of-the-art CPUs don’t seem to document too much about their branch predictors, so we don’t know – or at least, I couldn’t easily discover – what branch prediction looks like in real cutting-edge CPUs. However, there is (at least) one published algorithm that is both practical and can predict bytecode interpreter loops – the ITTAGE indirect branch predictor – and that’s what I’m talking about. The author of that predictor wrote a paper exploring prediction on bytecode interpreters and found that his ITTAGE exhibited similar performance to Intel Haswell CPUs and suggested they use a variation of it, but I don’t think we know for sure. ITTAGE is a variant of the TAGE predictor; TAGE predicts taken/not-taken behavior for conditional branches, while ITTAGE predicts the destination o...