Why a sorted array is faster: branch prediction, visually

There’s a Stack Overflow question that’s been doing the rounds since the summer and keeps showing up on Hacker News: Why is processing a sorted array faster than an unsorted array? If you haven’t read it yet, go read it. The code is about as simple as code gets:

// 32768 random values between 0 and 255
for (unsigned i = 0; i < 100000; ++i) {
    for (unsigned c = 0; c < arraySize; ++c) {
        if (data[c] >= 128)
            sum += data[c];
    }
}

In the question, this takes 11.54 seconds on random data. Add std::sort(data, data + arraySize) before the loop and it takes 1.93 seconds. Same work, same data, same number of additions, just sorted first. Mysticial’s accepted answer explains why with a railroad junction analogy, and it’s a great answer, but I found I only really got it after drawing it out, so here are the drawings.

The pipeline

A modern CPU doesn’t execute one instruction at a time, it works like an assembly line. While one instruction is executing, the next one is being decoded and the one after that is being fetched. On a current Intel chip that line is something like 14 to 20 stages deep, which is how it gets close to one instruction per cycle even though each instruction takes many cycles end to end.

The trouble is the if. When the CPU gets to the branch, it doesn’t know yet whether data[c] >= 128 is true, because the comparison is still working its way down the line. But the line can’t just sit there, it has to keep feeding instructions in at the front. Which ones, the ones inside the if or the ones that skip it? It guesses. If the guess is right, nothing is lost. If it’s wrong, everything it loaded after the branch gets thrown away and it starts again from the right place, which costs roughly as many cycles as the pipeline is deep. In a loop this tight that’s a lot more than the addition itself costs.

The predictor

The classic way to guess, and still the core of what real predictors do (real ones are a lot fancier), is a two-bit saturating counter for each branch. It remembers which way the branch has been going lately and needs to be wrong twice in a row before it changes its mind:

A two-bit saturating counter. One surprise nudges it, two in a row flip the prediction.

Now feed it the two arrays. These are 16 iterations of each, run through that counter by hand. Each cell is which way the branch actually went (T for taken, N for not) and the color is whether the predictor got it right:

Sorted data: two misses, both where the values cross 128. Random data: seven misses in sixteen.

With sorted data the branch goes “not taken” for the entire first half of the array and “taken” for the entire second half, so the predictor misses twice at the crossover and is right for the other 32,766 elements. With random data there’s nothing to learn. No predictor can do better than a coin flip, so roughly every other iteration pays for a pipeline flush, and that’s where the 6x goes.

Getting rid of the branch

The fix in the answer is a neat bit twiddling hack, the kind of thing you’d find on Sean Anderson’s Bit Twiddling Hacks page. If the branch is the problem, don’t have a branch:

int t = (data[c] - 128) >> 31;  // all ones if data[c] < 128, else zero
sum += ~t & data[c];

Shifting a negative number right by 31 smears the sign bit across the whole word (technically that’s implementation-defined in C++, but every compiler you’re likely to use does an arithmetic shift), so t ends up as a mask of all ones or all zeros and ~t & data[c] is either data[c] or 0. Nothing to predict. With that version sorted and unsorted run at the same speed.

Some compilers will do this for you, by the way. Depending on the compiler and flags, the if can turn into a conditional move (cmov) or the loop gets vectorized, and then the sorted/unsorted difference just disappears. The answer also mentions the Intel compiler doing something even sneakier and interchanging the two loops. So measure, don’t assume. And please don’t go sprinkling >> 31 all over your code after reading this. This is a hot inner loop that runs 3.2 billion times, your controller action is not.

I played with my digit-uniqueness counter a while back and came away with a similar feeling, that the machine in my head where every operation costs one unit is a lie. The real machine has pipelines and caches and predictors, and they reward predictable code in ways big-O notation doesn’t capture at all. For what it’s worth, I tried the loop in C# as well, and the JIT doesn’t save you either. Same shape of result.