Graph Colouring vs Linear Scan Allocation
That linear scan is simply the worse algorithm. It produces more spills on high-pressure code, but it runs in roughly linear time, and in a JIT the time spent allocating is time the program is not running — so the faster algorithm can win on end-to-end performance.
Graph-colouring allocation
In an ahead-of-time compiler at higher optimization levels, where allocation quality is worth superlinear compile time.
Linear-scan allocation
In a JIT or a baseline tier, where allocation must finish in time proportional to the program.
| Aspect | Graph-colouring allocation | Linear-scan allocation |
|---|---|---|
| Model | Interference graph; adjacent live ranges need different registers. | Live intervals sorted by start point, scanned once. |
| Cost | Building and simplifying the graph is superlinear in practice. | Near linear after sorting. |
| Handling of holes in a live range | Precise, since interference is computed per program point. | Approximated by one interval unless intervals are split. |
| Spill decisions | Chosen with a cost heuristic when simplification gets stuck. | Chosen when the active set is full — typically the interval ending last. |
| Result quality | Better under pressure, especially across loops. | Good enough for most code, worse where many values are simultaneously live. |
| Where you find it | Traditional AOT backends and higher optimization tiers. | JIT baseline tiers, and compilers where build time is a product requirement. |