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.