Branch Prediction, Superscalar and Out-of-Order Execution
A pipeline must fetch the next instruction long before a branch is resolved.
Concept
A pipeline must fetch the next instruction long before a branch is resolved. The CPU predicts the outcome and target, fetches and executes speculatively, and on a misprediction discards the wrong work (a penalty of ~15–20 cycles on modern cores).
Always taken / backward taken, forward not taken Repeat the last outcome 2-bit saturating counter
Change the prediction only after two wrong guesses — tolerates the single loop-exit branch Correlating / global history (gshare) Use the pattern of recent branches TAGE, perceptron
Modern CPUs: multiple history lengths, >95% accuracy on typical code BTB (branch target buffer)
Caches the target address of taken branches Return stack buffer Predicts ret targets
Branchless code (conditional moves, masks) avoids mispredictions when a condition is unpredictable.
Superscalar and Out-of-Order Execution Superscalar: fetch, decode and issue several instructions per cycle (modern cores: 4–8 wide), across multiple execution units (several ALUs, load/store units, FP/SIMD units).
Out-of-order (OoO) execution: instructions wait in a scheduler (reservation stations) and execute as soon as their operands are ready, not in program order; a reorder buffer retires them in order so exceptions stay precise.
Register renaming maps the few architectural registers onto many physical registers, removing false WAR/WAW dependencies.
The result: dozens of instructions in flight, hiding cache latencies and exploiting ILP automatically.
Other styles: VLIW (the compiler packs parallel operations into wide instructions — DSPs), SIMD vector units (SSE/AVX, NEON, RISC-V V), and simple in-order cores for low power (microcontrollers, efficiency cores).
Speculation and Security Speculative execution can leave traces in the caches even when the wrong-path work is discarded. The Spectre and Meltdown vulnerabilities (2018) showed that such side effects can leak data across protection boundaries. Mitigations include microcode updates, kernel page-table isolation (KPTI), retpolines, speculation barriers and hardware fixes in newer CPUs — part of why system calls became more expensive (Module 11).
flowchart LR
F["Fetch + branch prediction"] --> D["Decode (x86: to micro-ops)"]
D --> R["Rename registers"]
R --> S["Schedulers / reservation stations"]
S --> E["Execution units: ALU ALU ALU LOAD STORE FP"]
E --> ROB["Reorder buffer: retire in order"]Why It Matters
Unpredictable branches in hot loops can make code several times slower; knowing this guides data layout (sorting, partitioning) and branchless techniques. The OoO engine explains why performance is hard to predict from source code and why measurements beat intuition.
Syntax
if (__builtin_expect(error, 0)) { ... } /* hint: rarely true (GCC/Clang) */
s += x & -(cond); /* branchless select with a mask */Example
25.1 The cost of an unpredictable branch Compiled with if-conversion and vectorization disabled so the compiler keeps a real conditional branch.
25.2 Simulating branch predictors
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { N = 1 << 20, REPEAT = 50 };
static int data[N];
static int cmp(const void *a, const void *b) { return *(const int *)a - *(const int *)b; }
static double ms(struct timespec a, struct timespec b) { return (b.tv_sec - a.tv_sec) * 1e3 + (b.tv_nsec - a.tv_nsec) / 1e6; }
static long sum_big(void)
{
long s = 0;
for (int r = 0; r < REPEAT; r++)
for (int i = 0; i < N; i++)
if (data[i] >= 128) s += data[i]; /* the branch under test */
return s;
}
static long sum_big_branchless(void)
{
long s = 0;
for (int r = 0; r < REPEAT; r++)
for (int i = 0; i < N; i++) {
int mask = -(data[i] >= 128); /* all ones or all zeros: no branch */
s += data[i] & mask;
}
return s;
}
int main(void)
{
srand(1);
for (int i = 0; i < N; i++) data[i] = rand() % 256;
struct timespec t0, t1, t2, t3, t4;
clock_gettime(CLOCK_MONOTONIC, &t0);
long a = sum_big(); /* random data: the branch is unpredictable */
clock_gettime(CLOCK_MONOTONIC, &t1);
long c = sum_big_branchless();
clock
…"""Branch predictors: static 'always taken', 1-bit and 2-bit saturating counters on a loop branch."""
def run(history, predictor):
correct = 0
for taken in history:
if predictor.predict() == taken:
correct += 1
predictor.update(taken)
return correct
class AlwaysTaken:
def predict(self): return True
def update(self, taken): pass
class OneBit:
def __init__(self): self.last = True
def predict(self): return self.last
def update(self, taken): self.last = taken
class TwoBit: # 0,1 = predict not taken; 2,3 = predict taken
def __init__(self): self.c = 3
def predict(self): return self.c >= 2
def update(self, taken): self.c = min(3, self.c + 1) if taken else max(0, self.c - 1)
# inner loop of 4 iterations, executed 5 times: T T T N T T T N ...
loop = ([True] * 3 + [False]) * 5
alternating = [True, False] * 10
for name, hist in [("loop branch T T T N x5", loop), ("alternating T N x10", alternating)]:
print(name)
for p in (AlwaysTaken(), OneBit(), TwoBit()):
c = run(hist, p)
print(f" {type(p).__name__:<12} {c:2d}/{len(hist)} correct ({100 * c / len(hist):.0f}%)")Expected Result
The same additions took almost 5× longer on random data: the branch was taken about half the time with no pattern, so the predictor was wrong very often. After sorting, the branch is not-taken for the first half and taken for the second — almost perfectly predictable. The branchless version doesn't care about the data order at all.
For a loop branch (T T T N repeated), the 2-bit counter mispredicts only the exit; the 1-bit predictor mispredicts twice per loop (the exit and the next entry).
For a strictly alternating branch, simple counters fail; the 1-bit predictor is wrong almost every time. Real CPUs use history-based predictors that learn such patterns.
unsorted data, branch : 194.3 ms
unsorted data, branchless : 41.0 ms
sorted data, branch : 41.1 ms
same sums: yesloop branch T T T N x5
AlwaysTaken 15/20 correct (75%)
OneBit 11/20 correct (55%)
TwoBit 15/20 correct (75%)
alternating T N x10
AlwaysTaken 10/20 correct (50%)
OneBit 1/20 correct (5%)
TwoBit 10/20 correct (50%)Common Mistakes
Micro-optimizing branches that are already predictable.
Assuming instructions execute in program order when reasoning about timing.
Believing speculative execution has no observable effects.
Best Practices
Profile misprediction counters (perf stat -e branch-misses) before rewriting code.
Make data-dependent branches predictable (sort, partition, process by category) or branchless.
Keep security mitigations enabled; they are part of the platform's protection.
Interview Relevance
High (CPU and performance roles): "why is processing a sorted array faster?", "how does branch prediction work?", "2-bit predictor?", "what is out-of-order execution and register renaming?", "superscalar vs pipelined?", "what was Spectre about (conceptually)?".
Practice Questions
Add a gshare predictor (global history XOR address) to the simulator and test it on the alternating pattern.
Measure 25.1 with -O2 without the extra flags and inspect the assembly for cmov.
Explain how register renaming removes a WAR hazard with an example.
Estimate the misprediction penalty from the measured times and the number of branches.
Quick Quiz
Q1. (Multiple choice) Which predictor tolerates the single mispredicted loop exit without changing its prediction? A) Static not-taken B) 1-bit C) 2-bit saturating counter D) None
Answer: C (verified: 15/20 vs 11/20 for 1-bit).
Q2. (Predict the output) Summing values ≥ 128 over random vs sorted data with a real branch — which is faster?
Answer: Sorted, by almost 5× on the test machine (verified).
Q3. (True/False) Out-of-order CPUs retire (commit) instructions out of order.
Answer: False. They execute out of order but retire in program order.
Q4. (Find the bug) "Speculative execution is invisible because wrong-path results are discarded."
Answer: Architectural results are discarded, but microarchitectural state such as the caches can change — the basis of speculative side-channel issues.
Coding Challenge
Write a branchless clamp(int x, int lo, int hi) using comparisons converted to masks, and test it on −5, 50 and 500 with the range 0..255.
#include <stdio.h>
static int clamp(int x, int lo, int hi)
{
int below = -(x < lo), above = -(x > hi); /* all ones if the condition holds */
x = (lo & below) | (x & ~below);
x = (hi & above) | (x & ~above);
return x;
}
int main(void)
{
int tests[] = {-5, 50, 500};
for (int i = 0; i < 3; i++) printf("clamp(%d, 0, 255) = %d\n", tests[i], clamp(tests[i], 0, 255));
return 0;
}