Four squeezes on the faithful sieve

The faithful category of the prime-sieve drag race has one hard rule: every pass gets a fresh, zeroed buffer. No reuse of a populated buffer, ever. Our faithful=yes entry obeys — std/field:new and free on every pass — and it paid a measurable tax for it: the reuse-sieve ran meaningfully faster on the same machine, and the gap was the thing to explain.

This tax lives right next to a bug we already fixed once. In A 35-Line Prime Sieve Now Beats Hand-Tuned Rust, the single biggest win over Rust and Zig wasn’t algorithmic at all — it was discovering that Koru’s runtime allocator was backed by a debug allocator whose free() eagerly munmap‘d the backing page the instant a bucket emptied, costing 404,478 page faults per 3 seconds and roughly 24% of wall-clock time to the kernel, on every single Koru program. Swapping the backing allocator closed that gap outright. This post is about what’s left over even with that fix in place: faithful=yes still pays for a real new/free round-trip every pass, by rule, on top of an allocator that’s now genuinely fast. Same family of bug, one layer deeper — check the allocator before the algorithm, every time.

So we ran four squeezes in parallel, each in its own worktree, each attacking a different hypothesis. Here is what they found, including the one that found nothing — that one carries the lesson.

Two allocator strategies, one conclusion

The first two experiments both guessed the same culprit — per-pass allocation — and attacked it two different ways.

The LIFO bump region noticed that new/free are last-in-first-out within a pass, so a module-level fixed-buffer region over a one-time 8 MB allocation can rewind to empty after every pass. Freed pages never round-trip to the OS; the same resident pages serve every pass. When the region can’t fit a request, it falls back to the leak-metered allocator, so correctness and leak detection are never lost.

The block pool kept a process-lifetime freelist instead: new() recycles a same-sized block and re-zeroes it into a logically fresh buffer; free() returns the block to the pool. One resident block instead of an allocator churn per pass.

Both preserve faithfulness — every pass still gets a fresh, correctly-sized, zeroed buffer; only the page churn underneath goes away, which the drag-race rules explicitly permit (a faster allocator is fine; reusing a populated buffer is not). And both, as measured in their own experiment runs (arm64 macOS, 1M sieve, 1 thread, the official 5-second protocol, machine under concurrent load), lifted the faithful entry from roughly 11–13k passes/sec to roughly 14–16.5k — to the reuse-sieve’s own ceiling. The entire faithful-versus-reuse gap was per-pass allocation cost. All of it.

The vectorization squeeze: beautiful assembly, no speedup

The third experiment rewrote the generated mark-multiples marker to emit explicit @Vector(4, u64) OR-stores with baked mask vectors instead of scalar stores. It worked, in the sense that matters least: the stride-3 marker went from six lane-shuffle ops (LLVM’s autovectorizer realigning a misaligned period) to zero — pure paired 256-bit loads, ORs, and stores, confirmed in the disassembly.

And the sieve got no faster. Fourteen interleaved A/B runs gave overlapping medians, with the vector build slightly behind — its generated code was 2.5× larger, and the instruction-cache pressure appears to have eaten the per-marker gain. The marking loop was already well-vectorized by LLVM and was never the bottleneck; the allocator was.

This is the experiment worth writing down. It produced objectively cleaner codegen, it was measured honestly, and it lost. “The compiler already did this for you, and your clever version is bigger” is a result you only get by measuring — the disassembly said victory while the stopwatch said no.

The probe that pointed at the real feature

The fourth squeeze changed no compiler code at all. It hand-edited the generated Zig — a Stage-D probe — to stack-allocate the field, fresh and zeroed each pass, and measured the same reuse-ceiling lift as the allocator squeezes. That’s not a shippable change; it’s a proof that the language-level version is worth building: escape analysis driven by the phantom obligation that already proves the field never escapes the pass, lowering heap allocation to stack allocation where the proof holds. The obligation system already carries the lifetime proof; this probe measured what cashing it in is worth.

Where the work lives

None of the four merged. The two allocator strategies conflict with each other (both rewrite std/field’s new/free), so landing one means a clean-machine bench-off between them — a separate session’s work. The vectorization rewrite is a documented negative result. The probe’s real feature is the escape-driven allocation arc, which is its own thread.

All four survive as archive tags on the koru repo — archive/squeeze-arena-alloc, archive/squeeze-pool-freelist, archive/squeeze-marking-microopt, archive/squeeze-escape-local — full diffs, full commit messages, full measurement records, reachable forever without cluttering a single branch listing.

The summary a future session should start from: in the faithful sieve, allocation was the whole gap; marking was never the problem; and the honest negative result cost one worktree and saved the next person a week.