Branch prediction and branchless code

An inner loop sums elements above a threshold on an unsorted array. The same loop on a sorted array of the same data runs 2–3x faster — despite doing the same arithmetic. The sort cost is O(N log N). The branch cost is why it pays back.

How the CPU handles branches

Modern CPUs are deeply pipelined: many instructions are in flight simultaneously. When the pipeline reaches a branch (if, loop boundary, function call), it must decide which instruction to fetch next before the branch condition is computed. The branch predictor makes that guess.

If the guess is right: execution continues without interruption. If the guess is wrong: the pipeline must be flushed — all partially-executed instructions that followed the wrong path are discarded, and the CPU starts over from the correct path. On modern x86, this costs 10–30 cycles. On deep pipelines (Apple M1/M2/M3 with ~10 stages), a miss can waste 40+ instruction slots.

Branch predictor accuracy

Modern hardware predictors — Intel’s TAGE (TAgged GEometric history), AMD’s similar design — achieve 95–99% accuracy on real production code. Their techniques:

• Branch target buffer (BTB): caches recent jump targets.
• Pattern history table (PHT): tracks taken/not-taken history per branch.
• TAGE predictor: combines multiple history lengths, predicting long-period patterns.

For code with regular behaviour (loop bounds, type-stable hot paths), the predictor is essentially free. The cost appears for data-dependent branches — branches whose taken/not-taken outcome depends on the values being processed, not the code structure.

The sorted array trick

Classic example: summing elements above a threshold in an unsorted vs sorted array.

# Unsorted: threshold crossing happens at unpredictable positions
# The branch `if data[i] > THRESHOLD` is taken ~50% of the time, randomly
# Predictor accuracy: ~50% (random), misprediction every other iteration

# Sorted: all elements below threshold first, then all above
# The branch is predictably not-taken, then predictably taken — crossed once
# Predictor accuracy: ~99.5%

The sort costs O(N log N). For large N, the branch misprediction savings easily outweigh the sort. For small N where the sorted data stays in L1, the win is immediate. On a benchmark with 100k elements: sorted version runs 2.5–3x faster despite the sort cost.

Branchless code

For branches that cannot be sorted away (e.g. input data is inherently random), the alternative is to eliminate the branch entirely:

// Branched version: if (x > 0) y = a; else y = b;
// At 50/50 miss rate: 15-30 cycles per iteration wasted

// Branchless version using arithmetic select:
y = (x > 0) * a + (x <= 0) * b;

// Or conditional move (CMOV) — compiler often emits this:
// cmovg rax, rbx  (move rbx into rax if greater)

The branchless version always computes both paths; no branch, no misprediction. The tipping point: if a branch is predictable (95%+), the branched version is faster (skips one path’s compute). If unpredictable (50/50), branchless wins by 2–5x by eliminating the pipeline flush.

Common uses: sort partition, packet classification loops, image-processing inner loops.

Profile-guided optimisation (PGO) for branches

When you cannot change the data or the branch structure, Profile-Guided Optimisation (PGO) lets the compiler help. Build with instrumentation, run a representative workload, recompile with the profile. The compiler uses the branch-taken data to:

• Arrange “taken” paths sequentially (better instruction-cache hit rate).
• Insert __builtin_expect-style hints baked into code layout.
• Make better inlining decisions based on actual call frequency.

PGO wins: 10–30% speedup on real workloads. Used in Chrome, Firefox, Postgres, Linux kernel.