This question tests whether you can think in cycles per instruction instead of lines of code. The interviewer wants the pipeline story: modern CPUs don't wait to find out which branch was taken — they guess, and the guess costs nothing until it's wrong.
The mental model. A modern CPU is a deep pipeline: fetch, decode, rename, execute, retire — 10 to 20+ stages. The pipeline's job is to keep the execution units fed. A branch is a fork in the instruction stream, and the comparison that decides it is only known deep in the pipeline. If the CPU waited, every branch would stall for the full branch-to-execute latency. So a branch predictor guesses the outcome, and the fetch unit speculatively feeds instructions from the predicted path.
When the guess is right, the branch costs ~0: the instructions were already in flight and execute normally. When it's wrong, the CPU must flush every instruction fetched and partially executed down the wrong path, rewind the register rename state, and restart fetch at the correct target. That's the misprediction penalty: typically 15–40 cycles on modern cores, multiplied by however many speculative instructions were in the pipeline. A mispredict is not "a slow branch" — it's the pipeline emptying.
Why some branches are predictable and others aren't:
- Loops (
for i in 1..n) — the predictor sees the pattern: taken n-1 times, not taken once. Two-bit saturating counters and loop predictors nail this. - Sorted data —
if (arr[i] > threshold)over sorted input has a stable pattern the predictor learns. - Random or adversarial data — every branch is a coin flip; the predictor is right 50% of the time, so you pay a mispredict per branch. This is the classic "sorted vs unsorted array" 10x demo: the code is identical; the prediction rate isn't.
How you exploit this in real code:
- Sort before filtering when the branch is data-dependent and you control input order.
- Replace branches with lookups or arithmetic: a table
t[x & 3]is data, not control flow — no branch to mispredict. Conditional moves (cmov) trade a serialized dependency for no mispredict cost. - Reorganize the hot path: common case first, cold paths split out and annotated (
__builtin_expect), so the predictor and the I-cache agree.
Edge cases worth naming: virtual calls are indirect branches predicted by a separate branch target buffer; exceptions are the most mispredictable control flow (exceptional → flush); and microarchitectures differ — Apple silicon and Zen 4 predict much better, but the shape of the cost is the same.