Mysterious branch misprediction

TL;DR: CPUs guess the outcome of branches to keep their pipeline full. When the guess is wrong, the pipeline flushes and you pay a 10–20 cycle penalty. A sorted array with a conditional filter is the classic case where the predictor fails — and on older Intel CPUs it can be 2–3x slower than an unsorted one. On modern Apple Silicon the predictor is smart enough that the effect has nearly vanished.

Branch prediction is one of the crucial parts of a CPU that maximizes pipeline performance. At the software layer, we don’t have any direct control over the branch predictor, but does that mean we can ignore it when writing programs? The short answer is no — and in this post I’ll explain why, with examples in Go.

This post is heavily inspired by the canonical Stack Overflow question “Why is processing a sorted array faster than processing an unsorted array?”, which itself goes back to a 2012 discussion on Andrew Binstock’s blog with Vladimir Yaroslavskiy. If you want the original benchmarks and the deep hardware-level explanation, start there.

What is a branch predictor and why do we need it?

According to Wikipedia, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–else structure) will go before this is known for certain. But why guess when we can just execute the branch and get the definite answer? To answer that, we need to know how a CPU executes instructions.

In modern CPUs every instruction is executed using a technique called pipelining. Pipelining helps us achieve instruction-level parallelism by keeping every part of the processor busy with some instruction. Incoming instructions are divided into a series of sequential steps performed by different processor units, with different parts of different instructions processed in parallel.

Let’s imagine you want to do laundry, and the process consists of three steps:

• Washing — 30 minutes
• Drying — 40 minutes
• Ironing — 20 minutes

Doing laundry for one load takes 90 minutes. What about multiple loads? If you have 4 loads and you start a new load only when the previous one finishes, the total is 4 × 90 = 360 minutes, or 6 hours.

Sequential laundry: one load at a time, most of the equipment sits idle.

That’s wasteful. When you’re drying one load, the washing machine and the iron sit unused, and the same is true for every step. A better solution is to put a new load on the washing machine while you’re drying washed ones, and to start ironing as soon as the first load is dry. That way you minimize the total time. Now all four loads take 3 hours and 30 minutes.

Pipelined laundry: each stage is busy with a different load at the same time.

Pipelining steps vary between CPU architectures, but for the rest of this article I’ll use the classic 5-stage RISC pipeline:

• Fetch
• Decode
• Execute
• Memory
• Write Back

So where does the branch come in?

Here’s the problem: the pipeline doesn’t wait for one instruction to finish before starting the next. While instruction A is being decoded, instruction B is already being fetched. But what happens when instruction A is a branch like if arr[i] <= 128? The CPU doesn’t know which path to fetch next until A reaches the Execute stage. It has two choices:

1. Wait — stall the pipeline and waste cycles doing nothing.
2. Guess — predict the branch direction and keep the pipeline full.

Waiting is expensive. With a 5-stage pipeline, stalling for every branch throws away a huge amount of throughput. So modern CPUs guess. They use a branch predictor — a small piece of hardware that keeps a history of past branches and uses it to predict the future.

If the prediction is correct, there’s no penalty. If the prediction is wrong, the CPU has to flush the entire pipeline, throw away all the speculatively executed instructions, and start over from the correct branch target. This is called a pipeline flush or misprediction penalty, and it typically costs 10–20 cycles on modern CPUs.

Misprediction chaos

Now let’s look at a Go program that demonstrates this problem:

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

func main() {
	rng := rand.New(rand.NewSource(time.Now().UnixNano()))

	const N = 32768
	arr := make([]int, N)
	for i := range arr {
		arr[i] = rng.Intn(256)
	}

	sort.Ints(arr)

	sum := 0
	for m := 0; m < 100_000; m++ {
		for _, v := range arr {
			if v <= 128 {
				sum += v
			}
		}
	}

	fmt.Println(sum)
}

At first glance this looks innocent. We generate 32768 random numbers between 0 and 255, sort them, then sum all values ≤ 128. Simple.

But look at what sorting does to the data. All values ≤ 128 are grouped at the beginning, and all values > 128 are grouped at the end. The array looks something like this:

[0, 1, 2, ..., 127, 128, | 129, 130, ..., 254, 255]
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       always true         |      always false

When the inner loop starts iterating, the branch if v <= 128 is true for roughly the first half of the array, then false for the second half. The branch predictor sees a long streak of true outcomes, learns the pattern, and keeps predicting true. Then, right in the middle of the array, the branch suddenly flips to false — and the predictor is caught off guard.

The predictor doesn’t understand the data. It tracks patterns like “the last N times this branch was taken, so it will probably be taken again.” A sorted array is the classic example because it creates a sharp transition. The streaks themselves are predictable, but the single point where the condition flips from true to false catches the predictor off guard, and it takes several iterations to relearn the new pattern.

This kind of unpredictable conditional branch is the most common source of mispredictions in real-world code.

Does it actually matter?

Here’s the uncomfortable truth: it depends on your CPU.

Let’s benchmark sorted vs unsorted. The test is simple — iterate over 1M elements and sum values >= 128:

const N = 1 << 20 // ~1 million elements

func sumOverThreshold(data []int, threshold int) int {
	sum := 0
	for _, v := range data {
		if v >= threshold {
			sum += v
		}
	}
	return sum
}

On an Apple M3 Pro (2023+), sorted and unsorted produce nearly identical results in practice:

BenchmarkUnsorted-11    4376    263397 ns/op
BenchmarkSorted-11      4525    275829 ns/op

No meaningful difference. The M3’s branch predictor is sophisticated enough (a TAGE-style design) that it handles the sorted-data pattern with near-zero mispredictions. It learns the “always true → always false” transition almost instantly.

On an older Intel CPU (Haswell / Skylake era), the same benchmark tells a different story. The branch predictor has a simpler design and struggles with the sharp transition in sorted data. On the original Stack Overflow question, the measured difference for this exact pattern was roughly a factor of 3x on a Haswell-class CPU, driven by the burst of mispredictions at the transition point and the iterations it takes the predictor to relearn.

On AMD Zen architectures the effect falls somewhere in between — better than older Intel, worse than Apple Silicon.

So why write about this at all?

1. Not everyone runs Apple Silicon. Servers on Intel Xeons (common in AWS, GCP, Azure) still exhibit this effect measurably.
2. It explains the why behind performance. Even on hardware that handles it well, understanding branch prediction helps you reason about why certain code patterns are fast or slow.
3. The principle generalizes. The sorted-array example is the simplest case. In real code, branches on correlated data — status codes, feature flags, grouped records — can mispredict on modern CPUs when the pattern is complex enough.

What about branchless code?

One way to eliminate the branch entirely is to use bitwise tricks — replacing the if with arithmetic that produces the same result without branching. In C, the canonical form is:

// Branchless: mask is 0xFFFFFFFF when condition is true, 0x00000000 otherwise.
int mask = -(arr[i] <= 128);
sum += arr[i] & mask;

In Go the same idea can be written with a helper that compiles to a CMOV-style sequence on most architectures:

func branchlessSum(data []int, threshold int) int {
	sum := 0
	for _, v := range data {
		// v&mask == v when v >= threshold, 0 otherwise.
		mask := -boolToInt(v >= threshold)
		sum += v & mask
	}
	return sum
}

func boolToInt(b bool) int {
	if b {
		return 1
	}
	return 0
}

A few caveats: right-shifting negative signed integers follows arithmetic shift rules, so the >> trick that works in C isn’t portable in Go. And in practice, the Go compiler often emits a branch for this kind of code anyway, because it can’t always prove that the arithmetic form is faster than the branched form. The concept is the same regardless: convert a boolean into a numeric mask and use bitwise AND to selectively include values — no branch instruction, no misprediction penalty.

On modern CPUs like Apple Silicon, branchless code often performs identically to branched code because the predictor is fast enough. The real benefit shows up on older or simpler CPUs, or when the branch condition is genuinely random.

Why should you care?

You might think: “who sorts data before a conditional check?” Nobody does it on purpose. But consider these real-world scenarios:

• Status codes: an API returns HTTP status codes; you process a batch of responses where most are 200, then suddenly a bunch of 4xx/5xx errors appear. Checking if status >= 400 causes the predictor to struggle at the transition — especially on older CPUs.
• Feature flags: a config check like if featureEnabled is true for 99% of requests, then false for a batch of specific users. The predictor learns “always true” and gets hit hard when it’s false.
• Data processing: a dataset is grouped by category, and if record.Type == "premium" is true for a chunk of records and then suddenly false for the next chunk.

The pattern is always the same: a condition that is consistently one value for a long stretch, then switches. On modern Apple Silicon the predictor handles this gracefully. On older Intel CPUs it doesn’t.

What can you do?

1. Profile before optimizing. Branch misprediction is hardware-dependent. Use hardware counters — perf stat -e branch-misses ./bench on Linux, Instruments on macOS — to see if it’s actually a problem on your hardware before changing code.
2. Avoid sorted data before conditional branches if you’re targeting older CPUs. If you need to sort and filter, consider filtering first, then sorting the filtered results.
3. Use branchless techniques when profiling proves they help. Bitwise operations, arithmetic tricks, or lookup tables can replace branches entirely.
4. Consider data-oriented design. Group similar data together only if you’re going to process it uniformly. If you need to branch on a property, mixing values might actually be better for the CPU.

Conclusion

Branch prediction sits at the boundary between hardware and software. We can’t control the predictor directly, but understanding how it works helps us write better code.

The sorted-array example is the canonical demonstration — on older Intel CPUs it shows a roughly 3x performance difference; on modern Apple Silicon the predictor is advanced enough that the effect is negligible. Both facts are true, and both are worth knowing.

The next time your code runs slower than expected, the answer might be in the silicon, not the source code.

Challenge: run this benchmark on your own machine. On Linux, use perf stat -e branch-misses ./bench to see how many mispredictions occur with sorted vs. unsorted data, and share your results in the comments.