The Compiler Writes the Marker

A couple of days ago, on this blog, we ended a post about a prime sieve with a promise. The fast marking lived in a hand-written library primitive, and we said the honest next move wasn’t to hand-write more SIMD — it was to make the compiler generate the specialized marker, the same trick Koru already pulls for regex and for the kernel family. We wrote: “We’re not there yet. But we can see the road, and we know what’s parked at the end of it.”

We drove the road. This is what was parked at the end of it.

The marking becomes a transform

The marking call is std/field:mark-multiples(f, from, stride, limit) — “set every bit at from, from + stride, from + 2·stride, … up to limit.” In the sieve that’s “cross out every multiple of this prime,” and the call reads the same as it did last time. What changed is what’s behind it.

mark-multiples is a [comptime|transform] now. At each call site the compiler reads the access pattern and emits a specialized native marker — a fully-unrolled, residue-class function per stride, with the bit-masks baked in as compile-time immediates and dispatched through a function-pointer table. The program says which numbers to cross out; the compiler writes how to cross them out fast. (The generated marker is a tight unrolled scalar loop, the kind the backend — LLVM — is then free to auto-vectorize; the unrolling and residue-specialization are ours.) It’s the same move the language already makes for a regular expression (read by a compile-time transform, compiled to a DFA) and for an arithmetic kernel (a fixed vocabulary fused into SIMD) — now pointed at a strided bit-fill. The readable thing and the fast thing are, again, the same source.

The whole program we race

Here it is — the entire benchmarked entry, not a snippet. It looks busier than the eight-line sieve from last time, and that’s the contest’s doing, not the sieve’s: the drag race wants a self-timed five-second loop that re-creates the sieve from scratch every pass, plus a final validation pass. The sieve itself is still the four lines around mark-multiples; the rest is protocol.

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

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: 500000)
    | 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: 500000)
        | 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 _ |> _

The loop is the #L … @L label-fold — a conditional back-edge that threads the deadline and the pass count until std/time:now() reports five seconds elapsed. Each pass allocates a field, sieves it, and frees it — and that per-pass free isn’t bookkeeping you can skip: new issues a free-obligation that lives in the field’s type, so forgetting it is a compile error, not a production leak. It’s also what lets the compiler prove the allocation never escapes and stack-place it — the faithful per-pass allocation that, in the fast path, never touches the heap at all.

The marking — the thing this whole post is about — is that one mark-multiples call. Behind it, the compiler has written the sixty-four residue-specialized, immediate-masked markers. You wrote “cross out the multiples.” It wrote the specialized marker — the unrolled, baked-mask scalar loop that the backend then vectorizes for you.

But the dev machine lied

There was a catch the last post never had to face. We develop on Apple Silicon — ARM, NEON. The drag race runs on x86 Linux. So we built what the contest actually requires: a Docker image that compiles the Koru compiler from source and then compiles the sieve inside it. The first time we ran it on a real x86 box, it didn’t validate. It segfaulted.

Two compiler bugs, both invisible on the Mac:

• An x86-64 result-location miscompile that silently dropped a struct field, so the generated code referenced a .source that was never written.
• A duplicate-std link that handed the backend two copies of os.environ — one initialized, one garbage — and the emitted pipeline read the garbage one. macOS routes getenv through libc and never touches the global; Linux reads it directly and dies.

Neither reproduces on the machine we wrote them on. “Green on the dev box” said nothing about the target, and the only way to learn that was to build on the target. We fixed both; the container validated 78,498 primes. The exercise had already paid for itself before we timed a single pass — it surfaced two real bugs that would otherwise have shipped silent.

The fix that looked perfect and was slower

Then the part worth the whole post. One of the models we collaborate with had an idea, and it was a good idea: force the dense marker to use explicit 512-bit @Vector writes — exactly what the Zig champion does. It read the disassembly, cross-compiled the markers to the Xeon’s AVX-512 target, and proved it: the scalar loop that LLVM had been auto-vectorizing unevenly now emitted a clean 512-bit vorps %zmm for every stride. By every static measure, the codegen got unambiguously wider. It looked like a clean win.

We ran it. It was three percent slower.

The dense marking is memory-bandwidth-bound — it’s streaming the bitset — so wider vectors buy nothing the bandwidth wasn’t already giving, while the explicit-vector path adds a mask-table load the scalar version never paid. The disassembly was a mirage. The only instrument that wasn’t fooled was the clock.

We almost shipped it. That’s the honest center of this whole thing, and it’s the rule we keep relearning: measure the full system on the real hardware, and when the static picture flatters you, trust the clock instead. A fix that’s prettier in the assembly and slower on the wall is still a regression.

The cheat we caught ourselves taking

The next idea worked — and we threw it away anyway.

There’s a crossover in the marker: small primes get a dense whole-buffer sweep, large primes get a sparse jump-to-multiples. We had it at stride 64. Move it to 256 and the sieve jumped +14%, suddenly within a couple percent of the champion.

But that 256 is a lie. It’s tuned to the fact that this sieve’s buffer fits in L2 cache, so the dense sweep stays fast far past where the math says it should. A ten-million sieve — buffer spilling to DRAM — would want a lower crossover, and our hardcoded 256 would make it slower. We’d have a great drag-race number bought with a constant that’s wrong for every sieve but the one in the benchmark. That isn’t “our compiler is fast.” It’s “we tuned a magic number for the contest.” We measured it, kept it just long enough to learn from it, and deleted it.

The real fix: a register spill

So we did the honest thing and went looking for why the sparse marker was slow — not how to route around it. We turned a small fleet of agents loose, each on its own machine, each under one rule: nothing counts until it’s faster on the clock. One of them profiled Koru against the champion, side by side, and found it.

It wasn’t the algorithm. Both spend roughly 80% of their time in exactly the same place — marking the large, sparse primes. But Koru was running 1.7× the instructions and 1.9× the memory loads for identical cache misses. The profiler annotated the hot loop and pinned the cause: Koru’s sparse marker kept eight bit-masks and eight byte-offsets live across the loop — sixteen values against the x86’s ~fourteen general registers — so the offset array spilled to the stack and reloaded every single iteration. The champion didn’t spill, because its masks were compile-time constants baked as immediates, leaving the registers free.

The fix is that same idea, generalized. The bit a marker sets in lane k is fixed once you know two residues — (from mod 8, stride mod 8). There are sixty-four such pairs. So the transform now emits sixty-four residue-specialized markers, and in each one the eight masks are compile-time immediates. The mask array disappears; the offsets fit in registers; the spill is gone. No magic constant, no field-size tuning — every caller of mark-multiples gets it, whether it’s a sieve, a Bloom filter, or a bitmap index. It’s a codegen fix, which is exactly the right place for it to live.

Where it lands

Measured on our own hardware — single-threaded, faithful (each pass re-creates the sieve from scratch), algorithm=base, one bit per flag, interleaved back-to-back against the hand-tuned Zig reference (solution_3), both validating 78,498:

The honest summary is not “Koru beats hand-tuned Zig.” It’s parity-class, and hardware-dependent: a couple percent ahead on one Intel generation, a hair behind on another. The improvement over our own baseline (+15–19%) is the same on both chips — that part is solid and reproducible. And these are our numbers on our boxes. The drag race’s official figures come from the maintainers’ benchmark machines, which we now have to earn. We’re submitting; the verdict is theirs to render, and we’ll report it whichever way it goes.

One thing said plainly, because it matters for the “faithful” label: Koru’s per-pass allocation is stack-placed by the compiler’s escape analysis — the source allocates a fresh sieve every pass, and the compiler proves it doesn’t escape and puts it on the stack, the same optimization Go and Java perform. We believe that’s faithful. The maintainers may read the rule differently, and that’s their call.

The point

The last post argued the durable artifacts were never the sieve — they were the primitives, std/table and std/field. Still true, and now there’s a sharper version of it: the marking is no longer in the library as hand-tuned Zig. It is generated by the compiler, one specialized function per stride, from a four-argument call. The day a high-level language’s compiler generates a specialized marker in the same league as a human expert writing it by hand — unrolled, residue- specialized, immediate-masked, and tight enough for the backend to vectorize cleanly — that was the thing parked at the end of the road. It’s parked in std/field now.

And the habit is still worth more than any number. We almost shipped a disassembly that lied. We almost shipped a constant tuned for the contest. Both times the same discipline caught it: build on the real target, measure the whole system, and when a result flatters you, look harder. The drag race was never the point. It was the instrument honest enough to tell us when we were fooling ourselves — and good enough to show us, twice, exactly where the speed actually went.