Read the original article here.

---

Okay, recruit. Forget what they drone on about in the standard curriculum. The real power comes from understanding the machine's hidden mechanisms. Today, we're cracking open one of the CPU's deepest secrets: Branch Prediction. This isn't just theoretical fluff; mastering this concept allows you to write code that dances through the processor, leaving predictable, optimized footprints instead of stumbling blocks.

Think of it as learning to read the CPU's mind and guide its decisions. They don't focus on this depth in school because it requires thinking like the hardware, not just writing abstract instructions. But we're going deeper.

---

Branch Prediction: Decoding the CPU's Crystal Ball

Modern CPUs are incredibly fast, not just because of high clock speeds, but because they execute instructions in a highly optimized, parallel fashion using pipelines. However, this pipeline approach hits a major roadblock: conditional branches (if, while, for, function calls, etc.).

The Problem: The Stalling Pipeline

Imagine a factory assembly line (the CPU pipeline). Workers (pipeline stages) are specialized: one fetches raw materials (instructions), the next decodes them, others perform operations, and so on. To keep the line moving efficiently, each worker needs materials constantly.

When the CPU encounters a branch instruction (like an if statement), it doesn't know which instructions to fetch next until the if condition is evaluated. Does it go down the 'true' path or the 'false' path? This decision happens relatively late in the pipeline. If the CPU waits for the decision, the assembly line stalls. The fetching and decoding stages sit idle, wasting precious cycles.

Fetch -> Decode -> Execute -> Memory -> Writeback
   ^                           ^
   |                           |
   |---- Pipeline is full ----|
   |
 Branch encountered here (don't know next instruction!)
 Next instruction to fetch depends on Execute result
 Line stalls waiting for Execute

This waiting is a massive performance killer. The deeper the pipeline, the more cycles are wasted on a stall.

The Solution: Guessing the Future

To avoid stalling, the CPU doesn't wait. It guesses which way the branch will go and starts fetching and executing instructions down the predicted path. This is Branch Prediction.

Branch Prediction: A technique used by modern processors to guess the outcome (taken or not taken) of a conditional branch and the target address of a branch before the outcome is known. This allows the pipeline to continue fetching and executing instructions speculatively down the predicted path.

If the guess is correct, the pipeline continues smoothly, having saved many cycles. If the guess is wrong (a misprediction), the CPU must discard all the work done down the wrong path, reset the pipeline, and start fetching from the correct location. This rollback incurs a significant performance penalty.

Why Predict? The Performance Edge

The performance gain from correct branch prediction is substantial. In modern code, branches are frequent (loops, conditionals, function calls). A high prediction accuracy keeps the pipeline full. Conversely, poor prediction accuracy leads to frequent stalls, crippling performance. The cost of a misprediction can range from 10 to over 20 CPU cycles or more, depending on the pipeline depth and architecture. Saving dozens of cycles per branch adds up rapidly in performance-critical code. Understanding and influencing this is your first step into low-level optimization magic.

Types of Branch Prediction: From Simple to Sophisticated

Processors use various techniques, ranging from simple heuristics to complex algorithms, to make these guesses. The goal is always higher accuracy with minimal overhead.

1. Static Prediction

This is the simplest form, relying on fixed rules based on the instruction type or direction before the code even runs. The CPU makes the same guess every time it sees a particular branch instruction.

• Heuristics:

  • Assume Not Taken: The default for many architectures, especially for forward branches (if (condition) { ... } where {...} is a small block). The logic is that code blocks following a conditional are executed less frequently than the straight-line code.
  • Assume Taken for Backward Branches: Branches that go back in code (like the end of a for or while loop) are usually taken most of the time (the loop continues). Predicting 'taken' for backward branches is a good heuristic for loops.
  • Opcode-Based: Some architectures might predict based on the specific branch instruction opcode.

• Context/Use Cases: This is useful as a fallback when dynamic prediction data isn't available (e.g., on the first encounter of a branch) or in very simple processors. Compilers can sometimes provide hints to the processor (using __builtin_expect in GCC/Clang) which the CPU might use for static prediction if dynamic prediction is not available or overridden.

2. Dynamic Prediction

This is where modern performance lives. Dynamic predictors use the runtime history of branches to make predictions. They adapt to the program's actual behavior.

• Core Idea: Keep track of whether a branch was taken or not taken in the past, and use that history to predict the future. This history is stored in structures like the Branch History Table (BHT) or Pattern History Table (PHT).

• Basic Predictor Designs:

  • One-Bit Predictor: For each branch, store a single bit representing its last outcome (0 for Not Taken, 1 for Taken).

    • Prediction: Predict the outcome based on the last result.
    • Update: If the prediction was wrong, flip the bit.
    • Limitation: Fails badly for branches that alternate outcomes regularly (e.g., a loop that runs 10 times: T T T T T T T T T N). It will mispredict the last iteration (predicting T instead of N) and then mispredict the first iteration of the next time the branch is hit (predicting N instead of T). Two mispredictions for a simple alternating pattern.

  • Two-Bit Predictor (Saturated Counter): This is a significant improvement. For each branch, use a two-bit counter (states: 00, 01, 10, 11). Think of these as representing "Strongly Not Taken" (00), "Weakly Not Taken" (01), "Weakly Taken" (10), and "Strongly Taken" (11).

    • Prediction: Predict Taken if the counter is 10 or 11. Predict Not Taken if 00 or 01.
    • Update: Increment the counter on a Taken outcome (maxing at 11). Decrement on a Not Taken outcome (minima at 00).
    • Benefit: The counter must be wrong twice before the prediction flips. This handles alternating patterns and transient changes much better than a one-bit predictor. A loop exit (TT...TN) will only cause one misprediction on the final 'N', as the state will likely go from Strongly Taken (11) to Weakly Taken (10), still predicting Taken if the loop is immediately re-entered.

• Advanced Dynamic Predictors: Modern CPUs use much more sophisticated dynamic predictors, often combining different techniques:

  • Local Predictor: Each branch instruction has its own history (e.g., a dedicated two-bit counter or a small history buffer). Good for branches whose outcome depends only on their own past behavior.
  • Global Predictor: Uses a shared history of the outcomes of the most recent branches executed, regardless of which branch they were. This is good at capturing correlations between different branches.
  • Gshare Predictor: A common and effective design. It combines bits from the branch's address (to identify the branch) with bits from the global history register (to capture recent outcomes) to index into a pattern history table. This captures both local and global patterns effectively.
  • Tournament Predictor: Uses multiple predictor types (e.g., a local and a global predictor) and a meta-predictor that learns which predictor is best for a given branch.
  • Perceptron/Neural Predictors: More complex designs that use machine learning techniques (specifically, linear threshold units or perceptrons) to combine global history bits with weights, learning complex, non-linear patterns. These can achieve very high accuracy but require more hardware resources.

Branch Target Prediction

For unconditional branches, direct calls, or indirect branches (like function pointers, virtual methods, or switch statements), the CPU also needs to guess the target address of the jump or call. This is handled by the Branch Target Buffer (BTB).

Branch Target Buffer (BTB): A cache in the CPU that stores the target addresses of recently executed branches and function calls. When a branch or call instruction is fetched, the CPU checks the BTB to predict the target address and starts fetching instructions from there speculatively.

If a branch is predicted taken, the BTB is checked to find the most likely destination address. If the target is found and the prediction is correct, fetching continues seamlessly. If the target is not in the BTB or the prediction is wrong, the pipeline stalls while the correct target is computed and fetched. Indirect branches are particularly challenging for the BTB as their target can vary widely.

Handling Mispredictions: The Cost of Being Wrong

When the execution unit determines that a branch prediction was incorrect, the CPU must:

1. Detect the Misprediction: This happens late in the pipeline when the branch condition is finally evaluated.
2. Flush the Pipeline: All instructions that were fetched and speculatively executed after the mispredicted branch down the wrong path must be discarded. Their results are cancelled.
3. Fetch from the Correct Path: The pipeline must be redirected to fetch instructions from the actual target address of the branch.

This process takes many cycles, effectively wiping out the benefit of pipelining for that duration. This is the penalty you pay for a wrong guess.

The "Forbidden" Angle: Writing Predictor-Friendly Code

Here's where you apply this knowledge to gain an edge. While compilers do a decent job, understanding branch prediction allows you to structure your code to help the predictor, especially the dynamic one. This isn't always intuitive from a high-level programming perspective, and it's rarely taught explicitly in beginner courses.

The goal is to make your branches as predictable as possible.

1. Order if/else Based on Likelihood: If you know one path of an if/else is much more likely than the other, put the more likely path first. Compilers might reorder based on profiling, but explicit ordering helps, especially for static prediction or when profile data is unavailable.

   // Potentially less predictor friendly if 'error_condition' is rare
   if (error_condition) {
       handle_error();
   } else {
       // Normal, frequent path
       process_data();
   }
   
   // More predictor friendly if 'error_condition' is rare
   if (!error_condition) {
       // Normal, frequent path
       process_data();
   } else {
       handle_error();
   }
   

   Reasoning: The predictor will likely learn that the if condition is often false and predict "not taken," flowing directly into process_data(). If error_condition was first, it would often predict "taken" (leading to handle_error()), then mispredict when it's false, causing a stall.

2. Loops and Backward Branches: The prediction "assume taken for backward branches" is a good heuristic. Loops structured conventionally (for (int i = 0; i < N; ++i)) naturally have the loop-continuation check as a backward branch, which predictors handle well (until the last iteration). Avoid unconventional loop structures that might confuse this.

3. Be Mindful of Unpredictable Branches:

   • Switch Statements on Variable Data: switch(value) where value can take many outcomes without a predictable pattern is hard to predict the target. This challenges the BTB.
   • Function Pointers and Virtual Methods: ptr->method() or func_ptr() where the actual function called varies unpredictably is the ultimate challenge for the BTB. Each call might jump to a different address, making target prediction difficult. Code relying heavily on dynamic polymorphism in hot loops can suffer here.
   • Conditional Logic Based on Unpredictable External Input: Branches based on things like network packet data, random numbers, or user input often lack predictable patterns for the CPU to learn.

4. Branchless Programming: The most extreme technique is to eliminate branches entirely using conditional move instructions (if available) or bitwise logic. This bypasses the need for prediction.

   // Branchful max
   int max;
   if (a > b) {
       max = a;
   } else {
       max = b;
   }
   
   // Branchless max using conditional operator (often compiles to conditional move)
   int max = (a > b) ? a : b;
   
   // Branchless max using bitwise operations (more complex, less readable but possible)
   int max = b + ((a - b) & ((a - b) >> (sizeof(int) * CHAR_BIT - 1))); // Example for int, simplified
   

   Context: While not always more performant (the CPU might still have to compute both sides of a conditional move or execute more instructions), branchless code avoids misprediction penalties entirely. This is powerful for short, frequently executed pieces of code with unpredictable conditions.

Advanced Implications: Speculation and Side Channels

Branch prediction is tightly coupled with speculative execution.

Speculative Execution: The CPU executes instructions along a predicted path before it knows if that path is the correct one. The results are held in temporary buffers and only committed (made permanent) if the prediction was correct. If incorrect, the speculative results are discarded.

While powerful for performance, the temporary execution of instructions on potentially wrong paths (based on branch predictions) can leave observable side effects in the CPU's state (like cache lines being loaded or evicted). This is the basis for certain types of security vulnerabilities like Spectre and Meltdown, which exploit these side channels to infer data that the program shouldn't have access to. Understanding branch prediction and speculative execution isn't just about speed; it's increasingly relevant to security.

Conclusion

Branch prediction is a fundamental technique modern CPUs use to overcome the performance bottleneck of control flow changes in pipelined execution. It's a complex, dynamic process hidden beneath your source code.

By understanding how processors guess branch outcomes and targets, and the significant penalty of mispredictions, you gain insight into why certain code structures perform better than others at a deep hardware level. Writing predictor-friendly code isn't always the most intuitive or "clean" from a purely abstract standpoint, but in performance-critical sections, guiding the CPU's crystal ball effectively is a vital, often overlooked, "forbidden" technique that separates those who write code from those who truly understand and control the machine. Now you know the secret. Use it wisely.