The Continuation Is a Lane: How We Stole Bend's Calling Convention

This morning’s post ended with Bend winning the ackermann row at 65.2ms — sequentially, no forks — against our 145.8 and C’s 133. The interesting part was never that Bend won; it was how. BendRT doesn’t use the native call stack for recursion. It runs everything through explicit continuations — each function is a segment, each “call” pushes a frame onto a heap stack and jumps, each “return” pops a continuation id and dispatches. Deep non-tail recursion, which is the entire ackermann workload, is exactly where that shape pays.

So we did what you do when someone shows you a better calling convention: we read its generated C, disassembled both sides to find out where the money was, and stole it.

The tax, itemized

A native non-tail call on ARM pays about eight memory operations per level. Push the callee-saved registers — tak spills eight, because x, y, z, and two intermediate results all have to survive the nested calls — push the frame and link register, bl, move the result, restore everything, ret. The callee-saves exist for exactly one reason: values the caller still needs must survive a call that owns every register.

The flat version writes those same values into a lane — a fixed-width slot, [continuation-id][live values…] — with one sequential store, bumps a pointer, and jumps. The “return” is one load and an indirect branch the predictor nails, because there are only about three distinct targets. Then LLVM fuses the whole tail-call chain back into a store-loop: stp; add; subs; cbnz. The continuation stops being a stack frame and becomes a bump pointer.

The embarrassing discovery: Koru was already halfway there. Tail self-calls have emitted as __koru_self_loop reentry for months — tail call as jump, no frame. The gap was exclusively non-tail calls. Flat emission is just “apply reentry thinking to non-tail calls”: the callee’s result goes to a lane-continuation instead of a return address.

The honest failure

The first implementation was wrong in an instructive way. We emitted the explicit continuation stack as ordinary structured control flow — one big loop, lanes pushed and popped, a dispatch switch. Oracle-green on every kernel. And on tak it ran 64.3ms — slower than the native path it replaced.

The reason is register pressure. One big function holds eight-plus live variables across the dispatch and spills them; Bend’s architecture gives each resumption point its own function, which means its own register file. The prototype spike had already proven the segment model at ~38ms; we’d just chosen the wrong way to express it. So the emitter was rewritten to generate what Bend actually does: separate segment functions, a uniform (sp, r0..rN) signature, @call(.always_tail) between them.

Three more measured fixes closed the rest of the gap: variable-width frames cost ~25% versus a uniform lane stride (found by morphing the spike, not by guessing); resumption segments provably can’t overflow the stack, so only the evaluator’s pushes needed a check; and a PROT_NONE guard page replaced even that check — overflow now faults exactly like a native stack overflow, at zero hot-path cost, while Debug builds keep a real @panic diagnostic.

One number we have to retract in print: an earlier spike figure claimed ~12× on tak. It was measured at tak(24,16,8); the suite runs tak(32,16,8), where the honest margin is 1.2×. The 12× is what a wrong input buys you.

The numbers

Measured under the suite’s own protocol — koruc build --release=fast in a fresh temp dir, oracle-gated (wrong output is excluded, not timed), hyperfine -N warmup-3/min-10, persisted to the board:

Three rows Koru now wins outright — including Bend’s signature row, beaten with its own mechanism, 2.8× under Bend’s best sequential number. Bend’s trick minus Bend’s runtime: no tagged Nat arithmetic, no term graph, no fork/join bookkeeping. The emitted path is about sixty lines of Zig and a lazily-mmapped stack.

The row that didn’t move is the point

fib didn’t change, and that’s the feature, not a bug.

fib’s continuation combines — fib(n-1) and fib(n-2) both return into a + b. Every leaf return is a dynamic br whose target alternates, and that loses to the hardware return-address-stack predictor that ret exploits for free. We measured it: flat fib runs ~20% slower than native. So the emitter doesn’t flat-emit it.

That’s the selection rule, and it’s the part Bend can’t do: the compiler picks the calling convention per handler, by proof of shape. A non-tail self-call whose continuation leads to another self-call — chained recursion: ack, hanoi, tak — gets lanes. A continuation that only combines results — fib, pascal, coins — keeps the native stack, which is genuinely excellent at exactly that job. We compiled all nineteen Koru kernels on the board: exactly those three qualify. Bend has one convention and pays for it everywhere, which is a chunk of why its fib sits at 73.8 against our native 28.7.

There’s no |flat spelling, and there won’t be. emitSelfTailReentry doesn’t have a |reentry keyword either — when the emitter can prove a shape is faster and semantics-identical, it just emits it. Asking the programmer to predict a runtime tradeoff the compiler has strictly more information about is how you get wrong answers in source.

The honest costs

• Debuggability. A crash inside flat tak produces __koru_seg_k2 → br x4, not a backtrace. Lane chains are invisible to debuggers and profilers.
• Scope. Scalar arguments, single-return flows, self-recursion only, arity bounded by the register file. Mutual groups are mechanically possible — the ABI doesn’t care which segment jumps where — but the gate stays conservative until the pins are wider.
• It doesn’t close the board. binarytrees, exprtree, listops — Koru’s missing cells — are combining recursion over ADTs. Flat doesn’t touch them; they want arena allocation, a different mechanism entirely.

Where the lane stack goes next

The substrate is the interesting residue. Bend uses the same structure for bend-par — a lane is exactly the unit a work-stealing scheduler ships between cores, which is where its tak got to 52.9. Ours now exists, correctly laid out. Whether a seq/task path over it is a spike or a wrong turn is a measurement we haven’t run yet.

The deeper takeaway from the whole Bend evaluation is the selection rule. Bend’s contribution wasn’t a faster stack — it was proof that making the continuation explicit data beats the platform ABI by a constant factor on the shapes where continuations are long-lived chains. Koru now emits each convention where it provably wins, per handler, in the same compilation. One language, two calling conventions, zero keywords.

Committed as e67673d0a on koru main: emitter + both pins + the frag. The full regression board came back 1790/1790; 320_148 asserts chained recursion emits segments, 320_149 asserts combining recursion stays native — the boundary is pinned in both directions. The benchmark board’s koru column is persisted with dirty: true provenance from the uncommitted tree, and the numbers now match the committed code exactly.