Branch Prediction

Sort an array before summing only the elements above a threshold, and the sum can run noticeably faster than doing the exact same comparisons on the unsorted array — despite touching the same numbers, doing the same number of comparisons, and producing the same answer. Nothing about the arithmetic changed. What changed is how predictable the pattern of true/false answers to that comparison became, and modern CPUs are built to exploit predictability in a very specific way: by guessing the future and starting work on the guess before they're sure.

The idea: an assembly line that can't afford to wait

A modern CPU doesn't execute one instruction, finish it completely, and then start the next — it works like an assembly line (a pipeline) with many stages, where several instructions are in different stages of being processed simultaneously, for throughput. The problem is an if statement: the CPU can't know which of the two possible next instructions to feed into the pipeline until the comparison itself has actually been computed, and computing it can take several pipeline stages. Stalling the entire assembly line every time, waiting for each comparison to resolve before deciding what comes next, would waste a huge fraction of the CPU's potential speed.

The CPU's answer is to guess. A branch predictor — a small piece of hardware that remembers how recent branches at this location resolved — makes an educated guess about which way the upcoming if will go, and the pipeline immediately starts executing instructions down that guessed path, before the comparison has actually finished. If the guess turns out right, the CPU has usefully gotten ahead — free speed. If the guess is wrong (a misprediction), every instruction the pipeline started on the wrong path has to be thrown away and the pipeline has to refill from the correct path — a pipeline flush, typically costing 10-20 cycles on modern x86 CPUs, which is a meaningful chunk of time when a single simple instruction might otherwise take under 1 cycle.

Worked example: sorted versus unsorted, traced

Suppose you're summing only the elements of an array above 50, out of values uniformly distributed 0-100.

import numpy as np, time

n = 10_000_000
data = np.random.randint(0, 100, n).astype(np.int64)
sorted_data = np.sort(data)

def branchy_sum(arr):
    total = 0
    for x in arr:
        if x > 50:          # unpredictable on random data, predictable on sorted
            total += x
    return total

On the unsorted array, whether x > 50 is roughly a coin flip on every iteration, with no pattern the predictor can learn — its accuracy on this data degrades toward chance, and every misprediction costs a pipeline flush. On the sorted array, once the running position crosses 50, every remaining comparison is True, and every comparison before that point is False — two enormous, easily-learned runs. The predictor, after seeing the same outcome a handful of times in a row, predicts "same as last time" with very high accuracy, and mispredictions collapse to essentially just the one moment the data crosses 50. In compiled, cache-resident code operating close to CPU speed (this Python loop is dominated by interpreter overhead and won't show the raw effect cleanly — see Vectorization vs Loops — but the identical C++ loop routinely shows it directly), this single change — sorting first — commonly produces a 2-6x speedup on the summation loop alone, purely from misprediction count dropping.

// The same comparison, same data, same total work either way --
// only the ORDER of true/false outcomes differs between the two calls.
long branchy_sum(const std::vector<int>& v) {
    long total = 0;
    for (int x : v)
        if (x > 50) total += x;     // unpredictable on shuffled v, predictable on sorted v
    return total;
}

A concrete fix: replace the branch with arithmetic

When a branch is genuinely unpredictable and sits on a hot path, one standard trick is to remove the branch entirely and compute both outcomes, selecting the right one with arithmetic instead of a jump — called a branchless rewrite.

// Branchy: CPU must guess which way this goes, every iteration
if (x > 50) total += x;

// Branchless: no guess needed -- (x > 50) evaluates to 0 or 1, no jump
total += x * (x > 50);

This does strictly more arithmetic (a multiply, every time, even when the answer is 0) but removes the possibility of a misprediction penalty entirely — a clear example of trading guaranteed small extra work for the elimination of a rare, expensive worst case, the same tradeoff logic that shows up throughout low-latency system design.

misprediction wrong-path work discarded ~10-20 cycle flush + refill

Where this shows up

In a quant-dev interview, "why is summing a sorted array faster than an unsorted one" is a well-known question specifically because the surprising answer (branch prediction, not caching, though caching can also play a role) reveals whether a candidate understands CPU microarchitecture beyond algorithm-level thinking. In production, this matters most in exactly the systems where every cycle on the hot path is counted: an order-book update loop, a risk-check gate that runs on every order, or a matching engine's core logic (How a Matching Engine Works) will often be written to minimize unpredictable branches — sorting inputs when possible, replacing if chains with lookup tables or branchless arithmetic, and structuring conditionals so the common case is the one the predictor learns to expect.