Going Faster by Doing It Once, All at Once

August 3, 2026 • 11 min read

A single compile of a single file used to take 15.7 seconds and allocate 29.5 gigabytes.

One file. Not a whole project, just the one file. And about 97% of that CPU time went to the garbage collector, so for most of those fifteen seconds the compiler wasn’t really compiling. It was producing garbage fast enough to keep another thread busy cleaning up after it.

That was the worst case of a habit the parser had picked up everywhere: redoing work it had already done. Inside a single type query. Inside a single expression. And across files, where the same module got tokenized, parsed and compiled from scratch dozens of times in a single startup.

Most of this post is about that last one, because fixing it meant rebuilding the parser around the dependency graph instead of the file. We’ll come back to the 29 gigabytes at the end.

The workload

Filtrera is an embedded language, and that changes what “parsing performance” even means here.

A host application doesn’t compile one program. It compiles thirty of them at startup, all small scripts, and most of them import the same five or six modules.

Hand that to a parser that treats every program as its own separate job and the arithmetic gets ugly fast. Thirty programs, five shared imports, nothing shared between them: that’s 150 module compiles to load thirty scripts that between them reference five modules. The standard library gets rebuilt from scratch every time anyone asks a question, despite its source not having changed since the process started.

That’s the workload Filtrera actually has, and it’s the one the old pipeline was worst at.

The pipeline

Three stages:

source ──▶ tokens ──▶ CST ──▶ compile ──▶ executable

Tokenization carries indentation state, since Filtrera is indentation-sensitive, so there’s no simple scan to be had. The CST parser is a backtracking combinator parser: it tries alternatives in order and rewinds the input when one fails. The third stage does scoping, type inference and generic specialization in one walk. There’s no separate typechecking pass, which surprises people. Types settle during that walk.

One more property matters, and the whole design ends up resting on it. Imports are top-level statements, and their targets are literals you can resolve statically. So you can read a module’s imports straight off its CST. You don’t have to compile it, and you don’t have to know that any other module exists.

What was serial

Imports used to resolve depth-first, right in the middle of a compile. The compiler would hit an import statement and stop. Then it tokenized and parsed the dependency, compiled it, recursed into that module’s imports, and only then picked up where it left off.

None of that survived the call. Every module got rebuilt on the next parse.

Modules with nothing to do with each other compiled one after another anyway, because there was only ever one thread of control. And if a module had to come off disk, that thread sat and waited for the disk rather than tokenizing something else in the meantime.

Where the parallelism is

Not in the inner loop, and it’s worth being upfront about that.

A tokenizer carrying indentation state doesn’t split across threads. A backtracking parser is sequential within a source by construction. You could fight either of those, but you’d be rewriting the parser to win back a slice of one file.

The graph is a different story. Two facts:

• Tokenizing and CST-parsing a module depends on nothing. It needs its own source text and that’s the whole list.
• Compiling a module depends only on its direct imports. Unrelated modules don’t matter, and neither does anything downstream.

Two facts, two phases.

Phase A: discovery

Discovery is a pool of workers draining a queue of module URIs. Every worker does the same small thing:

dequeue URI
fetch source          (may be I/O, other workers keep running)
tokenize, CST-parse
read import URIs off the CST
enqueue each import

Nothing has to happen in any particular order. Cycles don’t stall it, because a URI that’s already been seen doesn’t get queued again. It just runs until the queue is empty and every started task has finished, and what falls out the other end is the entire dependency graph with every module already tokenized and parsed.

The deduplication is where the real leverage is, and it hinges on a distinction that’s easy to miss. The obvious cache answers one question: have I finished this module? The useful cache answers a different one: is anyone already working on it?

So every cache entry is a task, created lazily and atomically on first request. Three workers asking for the same module all get a reference to the same task. They don’t kick off three copies of the work and race each other to write the same answer. The cache stores the computation, not just the result.

That’s what makes the sharing work across whole programs rather than only across imports. Thirty programs importing the same module never coordinate, never check in with each other, and have no idea the others exist. They ask the cache, and the module compiles once. Those 150 compiles become 5.

Two smaller details. Modules the host registers natively, which is how the standard library arrives, get dropped into the cache as finished entries before discovery even starts, so they never enter the graph at all. And the occasional import whose target isn’t statically known skips discovery and resolves later during phase B. Slower path, still correct.

Phase B: wave compilation

Now compile in dependency order, which means Kahn’s algorithm, used as a scheduler rather than as a sort. Nothing builds a topological ordering up front:

inDegree[uri]  = number of direct imports of uri
ready          = queue of URIs with inDegree 0

worker:
  dequeue uri
  compile uri                (imports already finished)
  for each rdep that imports uri:
    if --inDegree[rdep] == 0:
      enqueue rdep

The waves never exist as actual objects. There’s no level 0 followed by level 1. A module simply becomes ready the moment its last dependency finishes, wherever that happens to be.

That’s the whole reason to schedule instead of sort. Say one module takes ten times longer than its neighbours. Sort the graph into levels and everything at that level ends up waiting behind it. Schedule it and everything that doesn’t depend on it carries on past. The critical path sets the floor, and nothing else has to wait.

Program roots sit in the same graph, since a program depends on its imports plus the host’s globals. Roots and modules all compile in one wave, and results get written back by index so the caller sees them in the order it asked for.

Cycles

Discovery finishes whether or not the graph has cycles, which deduplication guarantees for free.

Then, once the ready queue drains, any module whose in-degree never reached zero is sitting in a cycle. Depth-first detection tells you about the first cycle it trips over; in-degree hands you all of them at once. Everything outside the cycles still compiles fine.

The bug that was safe by accident

Parallelism didn’t really introduce a bug here. It withdrew a guarantee nobody had bothered to write down.

Here’s the shape of it. Compiling an importer mutates state that lives inside a dependency. A module exports a generic function, an importer calls it with concrete types, and that call site triggers specialization. The specialized entry then gets appended to the dependency’s scope. The same dependency that had already finished compiling. The one that was done.

In a serial world this was perfectly safe, for exactly one reason: only one compile ever ran at a time. That was luck, not design.

Turn on the wave scheduler and two problems show up immediately.

The first is a straightforward data race. Two modules in the same wave both import the same function and both specialize it, so both mutate the same registration objects. The dictionary appends aren’t synchronized, and the counter that mints the specialization’s name isn’t atomic. That corrupts the dictionary, or quietly hands two different specializations the same identity. The race had been sitting there unreachable since the day it was written, purely because nothing ever ran two compiles at once.

The second problem is older than the parallelism, which was the more uncomfortable discovery. A dependency’s exported symbol table got captured as a snapshot the moment that dependency finished. But specializations kept being added to its live scope afterwards, by importers that compiled later. So a lookup for a specialized export could consult a table that predated the symbol and report, with total confidence, that it didn’t exist. The root-module path rebuilt its table from the live scope; the dependency path didn’t. Those two had been disagreeing for a long time, and nobody had asked them the right question.

Both are fixed now. Registration is thread-safe, and dependency symbol tables are read live.

What’s left is the assumption underneath, which is the part worth taking away: a module’s compile output is immutable once produced. Most compilers believe some version of that, usually without ever writing it down. It stops being true the second specialization crosses a module boundary, and the only thing hiding it from you is whether anything ever runs at the same time.

Determinism

A parallel compiler with unstable diagnostics is worse than a slow one, because now your test suite is a coin flip.

Results come back in the order they went in, whatever order they actually finish in, because they’re written by index.

Diagnostics get collected per module and then sorted by a total key. Tests comparing sets of errors don’t care about any of this. Tests comparing the order of errors see the same order every run, no matter how the waves interleaved.

There’s a progress stream too, and its main design constraint is that events are milestone-grained. One per module discovered, one when the graph resolves, one pair around each compile. Per-statement events would fire millions of times and cost more than the work they were describing, which rather defeats the point. Reporting is fire-and-forget, and a handler that throws gets swallowed. A progress bar has no business failing a build.

The numbers

BenchmarkDotNet on net10.0, two warmup runs and ten iterations. The baseline is the old host pattern (one independent parse per program, nothing shared) and it runs in the same session as the new one, so the ratio is a real before and after rather than a comparison against a fondly remembered old commit.

Workload	Before	After	Ratio	Allocated
8 programs, shared imports	9.90 ms	1.88 ms	0.19	8.4 → 4.7 MB
32 programs, shared imports	41.8 ms	6.46 ms	0.16	33.5 → 17.2 MB

5.3× faster at 8 programs, 6.5× faster at 32, with allocations roughly halved.

The gap growing with program count is exactly what the design predicts: shared work is paid for once, so every program you add costs less than the one before it. Attaching a progress handler moves the numbers by less than the measurement noise. A single source with no imports takes a fast path that skips the task machinery entirely, and the older benchmarks show no drift there.

The twenty-nine gigabytes

Which brings us back to the file that took 15.7 seconds.

That one had nothing to do with files. A generic function’s output type was derived by recompiling the entire function body, and meanwhile the type machinery asks for output types constantly. Assignability asks. Equality asks. Hashing, intersection and printing all ask. And since a nested handler’s output type is itself a generic function containing more handlers, one query at the top would recursively recompile everything underneath it. Then the next query did the same thing again.

The profiler counted 38,274 output-type queries in one compile, which between them triggered over 300,000 body compilations. An exponential blowup hiding behind a property getter.

The fix is a memo keyed on a stripped snapshot of the resolved input. A dictionary field, basically. That’s the whole change.

Metric	Before	After	Improvement
Time	15,700 ms	250 ms	~60×
Allocated	29,583 MB	145 MB	~200×
Gen0 collections	3,709	18	~200×

Sixty times faster, two hundred times less garbage, and the test suite passed unchanged. That last part is also the correctness argument: inference has already settled by the time that descriptor exists, so every derivation after it is pure. Caching a pure function changes how often you compute it and nothing else.

An earlier attempt at caching nearby had gone nowhere, and the contrast is the actual lesson. Memoizing type relations saved nothing, because the probe was a deep hash plus a deep equality check and it cost about what the comparison cost. When the probe costs what you save, a cache is just overhead. Here the probe is one hash and the saving is a recursive recompile, so it pays for itself thousands of times per compile.

Two more

Token-directed dispatch. The expression parser used to try ten alternative parsers in sequence for every link in every chain, backtracking after each failure. Dispatching on the leading token brings that down to one or two, which is worth 1.84× on small expressions and 2.45× on large programs.

The first attempt at that used a dictionary mapping token kinds to parsers, and it ran ten times slower than the linear scan it replaced. The lookup overhead plus a per-call array allocation cost more than the nine parser attempts it was supposed to skip. What shipped is a plain switch, which the JIT turns into a jump table.

Then there’s the one that didn’t work at all. Sub-scope creation eagerly flattens the ancestor symbol chain, which looks exactly like the sort of redundant work this whole post is about. Two replacements were prototyped, immutable dictionaries and lazy parent-chain walking, and both came out slower by 15 to 18% on large programs. Turns out the flatten isn’t waste: it’s prepaying for symbol lookup, and lookups outnumber scope creations by a wide margin. Moving cost off a rare operation and onto a common one isn’t an optimization, whatever it looks like on a whiteboard.

What it was

Every fix here is the same fix at a different size. A type derived again after it had already been derived. Parsers tried again when they couldn’t possibly match. A module compiled again ninety seconds after the last time, and due to be compiled again shortly after that.

Redundant work is good at surviving because it never actually fails. It returns the right answer, it passes the tests, and it just quietly charges you for it: in milliseconds, in gigabytes, and in a startup bar that takes longer than anyone expects.

The parser does each piece of work once now. And where it can prove the order doesn’t matter, it does several of them at the same time.