Branch Prediction Secrets: 6 Proven CPU Speed Wins Now

Your loop does almost nothing — one comparison, one addition. Yet it runs 4x slower on shuffled data than sorted data. Same instructions, same count, wildly different speed.

The CPU isn't executing your code line by line. It predicts, prefetches, and caches ahead — and your data's shape decides whether those guesses pay off.

You'll learn how branch prediction and cache lines really work, the sorted-array demo that proves it, and the measurement discipline that separates real wins from folklore.

How Branch Prediction Feeds the Pipeline (and Starves It)

Your CPU doesn't run one instruction at a time — it keeps 14-19 stages busy simultaneously, with dozens of instructions in flight. At every if, it must guess which way to go before the condition is computed, or the whole pipeline starves.

Guess right (the common case for loops and rare error checks) and the cost is zero — execution flows uninterrupted. Guess wrong and the CPU flushes everything speculative: ~15-20 cycles (~5ns) of work discarded. One mispredict is nothing; 5 million per second is a bottleneck.

Predictors aren't coin flips — they're two-level history tables that learn patterns, even alternating ones. Loops, correlated branches, mostly-one-way checks: all nearly free. The killer is data-dependent 50/50 chaos no table can learn.

The Sorted-vs-Shuffled Demo That Converts Skeptics

The classic demo fits in 30 lines: loop 10M integers, count those above a threshold. On sorted data it flies; shuffled, it crawls — 3-4x slower with identical instructions. The only difference is predictability.

Sorted, the branch is 'no,no,no...yes,yes,yes' — the predictor learns the single transition and naps. Shuffled, it's coin-flip noise — the predictor guesses wrong half the time and the pipeline flushes constantly.

Run it yourself with the benchmark below. The numbers convert skeptics faster than any diagram: same code, same data, different order, 4x speed gap. Data shape is performance.

import java.util.*;

public class BranchDemo {
  static long scan(int[] a, int t) {
    long c = 0;
    for (int x : a) if (x >= t) c += x; // one branch, 10M trips
    return c;
  }
  public static void main(String[] args) {
    Random r = new Random(42);
    int[] a = r.ints(10_000_000, 0, 256).toArray();
    int[] sorted = a.clone(); Arrays.sort(sorted);
    for (int i = 0; i < 5; i++) { scan(a, 128); scan(sorted, 128); } // warmup
    long t0 = System.nanoTime(); scan(a, 128);      long shuffled = System.nanoTime() - t0;
    t0 = System.nanoTime(); scan(sorted, 128);      long ordered = System.nanoTime() - t0;
    System.out.printf("shuffled: %d ms, sorted: %d ms, ratio: %.1fx%n",
      shuffled / 1_000_000, ordered / 1_000_000, (double) shuffled / ordered);
  }
}

Cache Lines, False Sharing, and the 100ns Toll

Below the predictor sit the caches: L1 (~1ns, 32-64KB), L2 (~4ns), L3 (~15ns), then RAM (~100ns). Data moves in 64-byte lines — using one byte fetches 63 neighbors. Sequential scans consume whole lines (fast); strided jumps waste 7/8 of every fetch.

False sharing is the multicore trap: two threads writing different fields on the same line force the coherence protocol to shuttle it between cores at ~100ns per transfer. Your 'independent' counters serialize through the memory system.

And the hierarchy rule: one RAM miss (~100ns) costs as much as twenty mispredicts (~5ns). Layout fixes usually outrank branch fixes — profile cache-misses before celebrating a branchless rewrite.

Branchless Selects, Lookup Tables, and Partition-First

When the branch is genuinely unpredictable and both sides are cheap, go branchless: replace if (c) x = a; else x = b; with arithmetic or cmov-style selects the CPU executes without guessing. The cost is always doing both sides' work — worth it only when guessing loses more.

Lookup tables trade branches for memory: precompute outcomes for small input domains and index instead of deciding. The table must stay cache-resident or you've swapped a 5ns mispredict for a 100ns miss — a 20x loss disguised as cleverness.

Sort or partition first when scans repeat: one O(n) pass over static data pays for itself across thousands of predictable scans. The trading fix was exactly this — partition by type once, scan predictably forever.

public class Branchless {
  // branchy: mispredicts ~50% on random data
  static int maxBranchy(int a, int b) { return a > b ? a : b; }
  // branchless: arithmetic select, no guess needed
  static int maxSelect(int a, int b) {
    int d = a - b;
    int mask = d >> 31; // -1 if a<b else 0
    return a - (d & mask);
  }
  public static void main(String[] x) {
    System.out.println(maxBranchy(3, 7) + " " + maxSelect(3, 7)); // 7 7
  }
}

Layout Wins: Tiling, SoA, and JIT Cooperation

Big arrays need tiling: process in cache-sized blocks so each line is reused while hot instead of streamed once and evicted. Hot-field/cold-field splits (Struct-of-Arrays) stop cold bytes from evicting hot lines. Loop interchange, padding, and alignment finish the job.

In Java specifically: prefer arrays of primitives over boxed collections in hot loops, keep hot methods monomorphic so the JIT inlines aggressively, and confirm compilation with -XX:+PrintCompilation — interpreted timings lie 10x about hardware effects.

Each transform has a cost (complexity, footprint, refactor risk). Apply them where counters prove the bottleneck, nowhere else.

The Measurement Discipline That Beats Folklore

The discipline in five steps. Profile with hardware counters (perf stat or async-profiler: branch-misses, cache-misses) on production-shaped data. Identify the dominant toll — 100ns misses outrank 5ns mispredicts, fix bigger first. Apply one transform. Re-measure with JMH (warmed, forked). Keep it only if the counters and the clock agree.

What not to do: optimize cold code, benchmark without warmup, test on sorted fixtures, or merge branchless rewrites without numbers. Folklore optimizations have negative value — they cost readability and sometimes speed.

The teams that win treat the CPU as a measurement-driven partner: predictable data, friendly layout, verified gains. Everything else is superstition with a compiler.

# hardware counters on the hot loop (Linux)
perf stat -e branch-misses,cache-misses,L1-dcemissloads java -jar target/bench.jar
# async-profiler flame graph with cache-miss events
asprof -e cache-misses -d 30 -f profile.html 
# rule: keep the change only if counters AND wall-clock both improve