A 35-Line Prime Sieve Now Beats Hand-Tuned Rust

TL;DR

We submitted a Koru prime sieve to Dave Plummer’s Primes drag race. It was closed the same day, on new “language eligibility” rules written in reaction to our PR — while PrimeBrainFuck, PrimeINTERCAL, PrimeWhitespace, PrimeLOLCODE, and PrimeBallerina remain in the same repo, unaffected. Rather than argue about it, we fixed a real bug in our own toolchain and made the submission unimpeachable instead. The numbers, all bare metal, same dedicated-CPU x86_64 box, single-threaded, n=20 unless noted:

Runtime — passes/5s, mean, Welch’s t-test against a ~2.0 bar for 95% confidence

Size and footprint — vs. PrimeRust/solution_1

* Rust’s binary bundles all 14 sieve variants PrimeRust/solution_1 implements, plus CLI parsing and both threading runners. Koru’s is one fixed program. Not a clean apples-to-apples comparison on scope — the raw number is real, the asymmetry travels with it.

Two more things worth knowing before the story: the win against Rust and Zig came from a dense-marker widening that helps x86_64 (+5.72%) but regresses ARM by 2.65% — an honest, still-open gap, not hidden. And fixing the one fair criticism the maintainer raised — our allocation was stack-placed, not genuinely dynamic — surfaced a real bug in Koru’s own runtime allocator (404,478 page-faults/3s from Zig’s DebugAllocator eagerly munmap-ing on every free), independent of any comparison to anyone. Every number above is reproducible on a fresh box with the exact recipe we wrote down while we were at it.

Two posts ago we said our marker generation ran dead even with hand-tuned Zig. One post before that we admitted our prettiest sieve was a vectorization dead end. We’ve been honest about this the whole way, so here’s the next honest thing: we submitted, and we got closed the same day.

What actually happened

We opened PR #1077 against Dave Plummer’s Primes drag race — a Sieve of Eratosthenes in Koru, single-threaded, faithful=yes. The maintainer was thoughtful and specific in the response, and this isn’t a story about someone being a jerk. He reviewed the contributing guidelines, decided they weren’t explicit enough about new language submissions, updated them the same day, and closed us under the new text:

“The Primes repository is intended to compare implementations in mature, established programming languages with an identity and usage history outside this benchmark… Accepting submissions in immature or purpose-built languages… would put the repository on a path where maintainers have to evaluate an open-ended stream of new experimental languages, custom compilers, generated code paths, and benchmark-specific optimizations.”

Reasonable-sounding policy. Here’s the wrinkle: PrimeBrainFuck, PrimeINTERCAL, PrimeWhitespace, and PrimeLOLCODE are already in that repo. None of them have an independent user base. None of them have general-purpose, non-benchmark usage — they’re esoteric languages; not having that is the entire point of what they are. They’re not going anywhere, and nobody’s asking them to leave. The rule, as written, would exclude them too if applied evenly. It doesn’t reject them, because they got in before the rule existed. It rejects only what comes next.

We’re not arguing the maturity point — it’s true, and we said so in the PR ourselves: Koru is young and pre-release. What we don’t buy is that a standard requiring pre-existing independent use is a standard new languages can ever pass, while the esoteric-language shelf is permanently exempt from ever needing to.

We’re not litigating it further here. We’re doing the other thing: making the technical case so complete that “not yet” is the only honest objection left standing.

The one fair criticism, and fixing it for real

Buried in an otherwise generous review was a real, correct technical point. Our faithful=yes submission allocated its sieve buffer fresh every pass — std/field:new … std/field:free, inside the timed loop, same as every other faithful entry. But Koru’s compiler does escape analysis, and for a compile-time-constant buffer size, it was stack-placing the allocation instead of actually calling the allocator. Same trick the JVM and Go do for non-escaping objects — except the faithfulness rule specifically wants the sieve state allocated dynamically at runtime, and a comptime-sized stack array is not that, no matter how legitimate the optimization is in general. We said so ourselves in the PR description. The maintainer read it correctly.

The fix is one line. Instead of a literal:

std/field:new(bits: 500000)

we introduce the size as a named constant:

const { sieve_bits: 500000 }
...
std/field:new(bits: sieve_bits)

Koru’s escape-analysis heuristic only stack-places a field when its size argument is a bare integer literal at the call site — an identifier doesn’t qualify, so this one change routes every allocation through the real, general-purpose heap path. No more wrinkle. No comptime trick standing between us and “genuinely dynamic.”

Here’s the whole thing, the actual submitted program, all 35 lines of it:

import std/io
import std/time
import std/field
import std/control

const { sieve_bits: 500000 }

pub event tick { deadline: i128, passes: i64 }
| live { deadline: i128, passes: i64 }
| expired i64

pub event run { deadline: i128 } -> i64

tick = std/time:now()
| t n |> if(n < deadline)
    | then => live { deadline, passes }
    | else => expired passes

run = #L tick(deadline, passes: 0)
| live l |> std/field:new(bits: sieve_bits)
    | field f |> for(1..500)
        ! each i |> std/field:test(f, i): pv |> if(pv == 0)
            | then |> std/field:mark-multiples(f, 2 * i * (i + 1), 2 * i + 1, 499999)
        | done |> std/field:free(f) |> @L(l.deadline, passes: l.passes + 1)
    | err _ |> _
| expired e -> e

std/time:now()
| t t0 |> run(deadline: t0 + 5000000000): n |> std/time:now()
    | t t1 |> std/field:new(bits: sieve_bits)
        | field g |> for(1..500)
            ! each i |> std/field:test(g, i): pv |> if(pv == 0)
                | then |> std/field:mark-multiples(g, 2 * i * (i + 1), 2 * i + 1, 499999)
            | done |> std/field:count-zeros(g, 1, 500000): c |> std/io:eprint.ln("validated primes: {{ c + 1:d }}") |> std/io:print.ln("korulang;{{ n:d }};{{ @as(f64, @floatFromInt(t1 - t0)) / 1000000000.0:f }};1;algorithm=base,faithful=yes,bits=1") |> std/field:free(g)
        | err _ |> _

We ran it. It validated 78,498 primes. And it was 26% slower.

The bug that was actually in our own allocator

That 26% sent us looking, and we found something we didn’t expect: it wasn’t the honesty tax we assumed it’d be. It was a real bug in a design decision we’d made a few days earlier.

Koru’s runtime allocator — the one every new/free in the standard library goes through — was backed by Zig’s GeneralPurposeAllocator with safety checks on, specifically so every produced Koru binary leak-checks itself at exit. Deliberate choice, good intentions. What we hadn’t checked closely enough: that allocator is a debug tool, not a throughput allocator. Its free() does this, unconditionally:

bucket.freed_count += 1;
if (bucket.freed_count == bucket.allocated_count) {
    // ...unlink the bucket...
    self.backing_allocator.rawFree(page[0..page_size], page_align, @returnAddress());
}

The instant a bucket’s last live slot is freed, the whole backing page gets munmap‘d — immediately, regardless of size class, regardless of any config tuning. Our sieve’s pattern is “allocate one buffer, use it, free it,” every single pass. That means every pass was a fresh mmap. We measured it with perf stat -e page-faults: 404,478 page faults per 3 seconds, roughly 20% of wall-clock time spent in the kernel just mapping and unmapping the same amount of memory over and over. This isn’t a tunable inefficiency — eager unmap-on-empty is why the allocator is good at catching use-after-free (a freed page reliably segfaults on next touch). It was never built to be fast.

We swapped the backing allocator to a real general-purpose one — std.heap.c_allocator, the same libc malloc/free every C, C++, and (transitively, through their own CAlloc) Zig entry in this benchmark already uses — wrapped in a plain outstanding-allocation counter that replaces the debug allocator’s leak tracking. Same guarantee (“a leaking Koru binary fails loudly”), different mechanism. Page faults dropped to 174 per 3 seconds. Sys time dropped to zero.

That fix alone closed a ~24% gap that had nothing to do with the sieve, or Rust, or Zig — it was a mistake in our own toolchain, one we’d have shipped in every Koru program’s runtime, sieve or not. We ran the full regression suite before and after: 826/895 passed, zero new regressions. It’s on origin/main now, and every Koru binary compiled from here forward gets it for free.

One of two backends — Zig today, and we’re not the only ones who do this

Koru’s current backend is Zig — std/field:mark-multiples is a compile-time transform, and it emits ordinary Zig, which the Zig compiler then optimizes exactly as hard as it optimizes anyone’s hand-written Zig. Zig isn’t the only target: Koru also has a working JavaScript backend (the same transforms, a different lowering — std/table’s comprehensions and std/declarations’s const both already ship both |zig and |js variants of the same template, one source, two targets). Compiling to a host language is the mechanism, not an apology for one.

It’s also not remotely unusual for this specific repository. PrimeNim compiles to C (nim c -d:release, then a C compiler does the rest). PrimeTypeScript compiles to JavaScript (npm run build, then Node runs the output). PrimeHaxe targets whatever backend you point it at — C++, JVM, C#, JS, more. All three are already in this benchmark, uncontested, on exactly the same “compiles to another language” shape we have. If “generates code in a host language” were disqualifying on its own, a third of the eligibility argument against us would apply equally to entries nobody’s proposing to remove.

So: on the actual technical merits, here’s where the Zig backend stands. Two posts ago the honest number was “dead even” with PrimeZig’s own best entry — before the dense-marker widening we did to chase Rust. We went back and re-measured rather than assume the old number still held. On the same dedicated-CPU hardware, bare metal, 20 runs each, current build:

Koru’s faithful entry beats Zig’s official solution_3 “best singlethreaded base runner” by 7.75% — 49,281.20 vs. 45,734.90 mean passes/5s, Welch t=166.52, the two twenty-sample distributions not overlapping at all (Koru’s lowest run beats Zig’s highest). The widening that helped against Rust helped here too, more than we expected — we hadn’t actually checked until we sat down to write this paragraph, caught ourselves about to publish a stale number, and went and got the real one instead.

Rust — the harder climb, and where we caught our own mistake

PrimeRust’s solution_1 is the actual hard target. It implements fourteen different sieve strategies side by side, and the two fastest single-threaded ones — bit-extreme-hybrid and bit-unrolled-hybrid — use a procedural macro to generate one fully-unrolled reset function per prime, from 3 up through 129, falling back to a sparse resetter above that. That’s the same idea as our mark-multiples transform: a small, declarative call site, and a separate compile-time facility that stamps out the specialized code. Koru’s version needs no external dependency — it’s a native compiler feature. Rust’s version pulls in syn, quote, and proc-macro2, three real third-party crates, because writing a proc-macro by hand without them is close to unbearable.

Our own dense-marker generation topped out at primes under 64 — a boundary set by the register width of a u64 word, not by anything principled. Once we saw Rust’s macro carrying its dense range all the way to 129, we widened ours to 128 (a deliberate power-of-two step, not a copy of their exact number) and measured, rather than assumed, what it bought us:

+5.72% on x86_64, dedicated CPU, 20 runs, means of 46,919.65 → 49,604.10 passes/5s, the two distributions not even overlapping. Same change on Apple Silicon: −2.65%. A real regression, not noise — the two architectures disagree, and right now DENSE_LIMIT is a flat constant that’s correct for one and wrong for the other. We don’t have a per-architecture codegen-profile mechanism yet. That’s an honest gap, not a footnote we’re hiding.

Then we found out we’d been sloppy. PrimeRust/solution_1 is a Cargo workspace, and its real release profile — opt-level = 3, lto = true, codegen-units = 1 — lives in the workspace root Cargo.toml, not in the member crate we’d copied over. We’d built and measured Rust without its own declared optimization settings for most of a session, which inflated our apparent lead. We caught it, copied the missing file, confirmed via the actual rustc invocation (not the Cargo.toml alone) that LTO was really being applied, and re-ran everything.

The corrected numbers, same protocol, 20 runs each, bare metal, dedicated CPU:

Smaller margin than our flawed measurement showed, and the honest one. Both differences are real by Welch’s t-test (t > 12 in both cases, against a bar of ~2 for confidence) — not a rounding error, just not the bigger gap we briefly, wrongly, reported to ourselves.

The size of it

None of the above required writing more code. faithful.k is 35 lines. The library machinery behind it — std/field, the whole general dense-bitset module, not just the sieve’s slice of it — is 709 lines, and it’s genuinely general: it also backs a Bloom filter elsewhere in our test suite, nothing sieve-specific about it.

Rust’s equivalent, stripped of the shared 1,271-line CLI/harness/test scaffolding that supports all fourteen variants, is 744 lines (unrolled.rs + unrolled_extreme.rs + the external helper-macros crate) — plus three third-party dependencies we don’t need.

The generated Zig for our 35 lines is genuinely large: 638KB, 14,038 lines, of which roughly 92% is the mechanically-explained marker/dispatch code (one unrolled line per residue class, for 63 different primes — that’s just what “generate one function per stride, up to 127” produces when you actually do it). Compiled and stripped: 171,464 bytes. Rust’s binary, properly built with LTO, stripped: 1,129,544 bytes — about 6.6× larger, though that number carries a real caveat we won’t let travel without it: Rust’s binary bundles all fourteen variants plus CLI parsing plus threading orchestration. Ours is one fixed program. Not fully apples-to-apples, and we’d rather say that than let the number stand alone.

That same asymmetry shows up again in actual runtime memory, not just disk size. Peak RSS (/usr/bin/time -v, 20 runs each, same hardware): Koru averages 1,484.2 KB, Rust averages 2,833.6 KB — Rust uses roughly 1.9× the peak memory Koru does. Both programs allocate the identical 500,000-bit sieve buffer per pass, so this isn’t an algorithmic difference; it’s the same baseline-footprint story as the binary size, measured a different way and landing in the same place.

Compile time, same hardware, three runs each:

Koru compiles roughly 2.7× faster cold and 3× faster warm, despite a heavier-looking pipeline (Koru’s compiler recompiles its own backend, including the whole standard library, before it even touches your program). Rust’s cold number is dominated by building syn/quote/proc-macro2 from scratch — the same dependency weight showing up a third time, after the line count and the binary size.

One more thing we found, that isn’t in this post

While chasing all of this we confirmed Koru has a second compile-time codegen capability we haven’t talked about yet: table comprehensions (std/table) — from(name) { x over lo..hi }, baking a const array at compile time from a closed range, plus sum and gaps for reducing and deriving wheel-sieve residue tables. It’s the same family as everything above — regex compiled to a DFA, a kernel abstraction compiled to fused SIMD, a router compiled away entirely, a marker compiled per-stride — just aimed at data instead of control flow. We didn’t fold it into this particular optimization; it deserves its own post, not a paragraph tacked onto this one.

Where this leaves us

We are not accepted into the drag race today, on grounds that are honest about Koru’s age and inconsistent about everyone else’s. We didn’t spend the time since then arguing about that. We spent it making the submission harder to dismiss: a real allocator bug found and fixed, a faithfulness wrinkle closed for good, and a performance story that — on the hardware that actually matters, measured the way we’d want anyone to check our own homework — has us ahead of the two most aggressively hand-tuned single-threaded solutions that exist for this exact problem, in 35 lines, with zero dependencies.

The door’s open for later, in the maintainer’s own words. We’ll be back when “later” arrives. In the meantime, the numbers are real, they’re reproducible on a fresh box with the recipe we wrote down while we were at it, and they don’t need Brainfuck’s help to make the point.