One Number Tells You Which Half of the Toolbox to Open
Last timeRemoving the Decision
Divide the arithmetic your loop performs by the bytes it moves. That single ratio says whether the processor or the memory is your ceiling, and therefore which optimisations can possibly help.
Operations per byte
The previous four lessons supplied techniques. This one supplies the question
that should be asked before any of them, because it decides which of them can
possibly work.
Take the loop you care about. Count the arithmetic operations performed in one
iteration. Count the bytes that have to travel from memory for that iteration.
Divide the first by the second. That ratio is the single most informative
number you can know about a loop, and it comes from reading the source rather
than from running anything.
- arithmetic intensity, in operations per byte
- arithmetic operations performed
- bytes that must come from memory
Take the simplest possible example. A loop adding two arrays into a third
performs one addition and moves twenty-four bytes, eight for each operand and
eight for the result. Its intensity is one operation per twenty-four bytes, or
about 0.04.
Now take a matrix multiply written in the obvious way but blocked so that each
block of data brought in is used many times. Each byte that arrives is involved
in dozens of multiplications before it is evicted, and the intensity is in the
tens.
Those two loops live in different worlds, and almost nothing that helps one of
them helps the other.
Two ceilings, whichever is lower
There are two hard limits on any loop. The processor can perform a certain
number of operations per second, set by its width and clock. The memory system
can deliver a certain number of bytes per second, set by the bus and the number
of channels. Your loop runs at whichever of those it hits first.
The lesson stops here
5 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