Part 4 · Where the fictions break
Branch prediction
A predicted branch costs nothing. A mispredicted one costs a pipeline. Which is why sorting your data can make the same loop several times faster.
What this lesson is trying to break (3)
- Branches are expensive.
- Branchless code is faster.
- The cost of an if depends on what is inside it.
A branch is a problem for a pipelined machine: it needs to know which instructions to fetch next, and the condition may not be computed yet. Stalling until it is would cost the full pipeline depth on every branch.
So it guesses, and executes the guess immediately. Modern predictors are extremely good — well above 95% on typical code — using history tables that learn per-branch patterns.
The two costs
Predicted correctly: approximately zero. The speculative work was the right work, so it retires normally. The branch cost nothing.
Predicted wrongly: roughly 15–20 cycles. Everything down the wrong path must be discarded and the pipeline refilled — the penalty is essentially the pipeline depth.
That asymmetry is the whole subject. A branch is not “expensive” or “cheap”; it is free or catastrophic depending on whether it is predictable, and predictability is a property of your data, not your code.
long sum_big(const int *a, int n) {
long s = 0;
for (int i = 0; i < n; i++)
if (a[i] > 128) s += a[i];
return s;
}Called twice on the same million random values in 0–255 — once unsorted, once sorted. The result is identical either way. Is the runtime?
The sorted version can be several times faster. This is the most famous performance question on Stack Overflow, and the reason is entirely branch prediction.
Unsorted, a[i] > 128 is essentially a coin flip. The predictor cannot learn a
coin flip, so it mispredicts about half the time — around 500,000 mispredicts at
~15 cycles each.
Sorted, the condition is false for the first half of the array and true for the second. The predictor learns “not taken” immediately, is wrong exactly once at the transition, then learns “taken”. Two mispredicts total.
Same instructions, same memory traffic, same answer, same instruction count. Several times the runtime, and the only difference is the order of the input data.
One important caveat, and it is why you should try this yourself rather than
believe it: modern compilers often defeat the demonstration by turning this into
a branchless conditional add or vectorising it with a mask. If you compile
this and see cmov or xmm registers, the branch is gone and sorting will not
matter. That does not weaken the lesson — it is the lesson, because the compiler
made exactly the trade this course is about.
So when is branchless better?
Now 1.4’s trade-off can be stated properly.
Varies: only the predictability of the condition
| Condition | Branch | cmov | Winner |
|---|---|---|---|
| Predictable (>95%) | ~0 cycles | both sides, every time, plus a data dependency | Branch |
| Coin flip | ~7 cycles average (half of ~15) | ~1–2 cycles, always | cmov |
| Predictable but expensive body | ~0, and skips the work | must evaluate both bodies | Branch, decisively |
A branch can skip work; cmov cannot. So for an unpredictable condition guarding cheap work, cmov wins; for anything guarding expensive work, the branch wins even when it mispredicts.
Two consequences worth having:
“Branchless is faster” is false as a general claim. It is true for unpredictable conditions over cheap alternatives, which is a real and common case, but it is a narrow one.
The compiler is guessing. It has no idea what your data looks like, so it
applies heuristics. If you know a branch is unpredictable, or that it is taken 99%
of the time, you can tell it — with [[likely]]/[[unlikely]] in C++,
likely()/unlikely() idioms in C, or #[cold] in Rust. Better still,
profile-guided optimisation measures it and removes the guessing entirely.
PGO is under-used and frequently worth a several-percent win for nothing but build
complexity.
Indirect branches are worse
A conditional branch has two targets, so a coin flip still gets 50%. An
indirect branch — a virtual call, a function pointer, a big switch through a
jump table — can go anywhere.
Predictors handle these too, and handle them well when a call site is monomorphic in practice (always the same target). They do badly when it is genuinely polymorphic.
This is the concrete cost behind dyn Trait and virtual dispatch, and it is a
better account than “one extra indirection”. The pointer chase is trivial; the
risk is a mispredicted indirect branch plus the lost inlining. Which is also
why a dyn call in a loop that always hits the same implementation is nearly free,
while one that alternates between three is not — a distinction worth being able to
make when someone asks whether dyn is “slow”.
A colleague reports that adding a sort() before their processing loop made the
whole thing faster, including the sort. They think they have found a bug in their
benchmark.
Explain what is actually happening. Then give the situation in which their result would not hold, so they know when not to generalise it.
What you should now be able to say
- A predicted branch is nearly free; a mispredict costs the pipeline depth, roughly 15–20 cycles.
- Predictability is a property of your data, not your code — hence the sorted array result.
- Branchless is not generally better:
cmovpays for both sides always and cannot skip expensive work. - The compiler is guessing;
likely/unlikelyand especially PGO let it know. - Indirect branches are the real cost of virtual dispatch — mispredict plus lost inlining, not the extra load.
Next: 4.4 — The memory hierarchy.