You Can't Rewrite Your Way Out of Big-O
Spinel is Matz's ahead-of-time<br>Ruby-to-C compiler, and this month it acquired an unusual asset: a<br>40,000-line application it could not compile. When<br>Roundhouse transpiles<br>Lobsters for the Spinel target, it emits a<br>~370-file tree of plain Ruby — the app, its views desugared into<br>methods, and the reified framework runtime. Two weeks ago, pointing<br>Spinel at that tree produced a single core pinned at 100% and no output;<br>we killed the run after 200 seconds and filed<br>spinel#3115. For this<br>post I checked out that exact commit and let it run to completion on<br>the tree every number below is measured on: 202 seconds .
Today the same command takes 8.7 seconds on Spinel's master, and 5.3<br>with the last pull request<br>of the series, currently in review. Thirty-eight times faster, two<br>days of work, five upstream PRs — and one recurring villain. But the<br>story starts a month earlier, with a rewrite.
Chapter one: the romance tax
In mid-June, Matz<br>wrote<br>(translation mine):
I reimplemented Spinel in C. It took a full week this time.<br>Self-hosting is a compiler writer's romance, but running whole-program<br>type analysis over a compiler that had grown to 80,000 lines meant<br>builds took about twenty minutes, and productivity had fallen.
The repository's design note says the same thing in engineering terms:<br>the analyzer and code generator were written in Ruby and compiled by<br>Spinel itself, so every change paid for ~93k lines through the whole<br>pipeline into multi-megabyte C, whose optimized link dominated the dev<br>loop — with every inference change risking a stage-2 self-host cascade<br>on top. The remedy was a week of rewriting the compiler directly in C,<br>landed as a single 275-commit batch. It worked: the compiler now builds<br>in seconds, and an entire class of self-hosting hazards vanished.
Here is the detail I find delicious. Matz's twenty minutes was<br>whole-program analysis over 80k lines. Our 200 seconds was the same<br>analysis — now in C — over a 40k-line tree. Half the input, roughly a<br>quarter of the time: that is what a quadratic looks like when you meet<br>it twice. The June rewrite and the July fixes were responses to the<br>same curve, and the rewrite, for all its real benefits, carried the<br>curve along — translated faithfully, line by line, into a faster<br>language.
Chapter two: one villain, five arrests
What followed was two days of profile-guided whack-a-mole, except the<br>mole was the same mole every time: a per-item helper that rescans the<br>whole table . Cheap at test-suite scale, invisible at 5,000 lines,<br>quadratic death at 40,000.
fix<br>what was rescanning what<br>compile
#3115 (Matz's fix)<br>a desugar pass rescanned every node per call receiver<br>202s → 82s
#3123<br>an unfrozen scope index degraded every method lookup to a linear scan; a hash-default helper rescanned all writes per query<br>82s → 45s
#3134<br>the fixpoint itself — see below<br>45s → 13s
#3149<br>the same pass #3123 fixed, two loops further out: every unresolved call name probed every class, and a per-argument helper rescanned every node<br>12.8s → 7.9s
#3192 (in review)<br>the post-fixpoint tail: a backstop rescanned every node per scope; a narrowing pass walked the table four times per candidate local<br>7.3s → 5.3s
The centerpiece is<br>#3134. Spinel's inference<br>runs ~59 analysis passes in a loop, up to 128 iterations, until nothing<br>changes. Instrumenting that loop showed something better than a<br>bottleneck: it had never converged on any non-trivial program.<br>Every compile of every real tree ran all 128 iterations with the<br>"changed" flag still set, and terminated because the cap said so — the<br>backstop quietly became the exit. Two passes were reporting change they<br>hadn't made: one measured its progress against its own per-iteration<br>reset instead of against the previous iteration, and one kept<br>re-deriving a raising method's return type as void while<br>override-dispatch unification kept widening it back, a ping-pong<br>neither side could win. Fix both and the loop converges in eleven<br>iterations. Even the tiny blog fixture had been silently burning the<br>full 128.
If you maintain anything with a fixpoint and an iteration cap, I<br>commend the experiment to you: log the iteration count. The cap will<br>make non-convergence invisible for exactly as long as you don't look.
Two things about how this went that I want on the record. Matz merged<br>these at a pace that kept the series moving — most within a day, the<br>convergence fix included. And the automated reviewers earned their<br>seats: between them they caught a real matching gap for classes nested<br>inside renamed classes and a real crash-ordering bug in my own<br>allocation guards — both confirmed, both fixed, both credited in the<br>threads.
The dead ends, measured
Honesty requires the failures. Going in, my leading theory was that<br>Spinel's analyze was slow because it re-derives what Roundhouse<br>already knows — Roundhouse emits RBS signatures for the whole tree,<br>and Spinel has a --rbs flag (which, in a nice bit of...