intertwingly

Spinel is Matz's ahead-of-time Ruby-to-C compiler, and this month it acquired an unusual asset: a 40,000-line application it could not compile. When Roundhouse transpiles Lobsters for the Spinel target, it emits a ~370-file tree of plain Ruby — the app, its views desugared into methods, and the reified framework runtime. Two weeks ago, pointing Spinel at that tree produced a single core pinned at 100% and no output; we killed the run after 200 seconds and filed spinel#3115. For this post I checked out that exact commit and let it run to completion on 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 with the last pull request of the series, currently in review. Thirty-eight times faster, two days of work, five upstream PRs — and one recurring villain. But the story starts a month earlier, with a rewrite.

Chapter one: the romance tax

In mid-June, Matz wrote (translation mine):

I reimplemented Spinel in C. It took a full week this time. Self-hosting is a compiler writer's romance, but running whole-program type analysis over a compiler that had grown to 80,000 lines meant builds took about twenty minutes, and productivity had fallen.

The repository's design note says the same thing in engineering terms: the analyzer and code generator were written in Ruby and compiled by Spinel itself, so every change paid for ~93k lines through the whole pipeline into multi-megabyte C, whose optimized link dominated the dev loop — with every inference change risking a stage-2 self-host cascade on top. The remedy was a week of rewriting the compiler directly in C, landed as a single 275-commit batch. It worked: the compiler now builds in seconds, and an entire class of self-hosting hazards vanished.

Here is the detail I find delicious. Matz's twenty minutes was whole-program analysis over 80k lines. Our 200 seconds was the same analysis — now in C — over a 40k-line tree. Half the input, roughly a quarter of the time: that is what a quadratic looks like when you meet it twice. The June rewrite and the July fixes were responses to the same curve, and the rewrite, for all its real benefits, carried the curve along — translated faithfully, line by line, into a faster language.

Chapter two: one villain, five arrests

What followed was two days of profile-guided whack-a-mole, except the mole was the same mole every time: a per-item helper that rescans the whole table. Cheap at test-suite scale, invisible at 5,000 lines, quadratic death at 40,000.

The centerpiece is #3134. Spinel's inference runs ~59 analysis passes in a loop, up to 128 iterations, until nothing changes. Instrumenting that loop showed something better than a bottleneck: it had never converged on any non-trivial program. Every compile of every real tree ran all 128 iterations with the "changed" flag still set, and terminated because the cap said so — the backstop quietly became the exit. Two passes were reporting change they hadn't made: one measured its progress against its own per-iteration reset instead of against the previous iteration, and one kept re-deriving a raising method's return type as void while override-dispatch unification kept widening it back, a ping-pong neither side could win. Fix both and the loop converges in eleven iterations. Even the tiny blog fixture had been silently burning the full 128.

If you maintain anything with a fixpoint and an iteration cap, I commend the experiment to you: log the iteration count. The cap will 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 these at a pace that kept the series moving — most within a day, the convergence fix included. And the automated reviewers earned their seats: between them they caught a real matching gap for classes nested inside renamed classes and a real crash-ordering bug in my own allocation guards — both confirmed, both fixed, both credited in the threads.

The dead ends, measured

Honesty requires the failures. Going in, my leading theory was that Spinel's analyze was slow because it re-derives what Roundhouse already knows — Roundhouse emits RBS signatures for the whole tree, and Spinel has a --rbs flag (which, in a nice bit of circularity, originated from this project in May) to seed its inference with them. The plan was a grand one: a "trust mode" where declared signatures replace inference wholesale.

Measurement was unkind to the plan, twice. First: seeding turned out to be nearly inert — 6% — which led to #3145 (merged): the most common signature token Roundhouse emits was silently unparsed, and the collision-renamed classes at the heart of the framework — ActiveRecord::Base itself — never matched their seeds at all. Worth fixing for its own sake; it made a small fixture compile six times faster. But second, and more damning for the theory: Spinel can dump its own inferred signatures for a whole program, and feeding those back in simulates perfect coverage for free. On the post-convergence compiler, perfect signatures were worth 0.3 seconds. The seductive hypothesis — "just give it the types" — was off by an order of magnitude, because once the fixpoint actually converges, signatures mostly prevent churn that no longer exists. The trust-mode design is shelved, feasibility-studied to death by its own probe. Two days of algorithmic fixes beat the architecture I walked in intending to build.

The baseline that kept us digging

Why did I believe, at 82 seconds and again at 45 and again at 13, that there was more? Because Roundhouse compiles the same application — ingest, whole-program type analysis, Rails lowering, emit — in 0.6 seconds. A second implementation of comparable analysis over the same input is a powerful thing: it converts "this feels slow" into "this is demonstrably 100× off," and it keeps saying so until the gap closes.

The comparison needs one honesty footnote in each direction. Spinel is fed more program than Roundhouse reads — Roundhouse takes 21k lines of application source and models Rails internally; it hands Spinel 60k lines with the framework reified into plain Ruby. Per line of input, the gap today is about 3×, not 9× — and pre-series it was about 115×, which is why the baseline's verdict of keep digging held up four times running. The remaining 3× is honest work still on the table: one more known table-rescan (flagged in #3115 itself, which predicted its own sequels in a list of sibling helpers we're still working through), and the genuinely-iterative floor a fixpoint has to pay.

Good enough, for now

Lobsters now compiles to a native binary in about the time a Rails app boots. That's good enough to stop — for lobsters. The Mastodon tree will be five times larger, and if this series taught anything, it's that every 5× finds the next scan that was invisible at the last scale. I expect to be back. The difference is that next time it's a playbook, not an investigation: log the iteration count, profile per pass not per function, and when a helper loops over the table, ask what index would make it stop.

And the moral, which I promised the title: the June rewrite did not fix the scaling, because rewrites can't — an O(N²) survives translation into any language you like. But it would be exactly wrong to conclude the rewrite was a mistake. Every fix in this series was found with second-long compiler rebuilds and clean native profiles — the dev loop the rewrite bought. Matz fixed "slow to build the compiler." That made it tractable, a month later, to fix "slow to compile applications." You can't rewrite your way out of big-O. But the rewrite can build the workbench you'll be standing at when big-O comes due.

Roundhouse is open source: dual-licensed MIT / Apache-2.0. Issues and discussion welcome.