English is currently available.
Computer Engineering DISCUSSION
I have a loop that adds up every element of a 32,768-element array whose value is 128 or more: if (data[i] >= 128) sum += data[i];. The values are random bytes from 0 to 255. If I sort the array first, the loop runs several times faster, even though it executes exactly the same number of comparisons and additions.
What makes sorted data faster for the processor, and why do some people report no difference at all when they try to reproduce this?
The cause is branch prediction. A pipelined processor fetches and starts executing instructions many cycles before a conditional branch is resolved, so it guesses the outcome and carries on speculatively. A correct guess costs nothing. A wrong guess means everything started after the branch is discarded and the pipeline refills from the correct path, which costs on the order of 15 to 20 cycles on current desktop processors.
With sorted data the branch is not taken for the first part of the array and taken for the rest, so the predictor is wrong about once. With random data the outcome is a coin toss and no predictor can do better than about 50 percent.
Rough numbers show why it dominates. With random data about half of the 32,768 branches mispredict: 16,384 × 15 cycles is about 250,000 cycles per pass lost to recovery. The useful work, a load, a compare and an add per element, is only a cycle or two each, perhaps 30,000 to 60,000 cycles for the whole pass.
So the unsorted run spends several times longer recovering from wrong guesses than doing arithmetic, and that ratio is the speed difference you measure.
People who see no difference have usually compiled with full optimisation. The compiler can remove the branch entirely, either with a conditional move or by vectorising the loop with SIMD compares and masks. Then there is nothing to predict and sorted and unsorted data take the same time.
You can do the same by hand. Since a comparison yields 0 or 1 in C, sum += data[i] & -(data[i] >= 128); adds either the value or zero with no branch. A conditional move turns the control dependency into a data dependency: both inputs are computed and one is selected, which costs a cycle or so every time but never causes a pipeline flush.
On how the predictor learns: the simplest scheme is a two-bit saturating counter per branch, which needs two wrong outcomes in a row to change its prediction, so a loop branch is mispredicted only on exit. Modern predictors add history: they index their tables with the branch address combined with the outcomes of the last several dozen branches, so they also learn repeating patterns such as taken, taken, not taken.
That is why a branch does not need to be biased to be fast, only regular. Data-dependent branches on random values are the case that cannot be learned.
Before restructuring real code, measure. On Linux, perf stat -e branches,branch-misses ./program reports the misprediction rate directly; a hot loop with a rate of tens of percent is a candidate, and one at 1 percent is not.
Sorting just to help the predictor rarely pays, since the sort costs far more than one pass over the data. It pays when the same data is scanned many times. Otherwise the usual tools are branchless arithmetic, lookup tables, or partitioning the data once so that each loop handles one case.
