The Wheel Was the Wrong Optimum

This is really a story about two primitives. Koru had just grown a comprehension surface — std/table, which turns a one-line description of a table into a const baked at compile time — and a dense bitset, std/field. Neither was built for a sieve. The question was whether they were any good: not pretty in a demo, but fast and reusable under real load. And the most honest way to find that out is to take the most-benchmarked program on earth and race it against people who have spent years making it fast.

So we entered a prime sieve in Dave Plummer’s “Software Drag Racing”: count the primes below 1,000,000, run for five seconds, report passes per second. There is a leaderboard; there are hand-tuned SIMD C++ entries on it. But the leaderboard is the instrument, not the point — the point is what the exercise taught us about the primitives. What follows is the real arc — the wins, the part where we were fooling ourselves, the climb back, and the eight-line program it all collapses into. The most useful thing we learned wasn’t a trick: it was that our most elegant sieve was the wrong sieve, and the only way to find that out is to measure the whole system against a real opponent.

A wheel from one line — and the idea behind it

Koru recently grew a comprehension surface, std/table. The idea is one Koru keeps returning to: a restricted, closed sub-language, read by a compile-time transform, and baked to a native artifact. Regex does it for strings — a regular expression is read by a [comptime|transform] and compiled to a DFA table. The kernel family does it for arithmetic — a fixed vocabulary fused into scalarized SIMD. std/table does it for data: a comprehension, evaluated at compile time, emitted as a const.

It isn’t a new keyword. from, keep, gaps, sum are ordinary library events, and the comprehension composes like everything else. You write what you want; the compiler runs it at compile time and bakes the result into the binary.

The prime sieve’s classic optimization is a wheel: skip the multiples of the small primes entirely. The mod-30030 wheel — the numbers coprime to 2·3·5·7·11·13 — has 5,760 residues. primesieve.cpp ships that as a hand-written static array because nobody types 5,760 numbers by hand. In Koru it’s one line:

from(wheel) { x over 0..30030 | keep gcd(x, 30030) == 1 }

from generates, keep filters with a guard the compiler evaluates at compile time (here a gcd and a comparison), and the result — every residue coprime to 30030 — lands as a const in the binary. There’s a sibling, gaps, that derives the step-table a wheel actually walks — the cyclic differences between consecutive residues, which primesieve also ships hand-written:

gaps(steps) { x over 0..30030 | keep gcd(x, 30030) == 1 }

Two tables that are infeasible to write by hand, both one line, both computed and checked at compile time. We sieved with the wheel, and it was genuinely good — it beat a naive C sieve, and it beat a hand-rolled mod-6 Koru sieve. We were thrilled. We started measuring against the C++ field.

The part where we were wrong

Here is the number that should have triggered suspicion, and did:

ours (mod-30030 wheel):   ~3,700 passes/sec
C++ "base" entries:       ~1,100–1,400 passes/sec

Three times faster than C++! Except — no. The C++ “base” entries are odds-only sieves: algorithm=base. Ours uses a big wheel. We were comparing a wheel against a non-wheel and calling it a language win. That’s not a fair fight; it flatters us.

So we found the right opponent: solution_5, the recently-optimized entry that uses SIMD. Same machine, single-threaded, same limit:

ours (mod-30030 wheel):   ~3,700 passes/sec
cpp solution_5 (SIMD):   ~14,000 passes/sec

We were 4.3× slower than the real champion. The “we beat C++” story was a measurement artifact — a flattering comparison we’d have looked foolish repeating. The gut-check that caught it is worth saying out loud: if a number comes out that far in front without us having to work for it, we’re probably measuring the wrong thing.

Why the pretty sieve loses

This is the lesson, and it surprised us. We profiled and proved, in the assembly, two facts:

• A contiguous word-OR — data[i] |= mask[i] over consecutive 64-bit words — auto-vectorizes to NEON. The compiler turns it into 128-bit vector ORs for free.
• A scattered bit-set — data[m >> 6] |= 1 << (m & 63) at computed positions m — does not, and cannot. Nothing tells the compiler the writes are structured.

Now look at what a wheel does. It marks composites at scattered, non-uniform positions — that’s the whole point, it skips around to do less work. The wheel makes marking sparse and scattered, which is exactly the shape SIMD cannot touch. The big wheel and vectorization are opposed. Our prettiest idea was a vectorization dead end.

solution_5 resolves the tension the opposite way from us: it uses the minimal wheel — odds-only, mod-2 — precisely to keep marking dense, then annihilates that dense marking with SIMD. The wheel we were proud of was the wrong local optimum. The fast basin is “barely wheel at all, but vectorize the marking.”

The climb

Once you know which basin you’re in, the path is mechanical — and we walked it the same way each step: prove the shape in an isolated probe (assembly and clock), confirm it beats the baseline on the full workload, then wire it in and race back-to-back against solution_5. No step shipped on a microbenchmark.

The marking primitive lives in std/field:strike. We rebuilt it four times — the last by a small fleet of research agents we turned loose on the problem:

1. Word-wise stepMask marking. For odds-only storage, every prime p has a uniform bit-stride of p. Precompute the per-phase word masks, build the cyclic sequence, and OR one mask per 64-bit word instead of one set per bit.
2. 8-way-unrolled byte scatter for the large primes (stride ≥ 64), which turn out to dominate once the small primes are fast — they were ~74% of the marking.
3. Doubled cycle. The SIMD pair-loop had a scalar tail for odd cycle lengths (strides 3, 5, 7 — the densest primes). Doubling the mask cycle makes the loop length even: pure NEON pairs, no tail.
4. Quadrupled cycle. An agent reading the assembly found that @Vector(4,u64) lowers to paired ldp/stp — 256 bits per instruction — where the doubled @Vector(2,u64) used single ldr/str. Half the memory instructions per word. Another +8%. (Two sibling agents chased alignment and mask-caching and came back with honest nos — alignment is free on ARM NEON, and caching the masks is slower, because rebuilding them per call is what lets the compiler specialize each prime’s loop. Negative results, cheaply bought.)

Each one we measured back-to-back:

A pure-Koru sieve at 95% of the hand-tuned SIMD C++ champion — 3.6× faster than where this thread started. (Every row here shares one harness: ours, which counts and prints the primes on every pass. Hold that thought — the last 5% turns out to be hiding in that sentence, and we settle it at the end.)

The whole program

Here’s the thing readability is for. This is the fast sieve, in full — not a snippet, the entire program. Flip the tab to put the C++ champion’s sieve loop next to it:

import std/io
import std/field

std/field:new(bits: 500000)
| field f |> for(1..500)
    ! each i |> std/field:test(f, i): pv |> if(pv == 0)
        | then |> std/field:strike(f, 2 * i * (i + 1), 2 * i + 1, 499999)
    | done |> std/field:count-zeros(f, 1, 500000): c |> std/io:print.ln("{{ c + 1:d }}")
| err e |> std/io:print.ln("ERR {{ e:s }}")

void runSieve()
{
    const uint64_t limit = Bits.size();
    const uint64_t q = (uint64_t) sqrt((double)limit);
    const size_t qBi = q / 2;

    // Start with the first odd prime and discover all primes algorithmically
    uint64_t factor = 3;
    size_t bi = factor / 2;  // 3 -> 1

    while (factor <= q)
    {
        // Find the next prime by scanning for next zero bit
        size_t nextBi = Bits.find_next_prime_bit(bi, qBi);
        if (nextBi > qBi)
            break;
        factor = (uint64_t)(nextBi * 2 + 1);

        // Mark multiples starting from factor^2
        uint64_t start = factor * factor;
        Bits.mark_multiples(start, factor);

        bi = nextBi + 1;
    }
}

Eight lines. Allocate a bitset over the odd numbers; walk the candidates; if one is still unmarked it’s prime, so strike its multiples; count the survivors. It reads like the description of the sieve, because that’s what flow is for. The 2*i+1 is the only nod to odds-only packing. All the speed — the word-wise stepMask marking, the NEON, the 8-way scatter — lives behind strike, in std/field, where it belongs. The program stays the algorithm; the library carries the metal.

And notice what isn’t there: a free. new issues a free-obligation that lives in the field’s type — forget to discharge it and the program won’t compile; it’s a type error, not a leak you chase in production. But you don’t discharge it by hand either. The compiler inserts the free for you at the end of the field’s scope — we checked the emitted code, and there’s a free_event.handler(f) call sitting right after the print that we never typed. The obligation is enforced and auto-discharged: the eight lines are the whole program, leaks and all accounted for, by the type system.

And in case “348 lines” reads as hyperbole — it isn’t. This is mark_multiples, the C++ champion’s marking function, in full. It’s excellent code; it is also the thing our eight-line program calls one library word for:

    void mark_multiples(uint64_t start, uint64_t factor)
    {
        const uint64_t bitCount = (logicalSize + 1) / 2; // number of bits stored
        uint64_t b = start / 2;           // starting bit index
        const uint64_t bitStep = factor;  // step in bit domain
        if (bitStep == 0 || b >= bitCount)
            return;

        // For larger steps, one byte-level mark per hit is cheaper than sweeping every 64-bit word.
        if (UNLIKELY(bitStep >= BITSTEP_WORDWISE_THRESHOLD || bitStep >= 64))
        {
            uint64_t bi = b;
            const uint64_t step8 = bitStep * 8;
            uint8_t masks[8];
            size_t offsets[8];
            const uint64_t baseByte = bi >> 3;

            for (uint32_t i = 0; i < 8; ++i)
            {
                const uint64_t markBi = bi + bitStep * i;
                masks[i] = static_cast<uint8_t>(1u << (markBi & 7));
                offsets[i] = static_cast<size_t>((markBi >> 3) - baseByte);
            }

            uint64_t byteIndex = baseByte;
            const uint64_t groupEnd = (bitCount > bitStep * 7) ? (bitCount - bitStep * 7) : 0;

            while (bi < groupEnd)
            {
                uint8_t* ptr = array + byteIndex;
                ptr[offsets[0]] |= masks[0];
                ptr[offsets[1]] |= masks[1];
                ptr[offsets[2]] |= masks[2];
                ptr[offsets[3]] |= masks[3];
                ptr[offsets[4]] |= masks[4];
                ptr[offsets[5]] |= masks[5];
                ptr[offsets[6]] |= masks[6];
                ptr[offsets[7]] |= masks[7];
                byteIndex += bitStep;
                bi += step8;
            }

            while (bi < bitCount)
            {
                array[bi >> 3] |= static_cast<uint8_t>(1) << (bi & 7);
                bi += bitStep;
            }
            return;
        }

        // Byte and word geometry
        const size_t totalBytes = byteSize;
        const size_t fullWordCount = totalBytes / sizeof(uint64_t); // number of complete 64-bit words
        const size_t tailBytes = totalBytes - fullWordCount * sizeof(uint64_t);

        // Process full 64-bit words starting from the word containing the first bit
        size_t wordIndex = b / 64;
        const size_t startWordIndex = wordIndex;
        const uint32_t startPosAbs = static_cast<uint32_t>(b % 64); // first position to mark within start word
        const uint64_t delta = 64 % bitStep;          // (pos + 64) % bitStep
        const uint32_t advance = static_cast<uint32_t>(delta == 0 ? 0 : (bitStep - delta));
        uint32_t firstMod = static_cast<uint32_t>(startPosAbs % bitStep); // first position modulo bitStep within the word

        uint64_t stepMasks[64];
        for (uint64_t first = 0; first < bitStep && first < 64; ++first)
        {
            uint64_t m = 0ULL;
            uint64_t pos = first;
            while (pos + bitStep * 3 < 64) {
                m |= (1ULL << pos);
                pos += bitStep;
                m |= (1ULL << pos);
                pos += bitStep;
                m |= (1ULL << pos);
                pos += bitStep;
                m |= (1ULL << pos);
                pos += bitStep;
            }
            while (pos < 64) {
                m |= (1ULL << pos);
                pos += bitStep;
            }
            stepMasks[first] = m;
        }

        // Optimized word processing with bulk updates
        uint64_t* PRIMECPP_RESTRICT words = PRIMECPP_ASSUME_ALIGNED(reinterpret_cast<uint64_t*>(array), 64);

        // Handle partial starting word (if start bit not aligned to word boundary)
        if (startPosAbs && wordIndex < fullWordCount)
        {
            uint64_t mask = stepMasks[firstMod];
            mask &= ~((1ULL << startPosAbs) - 1ULL);
            words[wordIndex] |= mask;
            ++wordIndex;
            if (advance)
            {
                firstMod += advance;
                if (firstMod >= bitStep)
                    firstMod -= bitStep;
            }
        }

        // Precompute mask cycle for successive words; pattern repeats after bitStep words
        alignas(64) uint64_t cycleMasks[64];
        uint32_t cycleLen = 0;
        if (wordIndex < fullWordCount)
        {
            uint32_t mod = firstMod;
            const uint32_t cycleLimit = (advance == 0) ? 1u : static_cast<uint32_t>(bitStep);
            do
            {
                cycleMasks[cycleLen++] = stepMasks[mod];
                if (advance == 0)
                    break;
                mod += advance;
                if (mod >= bitStep)
                    mod -= bitStep;
            }
            while (mod != firstMod && cycleLen < cycleLimit);
        }

        if (cycleLen > 0)
        {
#if defined(PRIMECPP_VECTOR_AVX512)
            while (wordIndex + cycleLen <= fullWordCount)
            {
                size_t idx = 0;
                while (idx + 8 <= cycleLen)
                {
                    __m512i existing = _mm512_loadu_si512(reinterpret_cast<const void*>(words + wordIndex + idx));
                    const __m512i masks = _mm512_set_epi64(
                        static_cast<long long>(cycleMasks[idx + 7]),
                        static_cast<long long>(cycleMasks[idx + 6]),
                        static_cast<long long>(cycleMasks[idx + 5]),
                        static_cast<long long>(cycleMasks[idx + 4]),
                        static_cast<long long>(cycleMasks[idx + 3]),
                        static_cast<long long>(cycleMasks[idx + 2]),
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm512_or_si512(existing, masks);
                    _mm512_storeu_si512(reinterpret_cast<void*>(words + wordIndex + idx), existing);
                    idx += 8;
                }
                while (idx + 4 <= cycleLen)
                {
                    __m256i existing = _mm256_loadu_si256(reinterpret_cast<const __m256i_u*>(words + wordIndex + idx));
                    const __m256i masks = _mm256_set_epi64x(
                        static_cast<long long>(cycleMasks[idx + 3]),
                        static_cast<long long>(cycleMasks[idx + 2]),
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm256_or_si256(existing, masks);
                    _mm256_storeu_si256(reinterpret_cast<__m256i_u*>(words + wordIndex + idx), existing);
                    idx += 4;
                }
                while (idx + 2 <= cycleLen)
                {
                    __m128i existing = _mm_loadu_si128(reinterpret_cast<const __m128i_u*>(words + wordIndex + idx));
                    const __m128i masks = _mm_set_epi64x(
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm_or_si128(existing, masks);
                    _mm_storeu_si128(reinterpret_cast<__m128i_u*>(words + wordIndex + idx), existing);
                    idx += 2;
                }
                while (idx < cycleLen)
                {
                    words[wordIndex + idx] |= cycleMasks[idx];
                    ++idx;
                }
                wordIndex += cycleLen;
            }
#elif defined(PRIMECPP_VECTOR_AVX2)
            while (wordIndex + cycleLen <= fullWordCount)
            {
                size_t idx = 0;
                while (idx + 4 <= cycleLen)
                {
                    __m256i existing = _mm256_loadu_si256(reinterpret_cast<const __m256i_u*>(words + wordIndex + idx));
                    const __m256i masks = _mm256_set_epi64x(
                        static_cast<long long>(cycleMasks[idx + 3]),
                        static_cast<long long>(cycleMasks[idx + 2]),
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm256_or_si256(existing, masks);
                    _mm256_storeu_si256(reinterpret_cast<__m256i_u*>(words + wordIndex + idx), existing);
                    idx += 4;
                }
                while (idx + 2 <= cycleLen)
                {
                    __m128i existing = _mm_loadu_si128(reinterpret_cast<const __m128i_u*>(words + wordIndex + idx));
                    const __m128i masks = _mm_set_epi64x(
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm_or_si128(existing, masks);
                    _mm_storeu_si128(reinterpret_cast<__m128i_u*>(words + wordIndex + idx), existing);
                    idx += 2;
                }
                while (idx < cycleLen)
                {
                    words[wordIndex + idx] |= cycleMasks[idx];
                    ++idx;
                }
                wordIndex += cycleLen;
            }
#elif defined(PRIMECPP_VECTOR_SSE2)
            while (wordIndex + cycleLen <= fullWordCount)
            {
                size_t idx = 0;
                while (idx + 2 <= cycleLen)
                {
                    __m128i existing = _mm_loadu_si128(reinterpret_cast<const __m128i_u*>(words + wordIndex + idx));
                    const __m128i masks = _mm_set_epi64x(
                        static_cast<long long>(cycleMasks[idx + 1]),
                        static_cast<long long>(cycleMasks[idx + 0]));
                    existing = _mm_or_si128(existing, masks);
                    _mm_storeu_si128(reinterpret_cast<__m128i_u*>(words + wordIndex + idx), existing);
                    idx += 2;
                }
                while (idx < cycleLen)
                {
                    words[wordIndex + idx] |= cycleMasks[idx];
                    ++idx;
                }
                wordIndex += cycleLen;
            }
#elif defined(PRIMECPP_VECTOR_NEON)
            while (wordIndex + cycleLen <= fullWordCount)
            {
                size_t idx = 0;
                while (idx + 2 <= cycleLen)
                {
                    uint64x2_t existing = vld1q_u64(words + wordIndex + idx);
                    uint64x2_t masks = vdupq_n_u64(cycleMasks[idx]);
                    masks = vsetq_lane_u64(cycleMasks[idx + 1], masks, 1);
                    existing = vorrq_u64(existing, masks);
                    vst1q_u64(words + wordIndex + idx, existing);
                    idx += 2;
                }
                while (idx < cycleLen)
                {
                    words[wordIndex + idx] |= cycleMasks[idx];
                    ++idx;
                }
                wordIndex += cycleLen;
            }
#else
            while (wordIndex + cycleLen <= fullWordCount)
            {
                for (uint32_t j = 0; j < cycleLen; ++j)
                    words[wordIndex + j] |= cycleMasks[j];
                wordIndex += cycleLen;
            }
#endif
        }

        // Process multiple words at once when possible
        while (wordIndex + 3 < fullWordCount) {
            // Process 4 words at a time for better memory throughput
            const uint32_t absPos = (wordIndex == startWordIndex) ? startPosAbs : 0u;

            uint64_t mask = stepMasks[firstMod];
            if (wordIndex == startWordIndex && absPos)
                mask &= ~((1ULL << absPos) - 1ULL);

            words[wordIndex] |= mask;

            // Compute masks for next 3 words
            uint32_t mod1 = firstMod + advance;
            if (mod1 >= bitStep)
                mod1 -= bitStep;
            uint32_t mod2 = mod1 + advance; if (mod2 >= bitStep) mod2 -= bitStep;
            uint32_t mod3 = mod2 + advance; if (mod3 >= bitStep) mod3 -= bitStep;

            words[wordIndex + 1] |= stepMasks[mod1];
            words[wordIndex + 2] |= stepMasks[mod2];
            words[wordIndex + 3] |= stepMasks[mod3];

            wordIndex += 4;
            firstMod = mod3 + advance;
            if (firstMod >= bitStep)
                firstMod -= bitStep;
        }

        // Handle remaining words one by one
        while (wordIndex < fullWordCount)
        {
            const uint32_t absPos = (wordIndex == startWordIndex) ? startPosAbs : 0u;

            uint64_t mask = stepMasks[firstMod];
            if (wordIndex == startWordIndex && absPos)
                mask &= ~((1ULL << absPos) - 1ULL);

            words[wordIndex] |= mask;

            wordIndex++;
            if (advance)
            {
                firstMod += advance;
                if (firstMod >= bitStep)
                    firstMod -= bitStep;
            }
        }

        // Process tail bytes (if any) with a compact scalar loop in bit domain
        if (tailBytes > 0)
        {
            const uint64_t tailBitStart = static_cast<uint64_t>(fullWordCount) * 64ULL; // first bit index of tail word
            const uint64_t lastWordBits = bitCount - tailBitStart; // number of valid bits in tail word (1..63)
            if (lastWordBits)
            {
                uint32_t tailFirstAbs = 0u;
                uint32_t tailFirstMod = 0u;
                if (b >= tailBitStart)
                {
                    // We start inside the tail word
                    tailFirstAbs = static_cast<uint32_t>(b - tailBitStart);
                    tailFirstMod = static_cast<uint32_t>(tailFirstAbs % bitStep);
                }
                else
                {
                    // We progressed through full words; current firstMod targets the tail word
                    tailFirstAbs = 0u; // no need to clamp below 0
                    tailFirstMod = firstMod;
                }

                // Compute the mask for the tail word
                uint64_t mask = stepMasks[tailFirstMod];
                if (b >= tailBitStart && tailFirstAbs)
                    mask &= ~((1ULL << tailFirstAbs) - 1ULL);

                // Clamp to the actual number of valid bits in the final partial word
                if (lastWordBits < 64)
                    mask &= ((1ULL << lastWordBits) - 1ULL);

                // Byte-safe OR to make the mask for the tail bytes
                uint8_t* tailPtr = array + fullWordCount * sizeof(uint64_t);
                uint64_t m = mask;

                // Apply the mask to the tail bytes
                for (size_t j = 0; j < tailBytes; ++j)
                {
                    tailPtr[j] |= static_cast<uint8_t>(m & 0xFFu);
                    m >>= 8;
                }
            }
        }

So what is strike?

We’ve leaned on strike for the whole post without ever saying plainly what it does — and most people, us included, picture the slow version. Here’s the honest answer.

The call is std/field:strike(f, from, stride, limit), and in plain words it means: set every bit at from, from + stride, from + 2·stride, … up to limit. A strided run of bits, flipped on. In the sieve that’s “cross out every multiple of this prime.” The arguments strike(f, 2*i*(i+1), 2*i+1, 499999) look cryptic only because of odds-only packing: bit i stores the odd number 2i+1, so for the prime p = 2i+1 the first composite worth marking is p² — which lands at bit index 2i(i+1) — and successive odd multiples sit p bits apart, so stride = 2i+1. Start at p², step by p, stop at the limit. The classic sieve inner loop, in one call.

The naive way to do that is one memory write per bit: data[m >> 6] |= 1 << (m & 63), walking m by stride. That’s the scattered write we proved the compiler can’t vectorize — one store per crossed-out number. strike does something better, and it’s the entire reason it keeps pace with hand-tuned C++:

Because only odds are stored, the bits a single prime crosses out inside any one 64-bit word form a fixed pattern that repeats as you march word to word. So strike computes that handful of word-sized masks once, then ORs a whole 64-bit word at a time — 64 bits crossed out per write instead of one — cycling through the masks. Then it goes further: four of those word-ORs fuse into a single @Vector(4, u64), which lowers to a paired ldp/stp — 256 bits per instruction. For the big primes (stride ≥ 64, less than one struck bit per word) it switches to an 8-way-unrolled byte scatter instead, because there the dense trick stops paying. That branching — dense word-masks for small primes, unrolled scatter for large ones — is the 348 lines of mark_multiples, and it’s what those ~138 lines of strike are too. Your sieve writes strike and means all of it.

That’s the same line the comprehension drew earlier, from the other side. from and keep push a table’s generation down to compile time so your source says what the table is, not how to fill it. strike pushes a bitset’s marking down to the library so your source says which numbers to cross out, not how to vectorize the crossing. In both cases the readable thing and the fast thing are the same file.

Does this belong in the standard library?

Fair question — we built std/field because of a sieve, and the hot path is NEON-flavored. Is a bit-packed buffer with a SIMD strike really standard-library material, or a benchmark prop in a stdlib costume?

We think the buffer belongs, and the test is the interface, not the benchmark that birthed it. std/field is a dense bitset: new, set, test, count-zeros, clear, free — and strike, “set a strided run of bits.” Not one of those names a prime. A bitset is one of the most-reused structures there is: integer sets, Bloom filters, visited-sets in graph traversal, free-list and allocator bitmaps, bitmap indexes in databases, pixel-coverage in rasterizers, permission masks. count-zeros is just cardinality; clear is reuse-without-realloc; and the strided strike shows up anywhere you flip structured runs of bits — downsampling masks, ring scheduling, periodic patterns. The sieve touches every one of those primitives, which is exactly why it was a good test: it exercised the whole interface at once. That strike happens to be vectorized is an implementation virtue, not a coupling — the caller sees four integers and a field.

The one we’re not sure about is strike-wheel, which takes a wheel’s residue array and its period. That one knows what a sieve is. It’s the honest edge of the question — strike is a general primitive that earned its place; strike-wheel is a sieve helper that wandered into the library and probably belongs back in the program that needs it. Drawing that line — general buffer op vs. domain helper — is exactly the call a standard library exists to make, and we’d rather make it out loud than ship both and pretend they’re the same kind of thing.

What it isn’t, and what it is

We almost shipped a hand-wave about “framework overhead” before stopping to ask where it actually comes from. So we profiled it properly. By subtraction — the full sieve minus a find-only sieve that walks every candidate but never strikes — the marking takes ~62µs/pass in Koru; the raw C++/Zig marking takes ~64µs. They’re the same speed. And the disassembly settles the rest: test and strike inline — there are no event-dispatch calls in the hot loop at all. There is no language tax hiding in there.

So where was the “few-percent gap” we kept seeing against solution_5? It was us, measuring differently. solution_5’s timed loop is bare: alloc → sieve → free, over and over, and it counts the primes exactly once after the clock stops, to validate. Our sieve counted every pass and printed the result every pass — ~3µs of bookkeeping solution_5 never pays inside the timer. That’s not a language cost; it’s an unfair-to-us measurement. So we deleted the asymmetry: time bare alloc → sieve → free passes, count once at the end, exactly like solution_5. Run interleaved on the same machine, odds-only base algorithm, single thread, limit 1,000,000:

That’s a tie. Run it five times and the lead swaps depending on what else the machine is doing — one batch went to Koru, the next went 4-of-5 to C++. Both live in the same ~13,600–14,200 band, and Koru’s number is the conservative one besides: it still carries process startup and a validation pass that solution_5’s timed loop doesn’t. The gap we’d been writing paragraphs to explain away simply was the paragraph. Measured the same way, the high-level Koru sieve runs dead even with hand-tuned, word-wise, SIMD-marking C++ — because its strike uses the same word-wise marking, now living in a library primitive instead of inline in a benchmark.

And that’s the real claim — not “Koru beats C++,” but something better-grounded: a high-level language whose sieve reads like a description of the algorithm, running even with code written directly against the metal, by building general primitives rather than a special-cased benchmark. That’s the whole point, and it’s worth saying plainly: the durable artifacts were never the sieve. They’re std/table — a 5,760-entry wheel from one line of comprehension — and std/field, a dense bitset whose strike marks word-wise and SIMD-wide. The drag race was the instrument that told us they were real. The sieve is just the program that proved them, and it’s already thrown away.

Which points at where this goes next. Right now the fast marking inside strike is hand-written — the masks, the cycle, the vector width, tuned by us and by a small fleet of research agents reading the disassembly. But there’s a faster sieve still on the board (a comptime-specialized, fully-unrolled marker — the same trick the Zig champion uses), and the honest way to reach it isn’t to hand-write more Zig. It’s to make Koru’s compiler generate the specialized marker — the same move it already makes for regex, for comprehensions, for kernels. The day a high-level language’s compiler out-generates hand-tuned SIMD, the drag race stops being the story and becomes a footnote to it. We’re not there yet. But we can see the road, and we know what’s parked at the end of it.

And the habit we kept is worth more than any number: measure the full system, against a real opponent, and when the number flatters you, look harder. The elegant wheel taught us that by being wrong — and chasing the last percent taught us exactly where it went.