Branch prediction

Deep dive

How it works

In: the instruction stream (branch address plus recent outcome history) · Out: a predicted direction and target per branch · State: global history and predictor tables, BTB, return stack buffer · Cost: correct guess about 0; a miss order of 15-20 cycles.

1. Direction predictor: TAGE-style tables indexed by the branch address hashed with global history of recent outcomes, at several geometric history lengths. Loops with fixed trip counts and repeating patterns are learned. Random data cannot be.
2. BTB (branch target buffer) predicts where a taken branch goes before it is decoded. The return stack buffer predicts ret. A separate indirect predictor handles jmp reg (virtual calls, match jump tables, interpreters).
3. Recovery: on a mispredict the core flushes younger instructions and refetches. The cost is the pipeline refill plus the work lost from a wide out-of-order window.
4. If-conversion: compilers turn simple if into cmov (x86) or csel/cset (AArch64), and loops into SIMD with masks. They also sometimes do the reverse. Only the assembly tells you which you got.

Decision table

Code

Branchy vs branchless filter, and a branchless lower bound. The filter is chosen because LLVM cannot if-convert a conditional store. A conditional sum += x gets turned into a branchless SIMD loop automatically, so it shows no difference.

use std::hint::{black_box, select_unpredictable};
use std::time::Instant;

/// Branchy filter: the CPU predicts `x >= t`. Cheap when the outcome is predictable,
/// about half a misprediction per element when it is random.
fn filter_branchy(v: &[u8], t: u8, out: &mut [u8]) -> usize {
    let mut n = 0;
    for &x in v {
        if x >= t { out[n] = x; n += 1; }
    }
    n
}

/// Branchless filter: always store, advance the cursor by 0 or 1. Same speed for any data.
fn filter_branchless(v: &[u8], t: u8, out: &mut [u8]) -> usize {
    assert!(out.len() >= v.len());
    let mut n = 0;
    for &x in v {
        out[n] = x;               // n <= current index < out.len(): always in bounds
        n += (x >= t) as usize;   // setcc/cset, no jump
    }
    n
}

/// Branchless lower bound: first index with a[i] >= key (a sorted).
/// The loop runs exactly ceil(log2 n) times; the select compiles to a conditional move.
fn lower_bound(a: &[u32], key: u32) -> usize {
    if a.is_empty() { return 0; }
    let mut base = 0usize;
    let mut n = a.len();
    while n > 1 {
        let half = n / 2;
        // Hint: the comparison is a coin flip, so prefer cmov/csel over a branch.
        base = select_unpredictable(a[base + half] < key, base + half, base);
        n -= half;
    }
    base + (a[base] < key) as usize
}

fn time(name: &str, mut f: impl FnMut() -> u64) {
    let t = Instant::now();
    let r = black_box(f());
    println!("{name:28} {:8.2} ms  ({r})", t.elapsed().as_secs_f64() * 1e3);
}

fn main() {
    let mut s = 0x2545_F491_4F6C_DD1Du64;
    let random: Vec<u8> = (0..1 << 24).map(|_| { s ^= s << 13; s ^= s >> 7; s ^= s << 17; s as u8 }).collect();
    let mut sorted = random.clone();
    sorted.sort_unstable();
    let mut out = vec![0u8; random.len()];
    time("branchy, sorted", || filter_branchy(black_box(&sorted), 128, &mut out) as u64);
    time("branchy, random", || filter_branchy(black_box(&random), 128, &mut out) as u64);
    time("branchless, random", || filter_branchless(black_box(&random), 128, &mut out) as u64);
    let mut out2 = vec![0u8; random.len()];
    let k = filter_branchy(&random, 128, &mut out);
    assert_eq!(k, filter_branchless(&random, 128, &mut out2));
    assert_eq!(out[..k], out2[..k]);

    let a: Vec<u32> = (0..1000u32).map(|i| i * 2).collect();
    for key in 0..2002 {
        assert_eq!(lower_bound(&a, key), a.partition_point(|&x| x < key));
    }
    assert_eq!(lower_bound(&[], 5), 0);
    println!("lower_bound ok");
}

On an M4 Pro with 16 M bytes: branchy on sorted data 5.9 ms, branchy on random data 56 ms, branchless on random data 6.1 ms.

Complexity and constants

• Cost model: time ≈ instructions / IPC + mispredicts × order of 15-20 cycles. At 4 instructions per cycle, one mispredict costs as much as order of 60-80 instructions.
• A random 50/50 branch costs about half a penalty per element on average: 7-10 cycles on x86, 3.4 ns per element in the M4 Pro run above. A well-predicted one costs about 0.
• perf stat -e branches,branch-misses (Linux) reports the miss rate. Above order of 1-2 % on a hot loop is worth investigating.

Efficiency

• Cost: a mispredict costs order of 15-20 cycles on x86 (about 4-5 ns at 4 GHz), a correct guess about 0. Measured on an M4 Pro over 16 M random bytes: 56 ms branchy (3.4 ns per element), 5.9 ms on sorted data, 6.1 ms branchless. No memory cost; the bound is pipeline refill latency, not bandwidth.
• Levers:
  • sort or partition the input first — 56 → 5.9 ms (M4 Pro run above) — the same data is filtered repeatedly, so the sort amortizes
  • branchless store and cursor advance — 56 → 6.1 ms (same run) — random 50/50 outcomes, branch guards no expensive work
  • select_unpredictable (cmov) in binary search — one coin flip less per level (Khuong and Morin) — hot-path searches; add prefetch, cmov lengthens the dependency chain
  • block partitioning — fewer mispredicts per comparison (Edelkamp and Weiß) — comparison sorts on random data
• Naive → standard → state of the art:
• naive: data-dependent if on random data · 3.4 ns per element (M4 Pro, above)
• standard: branchless cursor advance · 0.36 ns per element (6.1 ms for 16 M)
• state of the art: SIMD compare plus compress-store · several elements per instruction, not measured here

Implementation notes

• std::hint::select_unpredictable(cond, a, b) (stable in recent Rust) tells LLVM to emit a conditional move instead of a branch. Otherwise LLVM decides by its cost model, and it changes between versions.
• Arithmetic masks: (cond as u64).wrapping_neg() is 0 or all ones. x & mask, min/max, and bool as usize indexing are all branch-free.
• #[cold] on a function marks calls to it unlikely. likely/unlikely hints are not stable Rust. Prefer restructuring over hints.
• Check codegen: cargo rustc --release -- --emit asm and look for cmov/csel vs jcc/b.cond.
• Interpreters and virtual dispatch: a threaded interpreter (one indirect jump per handler) predicts better than one central match jump. Devirtualize hot calls or sort objects by type.
• Branchless code has longer dependency chains. A cmov waits for both inputs. In latency-bound loops (binary search) add software prefetch of both possible next positions.

Pitfalls

• Microbenchmarks with a fixed or sorted input pattern. The predictor learns it and hides the cost that production data would show.
• Benchmarking with small arrays repeatedly: modern predictors memorize thousands of outcomes across iterations.
• Making code branchless when the branch skipped a DRAM access. You traded a rare mispredict for a guaranteed miss.
• Assuming source-level if means a branch in the binary, or that the "branchless" source has no branch. Check the asm.
• Speculation is observable: branch predictors are the root of Spectre. Bounds checks on secret-dependent indexes need lfence or index masking in security-sensitive code.

Variants and alternatives

In production

pdqsort and its successor ipnsort (Rust's sort_unstable) use BlockQuicksort-style branchless partitioning. Branchless binary search is common in search engines and databases. LLVM's if-conversion and the select_unpredictable hint exist for this purpose.

Implementations

Sources

• André Seznec, Pierre Michaud, A case for (partially) TAgged GEometric history length branch prediction, Journal of Instruction-Level Parallelism, 2006. paper
• Daniel A. Jiménez, Calvin Lin, Dynamic Branch Prediction with Perceptrons, HPCA, 2001. paper
• Stefan Edelkamp, Armin Weiß, BlockQuicksort: Avoiding Branch Mispredictions in Quicksort, ESA, 2016. paper · code
• Paul-Virak Khuong, Pat Morin, Array Layouts for Comparison-Based Searching, ACM Journal of Experimental Algorithmics, 2017. paper
• Paul Kocher et al., Spectre Attacks: Exploiting Speculative Execution, IEEE S&P, 2019. paper
• Agner Fog, The microarchitecture of Intel, AMD and VIA CPUs. pdf