Turning Text Into Instructions
Thousands of Values and Sixteen Places to Keep Them
Last timeThe Promises You Made
The middle form invented names without limit. The machine has a few dozen fast slots. Deciding which values get one, and which get pushed to memory, decides the speed of the output.
More names than places
The middle form invented a name for every intermediate value and made no
attempt to economise. A medium function has a few thousand of them. A machine
offers perhaps sixteen general-purpose registers, a few of which are already
spoken for by the calling convention.
Everything that does not get a register lives in memory, and from the memory
course the cost of that is known: a register access is free in the sense that
it is part of the instruction, while a memory access that hits the nearest
cache is a few cycles and one that misses is dozens or hundreds.
So the job is to put as much as possible in the small fast set. If that sounds
hopeless at a ratio of two hundred to sixteen, it is not, because almost all
of those names are not alive at the same time.
Lifetimes, not values
A value needs somewhere to live only between the point where it is produced
and the point where it is read for the last time. Before that it does not
exist, and after it nobody cares. That interval is its lifetime.
Two values whose lifetimes do not overlap can share one place with no conflict.
The question is therefore not how many names the function has but how many are
alive at the same moment, which is a much smaller number.
| counter | address | temporary one | sum | temporary two | return value | |
|---|---|---|---|---|---|---|
| counter | 0 | 1 | 1 | 1 | 1 | 1 |
| address | 1 | 0 | 1 | 0 | 0 | 0 |
| temporary one | 1 | 1 | 0 | 0 | 0 | 0 |
| sum | 1 | 0 | 0 | 0 | 1 | 0 |
| temporary two | 1 | 0 | 0 | 1 | 0 | 0 |
| return value | 1 | 0 | 0 | 0 | 0 | 0 |
That reformulation is the classic one. Build a graph with a node per value and
an edge between values whose lifetimes overlap, then colour it with as many
colours as there are registers. A valid colouring is a valid assignment.
The reformulation also tells you the bad news. Colouring a graph with a fixed
number of colours is one of the genuinely hard problems, so every compiler uses
a heuristic, and the heuristic is where allocators differ from each other.
The lesson stops here
2 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