The Gist: What Is Branch Prediction?
Imagine your code is a railroad track. Most of the time, the train (your CPU) is just laying down track straight ahead, executing one instruction after another. This is called pipelining, and it’s incredibly fast. But then it hits a fork in the tracks—an
`if` statement, a `for` loop, a `switch` case. This is a branch. The CPU now has a choice: go left or go right? Without knowing the result of the condition, the train would have to stop, wait for the calculation, and then proceed. These stops are called pipeline stalls, and they kill performance. Branch prediction is the CPU’s superpower. Instead of stopping, it makes an educated guess. It says, “Last time we were here, we went left, so let’s start laying track that way.” If the guess is right, the train never slows down. If it's wrong, the CPU has to tear up the speculative work and go back to the fork, a process called a pipeline flush. This is expensive, wasting precious cycles.
The Part Everyone Knows: Simple `if/else` Patterns
Most tutorials on branch prediction stop here, focusing on the most common type of branch: the conditional direct branch. Think of a simple `if` statement inside a loop that checks if a number is positive. If the data is sorted, the predictor will quickly learn the pattern (e.g., all positive, then all negative) and achieve near-perfect accuracy. Modern predictors are incredibly good at this, tracking the history of recent branches to make their guesses. They learn that a loop's conditional branch is almost always taken until the very last iteration. This is the level of understanding most of us have: write predictable `if` statements and the CPU will be happy. But this only covers part of the story.
The Hidden Detail: Direct vs. Indirect Branches
Here’s the detail many self-taught developers miss: not all branches are simple forks in the road. There’s a crucial distinction between direct and indirect branches. A direct branch has a fixed destination. An `if/else` statement is a direct branch; it can either continue to the next line or jump to a specific, hardcoded label in the code. The predictor only needs to guess “taken” or “not taken.” An indirect branch, however, has a destination that is calculated at runtime, typically by reading an address from a register or memory. The most common sources of indirect branches in high-level languages are things like virtual function calls in object-oriented programming (polymorphism), function pointers, and some `switch` statements. For these, the CPU doesn’t just have to guess if the branch is taken; it has to guess where it’s going. This is a much harder problem. A single virtual method call site could potentially jump to dozens of different function implementations depending on the object's runtime type. The predictor can no longer just guess left or right; it has to guess a full-blown address from a list of many possibilities.
Why This Detail Wrecks Performance
While modern CPUs have specialized hardware to predict indirect branches, their accuracy is significantly lower than for direct branches. Studies have shown that while indirect branches may be a small percentage of total branches in a program, they can be responsible for a huge majority of mispredictions. A misprediction rate of 3% might be great for direct branches, but it's not uncommon for indirect branches to have misprediction rates of 25% or higher. What does this mean for your code? It means that a hot loop processing a `std::vector` of pointers to a base class and calling a virtual method on each one can be a performance minefield. Even if the logic inside each method is simple, the constant mispredictions from the indirect jumps can cripple your CPU's pipeline. The performance cost isn't in your algorithm; it's in the unpredictable control flow that prevents the CPU from doing its job efficiently. This is the kind of problem that doesn't show up in a standard algorithmic complexity analysis but can have a massive real-world impact.
