Why does iterating a sorted list run faster than an unsorted one in this C++ loop?

You are seeing branch prediction.

The CPU does not wait to find out whether x >= 128 is true before it starts executing what comes next. It guesses, based on the recent history of that branch, and runs ahead speculatively. A correct guess is almost free; a wrong one throws away the speculative work — around 15–20 cycles on a modern core.

• Sorted: the branch is false for the first half and true for the second. The predictor is wrong roughly once.

• Unsorted: the outcome is effectively random, so the predictor is wrong about half the time.

Remove the branch

for (int x : v) {
    int mask = -(x >= 128);   // all ones or all zeros
    sum += x & mask;
}

Or let the compiler vectorise: at -O3 most compilers turn the original loop into a branchless SIMD loop, and the sorted/unsorted difference disappears. Check with -fopt-info-vec (GCC) or -Rpass=loop-vectorize (Clang).

Good answer. One way to see it: run both versions under perf stat:

$ perf stat -e branches,branch-misses ./unsorted
   3,276,800,000  branches
   1,612,442,113  branch-misses   # 49.21% of all branches
$ perf stat -e branches,branch-misses ./sorted
   3,276,800,000  branches
          49,871  branch-misses   #  0.00% of all branches

The miss rate is the whole story.

Worth mentioning that the effect also exists in interpreted languages — I measured about 2× in CPython for the same pattern, smaller because interpreter overhead dominates.

The perf stat comparison is exactly what I needed to convince my team. Thanks both.

Does this mean I should always sort before looping?

No — sorting is O(n log n) and costs far more than the mispredictions unless you loop over the same data many times. Prefer the branchless form.

Which compiler and flags? With -O3 GCC turns this into a branchless cmov and the difference disappears.

@Keiko clang 17, -O2. You are right — at -O3 both run in the same time.

One of the clearest explanations of speculation I have read. The railway analogy in the second paragraph is what made it click.

Worth adding that perf stat -e branch-misses shows the difference directly.