Gotta go fast

I care about the gap between changing a line and finding out I was wrong. A compiler can produce excellent machine code and still make that gap annoying. During development, I would often take a slightly slower program in exchange for getting it back sooner.

We have already tried moving a small compiler onto the GPU. This time I want to go in the other direction. One thread, ordinary data structures, and a fairly rude question for every stage: do we actually need to do this?

The interesting small compilers have useful answers. Some generate instructions while reading an expression. Some keep just enough information to put its values in registers. Others keep an intermediate representation (IR), a form designed for the compiler to work on, but make it small enough that a handful of passes is cheap. There are several architectures here, with different things they are willing to give up.

Start with the work, not the stopwatch#

For a serial build, it helps to split the wait into reading inputs, resolving names and types, generating code, and assembling or linking the result. That accounting is deliberately boring. It stops a faster parser from getting credit for an improvement that actually came from a warm filesystem cache, or a compiler benchmark from quietly excluding the linker.

A direct-emitting compiler tries to overlap some of those responsibilities. The parser already knows that it has finished an addition. Given the operand types and locations, it can emit the addition right there. There is no requirement to first allocate an addition node, finish a whole tree, and visit that node again.

TinyCC is a concrete native-code example. Its 0.9.27 developer manual describes direct binary generation, expression-local optimization, and a value stack instead of a retained expression representation. It also integrates assembling and linking. The manual explicitly lists exceptions to its one-pass parser, including counting an initializer whose array size is unknown. So even this example comes with an important qualification: mostly one pass, where that fits the language. I am using that documented design here, not treating an old manual as a current target-support matrix.

The benefit to reason about is work avoided: fewer retained objects, fewer traversals, less conversion between formats. Whether that wins on a particular compiler still needs measurement. A bad hash table or an accidentally quadratic loop does not become fast because the pipeline has fewer boxes.

Compile an expression before building a tree#

Take a deliberately tiny language: signed 32-bit integer inputs, decimal constants, addition, subtraction, multiplication, unary minus, and parentheses. Arithmetic wraps modulo 2 to the power of 32. No overload resolution. No function calls. The compiler already knows every parameter's type and position.

The companion implementation compiles an expression to custom stack bytecode. A separate interpreter runs that bytecode. This is enough to demonstrate the architecture without pretending that a JavaScript array of opcodes is native machine code.

import { compile, execute } from "./compiler.mjs";const program = compile("x + 2 * 3", ["x"]);execute(program, [10]); // 16

For that expression, the emitted instructions are the following. Parameter zero is x; each constant pushes another operand; multiplication and addition consume two operands and leave one result.

LOAD  0      // parameter xCONST 2CONST 3MULADD

The scanner supplies one lookahead token. The parser emits LOAD when it resolves a parameter and CONST when it reads a literal. Multiplication gets a higher precedence than addition, so its right-hand expression finishes first. The relevant loop is small enough to keep in your head.

while (precedence(token.text) >= minPrecedence) {  const op = token.text;  const binding = precedence(op);  token = next();  expression(binding + 1);  emit(opcode[op]);}

The recursive call consumes the right operand at the appropriate precedence. Then emit appends the operator. Adding one to the binding strength makes equal-precedence operators left-associative: 20 - 5 - 3 becomes (20 - 5) - 3. Parentheses and unary minus are handled before this loop in the full implementation.

Notice what has survived when parsing finishes: the output bytes. There is no tree waiting to be lowered. The implementation still does real work: scanning, resolving parameter names, checking literal bounds, rejecting trailing tokens, and reporting source offsets. A syntax error discards the partial output rather than returning an executable half-program.

I kept a regular-expression scanner, a growable number array, and a final byte-array copy because they make the example readable. Those are not claims about the fastest JavaScript implementation. Its tests cover exact output, wrapping arithmetic, malformed input, a long flat expression, and 1,000 generated expressions checked against a separate tree evaluator. Run them with node --test examples/gotta-go-fast/compiler.test.mjs. There are no timing claims hiding in the test output.

A stack in the compiler need not be a stack at runtime#

The toy takes its stack literally: the interpreter pushes and pops values. A native emitter has another option. Its compile-time stack can hold descriptions saying where each value will live when the program runs.

// A possible native emitter's compile-time bookkeeping.// These are descriptions of values, not instructions to execute.type Value =  | { kind: "constant"; value: number }  | { kind: "register"; reg: number }  | { kind: "spill"; offset: number };

Suppose the emitter has just read the constant 2. It can record the number without emitting a load. After reading 3 and the multiplication, it can replace those two descriptions with the constant 6. When it finally combines that value with x, it may select an add-immediate instruction. This requires delaying emission; our first, literal bytecode emitter does not do that folding.

That small delay buys a useful amount of optimization. There is no search through an entire function to discover that two constants multiply to another constant. The operands are already in front of the emitter. For this language, folding uses the same 32-bit wrapping rule as execution. A different language may require overflow diagnostics, trapping behavior, or careful floating-point handling instead.

In V8's description of Liftoff, the baseline WebAssembly compiler decodes and validates a function while generating native code. Its virtual operand stack tracks constants, registers, and spilled values; small integer constants can remain metadata until used. Wasm's typed instructions and structured control flow make this practical. This starts from bytecode with explicit structure and types, so it does not eliminate the work required to translate a high-level source language into Wasm.

Register allocation can follow the same local approach. Reuse a register whose old value is no longer needed, take a free one, or spill a value to the function's stack frame. The compiler avoids a global search for a better assignment, at the possible cost of extra loads and stores in the generated program. Correctness still requires tracking aliases: two logical values may currently refer to the same register, so overwriting one must not silently destroy the other.

Branches add another obligation. If one arm leaves a value in a register and the other leaves it in memory, the code after the branch needs an agreed location. Liftoff's write-up describes snapshots of the expected state and moves that reconcile incoming states. A simpler first implementation could make both arms spill to canonical slots. Easy to reason about; potentially more runtime traffic.

Leave an address blank and come back#

Direct emission raises an obvious question: how can an if jump over code that has not been emitted yet? Usually, by reserving the jump operand and remembering its position.

For a made-up instruction encoding with a signed four-byte displacement measured from the end of that operand, the bookkeeping looks like this. This sketch extends the design; the arithmetic-only companion does not implement branches.

// Pseudocode for our own fixed-width relative-jump encoding.// reserveI32 appends four placeholder bytes and returns their offset.const operand = reserveI32(output);compileThenArm();const target = output.length;const displacement = target - (operand + 4);checkSignedI32(displacement);writeI32LE(output, operand, displacement);

If the operand begins at byte 9 and the target is byte 27, the displacement is 27 - 13 = 14. The compiler writes that value into the reserved bytes. A real instruction set specifies its own displacement rules and ranges. Fixed-width encodings simplify this job; selecting shorter encodings can introduce layout or relaxation passes.

The same idea handles a call whose destination address is not known yet. Keep a relocation or fixup containing the symbol, the patch location, and the relocation kind. Resolve it when code layout or linking supplies the address. Check that every required target was resolved and that each encoded displacement fits.

That solves a missing address. It does not solve a missing type. Before emitting a call, the compiler may need argument types, return-value layout, and the calling convention. A function declaration can provide those facts before the body exists.

For a language that permits definitions in any order, I would happily scan declarations first and compile bodies afterward. Another cheap pass over compact data may be much simpler than forcing every decision into one traversal. Count the work and the information that must remain live. Pass count alone is a weak design target.

Keep the working set small#

Even when a compiler needs a tree, there is no rule saying that every node must be a separately allocated object containing several copied strings. An array of nodes with integer indices is one possible representation. Keeping source spans as offsets into an owned source buffer can avoid copying text into every node.

When designing a compiler, I would start by drawing the lifetimes. Module signatures may need to survive the entire compilation. A function's temporary analysis data may only need to survive that function. The output object and its relocations have another lifetime. Giving all three the lifetime of the entire program is convenient until the program gets large.

An arena makes allocating many short-lived nodes cheap by handing out pieces of larger blocks and reclaiming the blocks together. Interning pays to look up a spelling once per occurrence, then lets later stages compare IDs instead of strings. Neither is free. An interner adds its own table, and an arena with the wrong lifetime keeps memory around longer than necessary.

I would also keep diagnostics out of the hot representation where possible. A node usually needs a source span, not a fully formatted error message. Format the rich explanation when reporting the error. Keep enough information to do that properly; making a compiler quicker by making its errors useless is a pretty bad trade.

The broader point is to reduce allocation, copying, and unrelated data touched during a traversal. Compact arrays often help with those goals, but I would check allocation profiles and peak memory before rewriting every structure. A simple pointer-based tree that is small and short-lived can be entirely fine.

Decide what a function is before compiling its neighbors#

Language design determines how much information the compiler must chase. An explicit function boundary gives a simple compiler somewhere to stop. It can infer local bindings without needing to infer the interface of an unrelated function at the same time.

// Sketch of a language with explicit function boundaries.fn twice(x: i32) -> i32 {  let result = x + x; // infer this locally  return result;}fn main() -> i32 {  return twice(21); // its signature is enough to check the call}

Here, checking the call requires the signature of twice. Looking inside its body may help optimize the call, but it is not necessary to decide whether the argument and result types fit. That separation leaves room for a fast development compiler and a more ambitious release compiler.

Generics make the distinction important. Sharing one implementation through a uniform representation or passed-in operations can avoid generating a separate body for every concrete type. Specialization can give the optimizer more information, but creates additional bodies to process. Actual languages mix strategies. I would put a budget on specialization before allowing the number of generated functions to grow without an obvious bound.

Modules provide a larger stopping point. Rob Pike's account of Go's design explains the importance of dependency information and exported package data to compilation. The useful idea to borrow is that a consumer should load the interface information it needs, rather than repeatedly rediscovering that information from dependency source. That historical account does not make today's Go compiler a one-pass compiler.

For a small language, I would serialize names, types, layouts, and the other facts consumers require. Inline bodies or generic definitions may also be required, depending on the language and build mode. An interface file is only a valid boundary when it actually contains enough information to compile the consumer.

Sometimes one small IR is the simpler answer#

Direct native emission gets less comfortable when several language constructs require nonlocal decisions. Closures need captured environments. Cleanup needs to happen along every applicable exit. Branches need consistent value locations. Good diagnostics may need context the parser has already left behind.

At that point, an intermediate representation can simplify the implementation. Keep one function in a compact form, make the necessary control flow explicit, run a few transformations, and emit it. The extra traversal can be cheaper than the bookkeeping invented to avoid it.

QBE demonstrates a useful middle position. It uses one static single-assignment (SSA) intermediate language across its compilation stages: each temporary value has one definition. It includes copy elimination and constant propagation through control flow. Its register allocator is linear, with separate spilling machinery. It also handles the C application binary interface (ABI), the platform rules for calling functions and passing values. This is a compact optimizing backend, not a direct-emitting one-pass compiler; using it does not make your language's frontend disappear.

There is also copy-and-patch compilation: prepare machine-code fragments with holes, then select, copy, and patch them when compiling a program. That moves some code-generation work into construction of the fragment library. It can make the online emitter small, but the full system still owns a template generator, target details, relocations, and calling-convention rules. I would distinguish a simple runtime compiler from a simple toolchain.

Include the boring end of the build#

Emitting textual assembly is convenient: a human can read it, and an existing assembler handles instruction encoding and object files. It also introduces formatting, another parse, and often another process. Direct object or machine-code emission can remove those steps, while moving responsibility for encodings, relocations, debug information, and platform conventions into your compiler.

A faster backend will not fix every long wait. The linker still has symbols and relocations to process. The build tool still has to decide what changed. Dependencies may still need compiling. That is why I would time both compiler-only work and the actual edit-to-executable command. Turning optimization off also does not automatically remove a compiler's frontend, lowering, register allocation, or output machinery.

Caching is a separate lever: do less work on the next build. A package-level cache can be a reasonable first step before building a fine-grained query engine. Its key must account for source, relevant dependency information, compiler version, target, flags, and any other inputs that can affect the output. Omitting an input buys a fast wrong build.

Parallelism is another separate lever. Once function or package boundaries provide enough independence, workers can process different units. Giving each worker its own temporary storage avoids some sharing. Scheduling and synchronization still cost something, and tiny units may not justify it. I would first find out how much time one worker spends doing work that could simply be removed.

The version I would build first#

For a restricted expression language, I would start very close to the companion: one lookahead token, known inputs, direct emission, and explicit errors. Then add delayed constants or a small register cache only when the generated code warrants them.

For a larger language, I would probably accept a declaration pass and one compact typed representation per function. Keep inference mostly inside those boundaries. Compile modules against sufficient interface data. Pick a modest backend, and keep aggressive optimization out of the default development path until there is evidence it belongs there.

To assess that choice, measure a clean build, a no-change build, a function-body edit, and an exported-interface edit. Record wall time, CPU time, peak memory, and generated-code performance with the same workload and build settings. A comparison starting from Wasm must say so; a comparison that ends at an object file must say that too.

The final trade is how much compilation work the program will repay while running. A short test and an overnight simulation justify different decisions. Tiered systems can make that decision per function; V8's dynamic-tiering write-up describes using execution activity to trigger further Wasm optimization. That is a later layer, with its own cost and complexity.

What I like about the simple designs is that I can account for their work. This token is read once. This operation emits here. This function's temporary data goes away now. This dependency does not need reading again. That gives me something concrete to improve before reaching for another thread, another cache, or a faster machine.