What Your CPU Does When It Doesn't Know What Comes Next: The Hidden Science of Branch Prediction

The most famous question on Stack Overflow isn’t about JavaScript frameworks or Git commands. It’s about why sorting an array makes code run faster. The answer—branch prediction—revealed something most programmers never consider: your CPU spends considerable effort guessing what your code will do next.

In 2012, a user named GManNickG asked why processing a sorted array took 11.777 seconds while the same operation on unsorted data took only 2.352 seconds—a 5x difference for identical computation. The accepted answer, written by user Mysticial, became the highest-voted answer in Stack Overflow history. It wasn’t about algorithms. It was about how processors handle uncertainty.

The Pipeline Problem

To understand why branch prediction exists, you need to understand what happens when a CPU executes instructions. Modern processors don’t execute one instruction at a time. They use pipelines—assembly lines where different stages of multiple instructions are processed simultaneously.

A typical modern CPU pipeline has 14-19 stages. Intel’s NetBurst architecture (Pentium 4) pushed this to an extreme 31 stages. At each stage, a different part of the processor works on a different instruction. The fetch unit grabs the next instruction from memory. The decoder figures out what it means. The execution unit performs the actual computation. The write-back stage stores results.

This works beautifully for sequential code. While instruction B is being decoded, instruction A is being executed. While instruction C is being fetched, instruction B is being decoded and instruction A is being written back. The pipeline stays full, and throughput approaches one instruction per clock cycle.

Then a branch appears.

if (x > threshold) {
    // path A
} else {
    // path B
}

The fetch unit needs to grab the next instruction. But which one? Path A or path B? The condition x > threshold hasn’t been evaluated yet—it’s still working its way through the pipeline. The fetch unit has no idea which instruction comes next.

Without prediction, the pipeline stalls. Every stage sits idle waiting for the branch condition to resolve. On a 15-stage pipeline, that’s potentially 15 cycles of doing nothing. Given that branches appear every 5-10 instructions in typical code, a processor without branch prediction would spend most of its time waiting.

sequenceDiagram
    participant F as Fetch
    participant D as Decode
    participant E as Execute
    participant W as Writeback
    
    Note over F,W: Normal pipeline flow - instructions overlap
    F->>D: Inst A
    D->>E: Inst A
    E->>W: Inst A
    F->>D: Inst B (Branch)
    D->>E: Inst B
    Note over F: Which instruction next?
    Note over F: Pipeline STALLS
    Note over F: Waiting for branch result...
    E->>W: Inst B (resolved)
    Note over F: Now we know target

The Evolution of Prediction: From Simple to Sophisticated

Static Prediction: The Naive Approach

The earliest approach was static prediction—guess without any runtime information. Intel’s early Pentium processors used a simple heuristic: predict backward branches (loop bottoms) as taken, forward branches (if-statements) as not taken.

This works because loops typically execute multiple times. A backward branch that returns to the top of a loop should be taken on most iterations. Forward branches skip code; predicting “not taken” means executing the straight-line path first.

The accuracy was mediocre—around 70-80%. But even this crude approach was far better than stalling. Dan Luu’s analysis shows that a 70% accurate predictor reduces the effective cost per instruction from 4.8 cycles to 2.14 cycles compared to no prediction—a 55% improvement.

Two-Bit Saturating Counters: Learning from History

The breakthrough came from a simple observation: branches tend to behave consistently. If a branch was taken the last three times, it will probably be taken the next time.

A two-bit saturating counter implements this insight elegantly. The counter has four states:

• 00: Strongly not taken
• 01: Weakly not taken
• 10: Weakly taken
• 11: Strongly taken

When a branch executes, the counter increments (if taken) or decrements (if not taken). The counter “saturates” at 00 or 11—it can’t overflow or underflow. Prediction uses the high bit: states 10 and 11 predict taken; states 00 and 01 predict not taken.

The hysteresis is crucial. If a branch has been consistently taken (state 11), a single not-taken outcome moves it to state 10, still predicting taken. The predictor doesn’t immediately flip its prediction—it requires consistent contrary evidence.

stateDiagram-v2
    [*] --> SN: Start
    SN --> SN: Not Taken
    SN --> WN: Taken
    WN --> SN: Not Taken
    WN --> WT: Taken
    WT --> WN: Not Taken
    WT --> ST: Taken
    ST --> WT: Not Taken
    ST --> ST: Taken
    
    SN: Strongly Not Taken
    WN: Weakly Not Taken
    WT: Weakly Taken
    ST: Strongly Taken

This simple mechanism, first implemented in the CDC Cyber series in the early 1980s and later in the Intel Pentium (1993), achieved around 89-90% accuracy. For the cost of a few kilobytes of table storage, processors could predict the vast majority of branches correctly.

Two-Level Adaptive Predictors: Pattern Recognition

Two-bit counters learn branch bias but miss patterns. Consider a loop with three iterations:

for (int i = 0; i < 3; i++) { ... }

The branch at the loop bottom produces the pattern TTTN TTTN TTTN… (Taken, Taken, Taken, Not-taken). A two-bit counter sees this as 75% taken and will mispredict the not-taken case every time.

Tse-Yu Yeh and Yale Patt’s 1991 paper introduced the solution: remember not just the bias, but the pattern. A two-level predictor stores:

1. A branch history register (BHR) tracking the last N outcomes of each branch
2. A pattern history table (PHT) of saturating counters indexed by the history

For the loop above, after seeing TTTN a few times, the predictor learns that history “TTT” predicts not-taken, while history “TTN” predicts taken. The pattern gets recognized.

This scheme—called “two-level adaptive” or “correlating” prediction—pushed accuracy to 93-94%. The DEC Alpha 21264 (1998) used a hybrid combining local and global history predictors, achieving around 97% accuracy on SPEC benchmarks.

TAGE: The Modern Standard

The state of the art for branch prediction, introduced by André Seznec in 2006, is TAGE (TAgged GEometric history length predictor). Modern Intel and AMD processors use TAGE variants.

TAGE’s key insight: different branches need different amounts of history. A simple loop might need just a few bits of history. A complex state machine might need hundreds or thousands of bits. No single history length works optimally for all branches.

TAGE maintains multiple predictor tables, each using a different history length. The history lengths follow a geometric progression—perhaps 5, 10, 20, 40, 80, 160, 320 bits. Each table entry is tagged with the branch address to avoid aliasing.

When predicting, TAGE queries multiple tables simultaneously. The prediction from the table with the longest matching history is used. A branch that needs long history gets long history; a branch that needs short history gets short history—automatically.

graph LR
    subgraph "TAGE Predictor Structure"
        PC[Branch PC] --> T1[Table 1<br/>History: 5 bits]
        PC --> T2[Table 2<br/>History: 15 bits]
        PC --> T3[Table 3<br/>History: 45 bits]
        PC --> T4[Table 4<br/>History: 135 bits]
        PC --> Base[Base Predictor]
        
        T1 --> Sel[Selection Logic]
        T2 --> Sel
        T3 --> Sel
        T4 --> Sel
        Base --> Sel
        
        Sel --> Pred[Prediction]
    end

The results are impressive. On the Championship Branch Prediction (CBP) benchmarks, TAGE variants consistently achieve 97-99% accuracy on integer workloads. The remaining 1-3% of mispredictions are often fundamentally unpredictable branches—branches whose outcome depends on truly random data.

The Branch Target Buffer: Where Are We Going?

Predicting whether a branch is taken is only half the problem. The processor also needs to know where it goes.

The Branch Target Buffer (BTB) is a cache that maps branch addresses to their target addresses. When the fetch unit encounters a branch, it queries the BTB. If there’s a hit, the predicted target is available immediately—the fetch unit can start grabbing instructions from the new location without waiting for the branch to execute.

Cloudflare’s investigation into BTB behavior revealed surprising constraints. On AMD EPYC 7642, the BTB holds approximately 4,096 entries. When hot loops exceed this capacity, branch prediction degrades dramatically. Predictions that took ~3.5 cycles with a warm BTB jump to ~10.5 cycles when the BTB overflows.

The BTB is distinct from the direction predictor. A never-taken branch might have an entry in the direction predictor’s table but not in the BTB—there’s no target to remember. Conversely, an unconditional jump always needs a BTB entry even though there’s no direction to predict.

The Return Address Stack

Function returns present a special challenge. They’re indirect branches—the target isn’t encoded in the instruction but determined at runtime. A naive BTB might store only the most recent return target, causing mispredictions on any function called from multiple locations.

The Return Address Stack (RAS), also called Return Stack Buffer (RSB), solves this. It’s a hardware stack that tracks call/return pairs. When a call instruction executes, the return address is pushed. When ret executes, the top address is popped and used as the predicted target.

This works because function calls and returns follow a strict LIFO discipline. Even in recursive calls, the RAS correctly predicts each return to its matching call—assuming the RAS is deep enough. Modern CPUs typically have 16-64 RAS entries.

The Performance Equation

The cost of branch misprediction follows a simple model:

The misprediction penalty on modern processors is typically 15-20 cycles—the time to flush the pipeline and restart from the correct path. Some deep pipelines (like the Pentium 4’s 31 stages) had penalties exceeding 30 cycles.

With SPECint workloads showing approximately 20% branch frequency, even small differences in prediction accuracy have large performance impacts:

These numbers explain why branch prediction receives so much engineering attention. Going from 90% to 97% accuracy—a 7 percentage point improvement—reduces the branch overhead from 38% to 12%, a 3x improvement in the branch-related component of execution time.

The Spectre Connection: When Prediction Becomes a Vulnerability

In January 2018, security researchers revealed Spectre—a class of attacks that exploit speculative execution, of which branch prediction is the primary mechanism. The attack works by deliberately poisoning the branch predictor.

Consider code with a bounds check:

if (index < array_size) {
    result = array[index];
    temp = side_channel[result * 64];
}

The bounds check prevents out-of-bounds access. But the branch predictor doesn’t know about security—it just learns patterns. An attacker can:

1. Train the predictor to expect the branch is taken
2. Call the function with an out-of-bounds index
3. The predictor incorrectly speculates the branch is taken
4. The speculative access reads secret data into cache
5. Even after the misprediction is detected and rolled back, cache timing reveals the secret

The CPU did exactly what it was designed to do—predict branches and speculate optimistically. But the side effects of speculation (cache state changes) weren’t properly isolated. The BTB and other prediction structures became covert channels for information leakage.

Mitigations include:

• Retpoline: Replace indirect branches with a return trampoline that’s safe but slower
• IBRS/IBPB: Hardware controls that isolate branch predictor state between privilege levels
• Enhanced IBRS: Hardware improvements that automatically flush predictor state on context switches

These mitigations have performance costs. Retpoline can add 5-20% overhead for workloads with many indirect branches. The full impact depends on the specific CPU generation and workload characteristics.

Practical Implications for Developers

Understanding branch prediction changes how you think about performance-critical code.

Data-Dependent Branches Are Expensive

The classic example—the sorted array benchmark—demonstrates the issue. When data[c] >= 128 alternates randomly between true and false, no predictor can achieve better than 50% accuracy. Every branch is a coin flip, and the CPU pays the misprediction penalty half the time.

Solutions include:

• Sorting or partitioning data so branches become predictable
• Using branchless techniques like conditional moves
• SIMD vectorization which evaluates all paths simultaneously

The conditional move instruction (CMOV on x86) doesn’t need prediction—it computes both values and selects one based on a condition, with no pipeline disruption. Compilers will often emit CMOV for simple ternary expressions, but complex conditions may require manual intervention.

Profile-Guided Optimization

Modern compilers support Profile-Guided Optimization (PGO), which uses runtime profiling data to improve code generation. For branches, PGO provides:

1. Accurate branch probability estimates for better static prediction
2. Code layout optimization placing likely paths contiguously
3. Improved inlining decisions based on actual call frequencies

Cloudflare reported 5-15% performance improvements from PGO on Go services, largely from better branch layout improving instruction cache behavior.

The [[likely]] and [[unlikely]] Attributes

C++20 introduced [[likely]] and [[unlikely]] attributes to provide hints to the compiler:

if (error_condition) [[unlikely]] {
    handle_error();
}

These hints help compilers arrange code optimally—the likely path gets placed in the fall-through position, improving instruction cache behavior. But they don’t directly affect hardware prediction; the CPU learns branch patterns dynamically regardless of compiler hints.

The attributes are most useful when profiling isn’t available or for cases where static knowledge (like error paths) exceeds what profiling would reveal.

Different CPUs, Different Approaches

Branch prediction implementations vary significantly across architectures and generations.

Intel

Intel’s Core architecture (2006 onward) uses a sophisticated hybrid predictor. Research suggests Haswell (2013) and later use TAGE variants, combined with:

• A dedicated loop predictor for simple counted loops
• An indirect branch predictor (ITTAGE) for virtual function calls
• A deep RAS for return prediction

Intel’s BTB size has grown from ~4K entries in early Core processors to 12K+ in recent generations. The predictor tables are similarly larger, improving accuracy for code with many branches.

AMD

AMD used simpler predictors through the Bulldozer era. Zen (2017) switched to a TAGE-based design. Zen 5 (2024) introduced a “2-ahead” branch predictor that predicts two branches per cycle, attempting to stay ahead of the fetch unit’s bandwidth.

The 2-ahead predictor reflects a new challenge: prediction latency. As predictors grow more sophisticated, the time to compute a prediction can exceed the time to fetch an instruction. Predicting two branches simultaneously allows overlap—while the second prediction is being computed, the first can be used to fetch.

Apple Silicon

Apple’s M1 processors take a different approach. Research suggests the BTB is integrated with the L1 instruction cache—prediction state is tied to cache lines rather than separate structures. This limits prediction capacity to cached code but dramatically reduces prediction latency.

Cloudflare’s benchmarks show M1 achieving ~1 cycle per predicted branch for code that fits in L1 cache, compared to 2-3 cycles on x86. The trade-off: prediction degrades when code exceeds the ~192KB L1 cache size.

The Limits of Prediction

Despite 97%+ accuracy on typical workloads, some branches remain fundamentally unpredictable. Cryptographic code, random number generators, and data-dependent comparisons on truly random input can’t be predicted better than chance.

For these cases, the solution isn’t better prediction—it’s avoiding branches entirely:

• Lookup tables replace conditionals with array indexing
• Bit manipulation computes results without branches
• SIMD processes multiple elements in parallel, masking results
• Specialized instructions like PCMPESTRI for string operations

The goal isn’t to make branches predictable. It’s to recognize when they can’t be and design accordingly.

Looking Forward

Branch prediction research continues. Academic papers explore:

• Perceptron predictors using simple neural networks for prediction
• Geometric history lengths optimized for specific workload classes
• Confidence estimation to identify low-confidence predictions and avoid speculation

The industry trend toward wider pipelines and higher clock speeds makes prediction more important, not less. Each pipeline stage added increases the misprediction penalty; each frequency increase reduces the time available for prediction logic.

Meanwhile, security concerns add new constraints. Spectre demonstrated that aggressive speculation has risks. Future predictors may need to balance performance against security isolation, perhaps accepting lower accuracy for improved safety guarantees.

The fundamental tension remains: the processor must decide what to execute next before it knows what should execute next. Branch prediction—the art and science of guessing correctly—is how modern CPUs resolve that tension billions of times per second.

References

1. Yeh, T. Y., & Patt, Y. N. (1991). Two-Level Adaptive Training Branch Prediction. ACM/IEEE Micro-24.

2. Seznec, A., & Michaud, P. (2006). A Case for (Partially) TAgged GEometric History Length Branch Prediction. Journal of Instruction-Level Parallelism, 8, 1-21.

3. Jiménez, D. A. (2014). Piecewise Linear Branch Prediction. ISCA 2005.

4. Sprangle, E., Chappell, R. S., Alsup, M., & Patt, Y. N. (1997). The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference. ISCA 1997.

5. McFarling, S. (1993). Combining Branch Predictors. WRL Technical Note TN-36, Digital Equipment Corporation.

6. Lee, C. C., Chen, I. C. K., & Mudge, T. N. (1997). The Bi-Mode Branch Predictor. MICRO-30.

7. Kocher, P., et al. (2019). Spectre Attacks: Exploiting Speculative Execution. IEEE S&P 2019.

8. Dan Luu. (2017). Branch Prediction. https://danluu.com/branch-prediction/

9. Majkowski, M. (2021). Branch predictor: How many “if"s are too many? Cloudflare Blog. https://blog.cloudflare.com/branch-predictor/

10. Stack Overflow. (2012). Why is processing a sorted array faster than processing an unsorted array? https://stackoverflow.com/questions/11227809/

11. Agner Fog. (2025). The microarchitecture of Intel, AMD, and VIA CPUs. https://www.agner.org/optimize/microarchitecture.pdf

12. Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.

13. Smith, J. E. (1981). A Study of Branch Prediction Strategies. ISCA 1981.

14. Pan, S. T., So, K., & Rahmeh, J. T. (1992). Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation. ASPLOS 1992.

15. Evers, M., et al. (1998). An Analysis of Correlation and Predictability: What Makes Two-Level Branch Predictors Work. ISCA 1998.

16. Tarjan, D., & Skadron, K. (2004). Revisiting the Two-Level Branch Predictor. MTEAC-4.

17. Championship Branch Prediction. (2006-2011). CBP-1 through CBP-4 Benchmarks. https://jilp.org/cbp/

18. André Seznec. (2011). A New Case for the TAGE Branch Predictor. ACM TACO, 7(2), 1-20.

19. André Seznec. (2006). Analysis of the O-GEometric History Length Branch Predictor. ISCA 2006.

20. Michaud, P. (2005). A PPM-like, Tag-based Branch Predictor. CHPC.

21. Edelson, N., & McFarling, S. (1997). Branch Target Buffer. WRL Research Report 97/8.

22. Skadron, K., Ahuja, P. S., Martonosi, M., & Roth, A. (1999). Improving Virtual Function Call Target Prediction via Dependence Detection. ICS 1999.

23. Driesen, K., & Hölzle, U. (1998). Accurate Indirect Branch Prediction. ISCA 1998.

24. Sprangle, E., & Carmean, D. (2002). Increasing Processor Performance by Implementing Deeper Pipelines. ISCA 2002.

25. Intel Corporation. (2024). Intel 64 and IA-32 Architectures Optimization Reference Manual.

26. AMD. (2024). AMD64 Architecture Programmer’s Manual.