prime-sieve: The Sieve Runs Backward Now, and It's 19% Faster

TL;DR

In July we published “a 35-line prime sieve beats Rust” — 49,604 vs 49,374 passes/5s on an Ice Lake Xeon. This week we re-ran the identical comparison on fresh dedicated-CPU droplets and lost. Rather than accept “different silicon” as the answer, we kept digging and found two real defects in std/field, neither of them in the sieve program itself. The same faithful.k algorithm — re-spelled to current syntax, 32 lines now — measures:

Passes per 5 seconds, single-threaded, interleaved runs, every binary validating the same 78,498 primes. The Rust side is PrimeRust/solution_1 built with its own workspace’s LTO profile — the same target as July. Koru is ahead in all 18 measured rounds on all three droplets.

Two honest caveats up front: Ice Lake, the silicon the original post was measured on, is still unmeasured — no droplet draw landed an 8358 this week, so we can’t tell you what the new numbers look like on the claim’s own hardware. And the bigger fix is about twenty lines of sequencing logic; nothing in it is ours by physics — it’s ours by being in std/field.

Losing first

The re-measurement was supposed to be a footnote — check the claim still holds, move on. On the first Cascade Lake droplet, Koru ran 33.6k against Rust’s 42.7k: a 27% loss. Two more droplets (another 8280, an 8168) said the real gap was ~6.5%, which is where it stayed while we eliminated the obvious: build flags (byte-identical stage-D invocation, both eras), libc vs musl (+3%), -mcpu tuning (+1%), and the generated code itself — Koru’s dense marker is instruction-for-instruction identical to Rust’s SSE-vectorized reset loop, and its sparse marker is tighter (12 instructions per iteration against Rust’s 21). We were emitting better code for the same algorithm and still losing. That was the part that wouldn’t sit.

Fix one: the memset that wasn’t the platform’s memset

Every pass allocates and zeroes a fresh 62.5 KB field. std/field did that with Zig’s @memset — which Zig lowers to the compiler_rt memset bundled inside the binary, a local symbol that shadows glibc’s. Rust’s binary calls memset@GLIBC, which on these chips is an AVX2/ERMS-tuned ifunc dispatch. Zeroing through libc (bzero when the target links libc, which every Koru binary does) moved x86 from ~6.5% behind to within ~1% of Rust — near-parity, honestly not a win, and we said so.

Fix two: a sweep should start where the last one left the cache

The sieve makes ~170 full passes over the same field per run — one marker per prime. Every marker ran forward, head to tail. On a 32 KB L1D, the field is twice the cache: by the time a forward sweep reaches the end, the beginning is gone. Each of the ~170 sweeps streamed the entire field from L2, every time, and so did Rust’s — which is why the two ran neck and neck.

The fix: markers take a direction, and the field alternates it. Forward, then backward, then forward — each sweep begins on the half of the field the previous one left resident. It’s gated on the field actually exceeding the machine’s L1D, queried at runtime (sysconf on glibc, sysctl on Darwin, off when unknown) — on the Apple Silicon laptop the 62.5 KB field fits the 64 KB L1D, alternation stays off, and the machine runs exactly as before. Nothing is hardcoded per-architecture; the condition is measured from the box.

Same program, same markers, same instruction streams — different order of visitation. +19%.

The program

The submitted entry, reproduced — every number above came from exactly this:

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

const { sieve_bits: 500000 }

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

pub tor run { deadline: i128 } -> i64

tick = std/time:now(): 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, from: 2 * i * (i + 1), stride: 2 * i + 1, limit: 499999)
        | done |> std/field:free(f) |> @L(l.deadline, passes: l.passes + 1)
| expired e -> e

std/time:now(): t0 |> run(deadline: t0 + 5000000000): n |> std/field:new(bits: sieve_bits)
    | field g |> std/time:now(): t1 |> for(1..500)
        ! each i |> std/field:test(f: g, i): pv |> if(pv == 0)
            | then |> std/field:mark-multiples(f: g, from: 2 * i * (i + 1), stride: 2 * i + 1, limit: 499999)
        | done |> std/field:count-zeros(f: g, lo: 1, hi: 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(f: g)

It is the July program, re-spelled to current syntax: event is tor now, arguments carry labels, interpolation is {{ }}. The algorithm, the structure, and the algorithm=base,faithful=yes,bits=1 output are untouched — and it’s 32 lines now, not 35: err became a ?! panic branch (allocation can only fail on OOM, where a panic is the honest exit), so the two forced | err _ |> _ arms are gone — and the final validation chain wraps across four lines instead of running off the page. Nothing about it knows the markers reverse.

Where the fix lives is the point

The direction change is ~20 lines. It is portable: Rust’s extreme resetters could adopt it tomorrow and the gap would narrow. What isn’t portable is where ours landed — inside the mark-multiples transform in std/field, which generates each call site’s specialized marker code. faithful.k’s algorithm did not change by a line (the re-spelling is syntax drift, not a benchmark edit); the optimization shipped in the standard library, and the program went from ~7% behind to 19% ahead because of what its calls now compile to. Rust’s equivalent change would live in the benchmark’s own crate.

And std/field is not a sieve-shaped novelty — it is the bitset you reach for to build a Bloom filter, and Bloom filters in 2026 are unglamorous load-bearing plumbing: cache admission, dedupe, rate limiters, join filters. Anything that bulk-marks a field larger than its machine’s L1D now gets alternating sweeps for free, measured against the runtime cache size rather than hardcoded to this benchmark’s 62.5 KB. That is the difference between a standard-library optimization and a benchmark tweak wearing a stdlib badge — the gates are machine-measured, and the next caller doesn’t have to look like a sieve at all.

This is also the answer to the question we get asked most: how can a language that emits Zig beat hand-tuned code? Because emitting Zig is not writing Zig. Those 32 source lines produce 25,522 lines of generated Zig (~1.1 MB) — one fully-unrolled, mask-table-baked marker function per stride, in both sweep directions, plus the dispatch LUTs that pick among them. Nobody writes that by hand in any language; and when the direction fix landed, none of those ~25k lines were edited — they were re-generated from a ~110-line diff to one transform. The program a human maintains is small and declarative; the program the machine runs is specialized past the point a human would ever reach. That is the whole pitch of the toolchain, made literal in one file size.

The other side

Worth saying plainly what that crate is, because it’s good work. PrimeRust/solution_1’s fastest entry — bit-extreme-hybrid — generates one fully-unrolled dense resetter per prime up to 129, exactly the same idea as mark-multiples: a small declarative call site backed by a compile-time facility that stamps out specialized marking code. The difference is where that facility lives. Theirs is helper-macros, a 307-line procedural-macro crate that needs syn, quote, and proc-macro2 — a separate crate in a separate compile-time dialect. Ours is a ~tor transform inside std/field, no dependencies, and the transform’s output is ordinary Zig that any reader of the emitted code can audit.

The counted comparison, re-measured this week against the same workspace we benchmarked (commit 5c7347a):

* Same caveat as July: Rust’s binary bundles all eight CLI-selectable variants plus orchestration; ours is one fixed program. The raw byte counts are real; the asymmetry travels with them.

And the closing irony, in fairness: the direction alternation that won this round would slot into their reset_flags in about twenty lines too. It just has nowhere to live but the benchmark itself.

What’s still open

• Ice Lake 8358 is unmeasured. The July claim’s own silicon never came up in this week’s droplet draws. Skylake-SP and Cascade Lake are adjacent cores; Ice Lake’s L1D is 48 KB and its memory pipeline is deeper, so +19% plausibly travels — but “plausibly” is not a measurement, and we’re not reporting it as one.
• Descending sweeps cost 6–9% on ARM when active. Measured, not explained. The runtime gate keeps it off there, which is the right call either way, but the cost itself is unexplored.
• The memset fix exposed a downstream effect we haven’t fully characterized: the slow zeroing cost ~1% of cycles directly, yet fixing it recovered ~6.5% — the state it left lines in appears to tax the sweeps that follow. Inferred, not measured.

The drag race’s door is where the maintainer left it — open “for later.” Nothing about this week’s work changes the eligibility objection; it just makes the technical case harder to wave at. The numbers, the protocol, and the binaries are all written down in koru-benchmarks/results/droplet/2026-10-03_droplet_c-2_sieve_revisit.json, same as always.