DEV Community

gxqwb
gxqwb

Posted on

Linear Scan vs Graph Coloring: Compile Time You Can Feel

A register allocator decides which of a program's live values sit in the handful of physical registers and which get pushed to the stack. It is the pass where a compiler's theoretical elegance meets a fixed budget of sixteen or thirty-two names, and it is also the pass that most often makes a build feel slow. Two families dominate: graph colouring, which models the problem as a graph and tries hard to find a good colouring, and linear scan, which walks the code once in order and assigns registers as it goes.

A graph-colouring allocator can cut spill code by 5 to 15 percent over linear scan, but its compile time grows with the square of live ranges and interference edges; linear scan is effectively linear and is why every serious JIT uses it.

Part One: What is being compared

Graph colouring starts by building an interference graph: one node per live range, an edge whenever two ranges are alive at the same time and therefore cannot share a register. Colouring that graph with k colours, where k is the number of allocatable registers, is NP-complete, so real compilers use heuristics. Chaitin-style allocators repeatedly remove nodes with fewer than k neighbours, push them on a stack, and pop them back assigning colours; when every remaining node has k or more neighbours, one is chosen to spill, its live range is split, and the process restarts.

Linear scan gives up on the global view. It sorts live intervals by start point, keeps an active list ordered by end point, and when a new interval starts it expires everything that has already ended, then assigns a free register or spills the interval that ends furthest in the future. One pass, no graph, no iteration.

The difference in what they optimise is the whole story. Graph colouring optimises the number of spills across the entire function. Linear scan optimises the cost of the pass itself, and treats the function as a sequence rather than a structure.

Part Two: The arithmetic

Take a function with 5,000 instructions and a few thousand live ranges, which is ordinary for generated code or a large inlined method. Building the interference graph means, for each program point, connecting every pair of live values. If a point has 40 live values, that is 780 edges from that point alone, and a function with thousands of points can produce hundreds of thousands of edges before any simplification begins. The iterated spill-and-rebuild loop multiplies that by the number of rounds, typically two to five.

Linear scan touches each interval a constant number of times. Sorting is O(n log n), and the active-list maintenance is O(n) with a balanced structure. In practice, allocator time for linear scan lands in the low single-digit percentage of total compile time; for graph colouring on large functions it can reach 20 to 30 percent, and it is the pass that makes a debug build of a template-heavy C++ file feel like it hangs.

The quality gap is smaller than the complexity gap. Published comparisons and compiler engineering reports put linear scan at roughly 5 to 15 percent more spill code than a good graph-colouring allocator, with the gap widening on functions with high register pressure and narrowing on straight-line code. Spill code costs a load or a store, so a 10 percent spill increase on a spill-heavy function might cost 2 to 5 percent of runtime, and on a function that already fits in registers it costs nothing.

That asymmetry explains the deployment pattern. Ahead-of-time compilers that run once and whose output runs a million times — LLVM, GCC — use graph-colouring variants and accept the compile time. Just-in-time compilers that must produce code while a user waits — HotSpot's C1, V8's baseline tiers, LuaJIT's early passes — use linear scan, because a 30 percent slower compile is a 30 percent longer pause.

Part Three: Where the model breaks

The clean story assumes live ranges are intervals. They are not. A value defined inside a loop and used after it is live across the loop body with holes in the middle, and treating it as a continuous interval overestimates pressure and causes unnecessary spills. Graph colouring handles holes naturally because it works on points, not intervals; linear scan either ignores them and spills more, or adds a second pass to split ranges at holes, which erodes its speed advantage.

The second break is coalescing. When a move can be eliminated by assigning both sides the same register, graph colouring can merge the nodes and remove the instruction. Linear scan usually cannot, so it leaves moves in place, and on architectures with two-address instructions those moves are real work. This is a large part of the quality gap and it is invisible in spill counts.

The third break is compile-time predictability. Graph colouring's runtime depends on the input structure in a way that is hard to bound; a pathological function can trigger many spill rounds. Linear scan has a bound you can reason about, which matters when the compiler runs inside a latency-sensitive service or a build farm with thousands of parallel jobs.

Part Four: The later cost

There is a maintenance bill attached to each. A graph-colouring allocator is a large piece of machinery: interference construction, coalescing, spill heuristics, live-range splitting, and a repair loop. Bugs are subtle and often appear only on inputs with specific pressure patterns, which is why compiler test suites lean on randomized differential testing.

A linear-scan allocator is small enough for one engineer to hold in their head, which is why it survives in JITs where the compiler ships inside a runtime that must be maintained for a decade. The cost is paid by the generated code rather than by the team, and for a JIT the trade is usually correct: a 3 percent slower program is invisible, a 30 millisecond longer pause is not.

Modern allocators blur the line. LLVM's greedy allocator is a graph-colouring design tuned for compile speed; the "linear scan" in HotSpot's C1 has been extended with range splitting and interval hints until it is a hybrid. The interesting question is no longer which algorithm, but which parts of the global view you can afford.

Part Five: Outside the team

For a developer, the difference is whether a clean build takes 40 seconds or 90, and whether the editor's language server responds while you type. That is allocator time showing up as attention cost, multiplied across a team and a day.

For a user, the difference is a JIT pause during a video call or a keystroke that lands late in a browser tab. A 20 millisecond compilation pause is imperceptible; a 200 millisecond one is a dropped frame. The allocator is one contributor among many, but it is one of the few where the trade is explicit and measurable.

A fair comparison fixes the instruction set, the register count, the benchmark suite and the optimisation level, then reports both compile time and runtime. Reporting only runtime is how a compiler team talks itself into a build that nobody wants to run.

Market sizing check

The commercial weight sits in toolchains and runtimes rather than in allocators as a product: compilers, language runtimes and the build infrastructure around them are plausibly a $10B to $20B a year segment by 2030, and allocator design influences a small but real share of it through build speed and runtime performance. The swing factor is how much code generation moves into always-on services where compile latency is billed.

These figures are an indicative synthesis of published tooling market ranges, not a vendor forecast.

The comparison that matters

The comparison that matters is between a global search for fewer spills and a single pass that finishes on schedule. Graph colouring wins where the binary runs far more often than it is built and where the last few percent of code quality compound. Linear scan wins where compilation happens at runtime, inside an editor, or in a build farm whose throughput is the constraint.

The ranking assumes register pressure is moderate. On functions that spill heavily regardless, the quality gap widens and graph colouring earns its time; on functions that fit comfortably, both produce the same code and only the clock differs.

Choose the allocator by who waits for it: graph colouring when the build is paid once and the binary runs forever, linear scan when a human or a request is waiting on the compile.

SOL: HCqPmPJM3NVtS6YrmVaTZYnuP8XZ2PFgQZKT94VK1LkS
If this saved you time, a tip is appreciated.

Top comments (0)