Answers · How a program runs
Why does sorting an array make a loop that scans it and counts matches so much faster?
In shortSorting does not make the comparisons cheaper. It makes the test inside the loop predictable, so the processor stops guessing wrong and stops paying for those mistakes.
Sorting does not make the comparisons cheaper. It makes the branch predictable, and a processor that guesses a branch correctly pays nothing for it, while a wrong guess costs about twenty cycles of work that gets thrown away. On shuffled data the test inside a counting loop is true about half the time with no pattern to learn, so the guess is a coin flip and roughly ten wasted cycles are paid per element. Sorted, the test is false for the whole run of elements below the threshold and true for the whole run above it, and the predictor is wrong about twice in the entire pass. The count is the same number in both runs.
- cycles lost to wrong guesses in total
- how many times the branch is reached
- the share of those guesses that are wrong
- the penalty for one wrong guess, about twenty cycles
Take a million elements, a threshold that half of them exceed, and a loop that counts the ones above it. The test is reached a million times. Shuffled, the predictor is right about 500,000 times and wrong about 500,000 times, so the loss is cycles. At 3 GHz that is seconds, about 3.3 milliseconds, and per element it is ten cycles that buy nothing at all. Sorting the same million numbers gives two long runs of one answer instead of a million coin flips, so falls to two in a million and the branch cost falls to cycles.
| arrangement | guesses wrong, per cent | wrong guesses | cycles lost |
|---|---|---|---|
| sorted | 0.0002 | 2 | 40 |
| shuffled, 1 in 100 above the threshold | 1 | 10,000 | 200,000 |
| shuffled, 1 in 5 above the threshold | 20 | 200,000 | 4,000,000 |
| shuffled, half above the threshold | 50 | 500,000 | 10,000,000 |
Why the loop does not speed up by 250,000 times
The branch cost fell by a factor of 250,000, from 10,000,000 cycles to 40, but the loop as a whole only gets five or six times faster, because the branch was never the whole loop. Suppose the remaining work, loading the element, comparing it, and usually skipping the increment, costs 2 cycles per element. Shuffled, the loop takes cycles per element, so 12,000,000 cycles, roughly 4 milliseconds. Sorted, it takes 2 cycles per element plus a negligible 40, so 2,000,040 cycles, roughly 0.67 milliseconds. The ratio is 6, and the difference between the two runs, about 3.3 milliseconds, is precisely the misprediction bill computed above. Counting matches rather than summing them makes the body thinner still, so a body of 1 cycle would give 11 cycles against 1, nearer eleven times.
The natural guess is that sorted data is somehow cheaper to compare. It is not. The comparison compiles to the same instruction on the same two numbers whatever order they arrived in, and a processor has no idea whether its operands were sorted. Sorting does not remove a single comparison from the loop, so if comparisons were the cost, sorting could not help at all. What sorting changes is the sequence of outcomes: false, false, false for half the array, then true, true, true for the rest. The predictor is a table indexed by recent history, and a long run of one answer is the easiest thing in the world for it to learn. A coin flip is the one thing it cannot learn, and no newer processor fixes that, because a direction unrelated to anything recent is wrong half the time by construction.
Sorting is not free, and the bill arrives first. A comparison sort of a million elements takes on the order of comparisons, twice the 10,000,000 cycles the branch was losing, before any moves are counted. Sorting to speed one pass is therefore a loss; it pays when the data is already sorted, is kept sorted cheaply, or is traversed many times. It also pays nothing if the compiler emits a conditional move rather than a branch, because then there is no direction to guess. And the gain shrinks as the data gets tamer: with only 1 in 100 elements above the threshold, the shuffled run loses 200,000 cycles out of 12,000,000 and there is little left to win. Whether a given loop is actually mispredicting is worth confirming with a counter rather than assumed.
Worth keeping
- A correctly guessed branch costs nothing at all; a wrong guess costs about twenty cycles of discarded work.
- A test on shuffled data is guessed right about half the time and no predictor can do better, because there is no pattern there to learn.
- Sorting a million elements costs about twenty million comparisons, so it only pays for a loop that was mispredicting badly and is run many times.
Where this goes next
This question is one step of What Makes Code Fast, a course that works through its subject from the beginning. The page that teaches this part of it is Guessing Which Way You Will Go, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- If I make one part of my program twice as fast, how much faster does the whole program get?Less than twice as fast: only the share of run time you actually touch can improve, so the untouched remainder caps the gain, often at a few per cent.
- Why does 2 + 3 * 4 equal 14 and not 20?The multiplication is done first: three times four makes twelve, and only then is the two added, giving fourteen. Reading left to right would give twenty.
- How many samples does a profiler need before a percentage in the report means anything?It depends on how many samples landed on that line: you need a few hundred samples on the line you care about, because the relative error is roughly one over the square root of that count.
- Why does reading one byte from memory load 64 bytes?Memory hardware moves data in fixed sixty-four-byte blocks, so a one-byte read fetches the whole block; the extra bytes cost almost nothing because reaching the memory row costs most of the time.
- Why can two threads that each work correctly still give the wrong answer?Each thread reads the shared value and writes it back in two separate steps, so the other thread can run in between and one increment silently overwrites the other.
- My change made it 4% faster — how do I know that isn't just noise?You cannot tell from one pair of runs. Run the unchanged program ten times first: only then does a four per cent gap mean anything.