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

I have a loop that sums every element of a large std::vector<int> that is at least 128. If I sort the vector first (outside the timed region), the loop runs about five times faster:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> v(1 << 16);
    std::mt19937 rng(42);
    for (auto& x : v) x = rng() % 256;

    std::sort(v.begin(), v.end());   // comment this out -> 5x slower

    auto t0 = std::chrono::steady_clock::now();
    long long sum = 0;
    for (int rep = 0; rep < 50000; ++rep)
        for (int x : v)
            if (x >= 128) sum += x;
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>(t1 - t0).count() << "s " << sum << "\n";
}

The work is identical — same elements, same number of additions. Why would the order matter?

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.

Does this mean I should always sort before looping?

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.

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

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.