Sorting the Array First Makes the Loop Six Times Faster Without Changing What It Computes
Last timeMore Than One Instruction at a Time
A processor guesses which way every branch will go and starts the work. When the data makes the guess easy the branch is free. When it does not, each mistake costs twenty operations.
Why it cannot wait
The previous lesson described a processor with dozens of instructions in flight
at once. That design has an obvious problem the moment the code reaches an if.
The instructions after a branch depend on which way the branch goes, and which
way it goes depends on a comparison that has not finished yet. A processor that
waited would have nothing to start, and would sit idle for the depth of its
pipeline, which is fifteen to twenty cycles. Branches are about one instruction
in six in ordinary code. A machine that stalled at every one of them would
spend most of its time stopped and all the overlapping of the previous lesson
would be worth nothing.
So it guesses. It predicts which way the branch will go, begins executing down
that path immediately, and carries on. When the comparison finally resolves,
one of two things happens.
How good the guess is
The predictor is better than most people assume. It remembers what each branch
did recently, and modern ones remember sequences: the pattern of the last
several outcomes, used to index a table of what usually followed that pattern.
A branch that alternates true, false, true, false is learned perfectly. A
pattern repeating every eight iterations is learned perfectly.
| guessed right, per cent | cycles lost per thousand | |
|---|---|---|
| a loop running 1000 iter | 100 | 0 |
| a check that is almost n | 100 | 0 |
| a pattern repeating ever | 99 | 180 |
| a comparison on sorted d | 98 | 360 |
| a comparison on partly s | 75 | 4500 |
| a comparison on shuffled | 50 | 9000 |
The last row deserves emphasis because it is a hard limit rather than an
engineering shortfall. If the direction of a branch is genuinely unrelated to
anything that happened before, no mechanism can do better than chance. Better
predictors do not help. A newer processor does not help. The only remedy is to
change the code so the branch is not there, which is the subject of the next
lesson.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents