Hi everyone,

I’m new here and wanted to share a crate I put together called Primer: a prime generator/sieve focused on being both fast and extremely memory efficient (especially on constrained targets like ESP32-class devices).​

Repo: https://github.com/wisprer/primer​

What it is

Primer is a bit-packed, odd-only Sieve of Eratosthenes implementation that generates primes in increasing order, with an emphasis on low memory residency and good real-world throughput.​

Why it might be useful

A lot of prime approaches end up memory-heavy (or require tradeoffs that don’t suit embedded / small-footprint work), so Primer aims for “small and sharp”: 1 bit per odd candidate, cache-friendly scanning, and fast bit-iteration to skip work.​

The core tricks used are:

• Bit packing (1 bit per odd number rather than byte/word-per-number style storage).​
• Odd-only sieving (hardcode 2, then only represent/process odd candidates).​
• Fast bit scanning using trailing_zeros (which the README notes compiles down to efficient CPU instructions on x86_64).​
• Brian Kernighan’s bit-iteration trick (iterate only over set bits rather than scanning all 64 positions).​

Performance & footprint (from the README)

In the included benchmarks, Primer is reported as about 64× faster than the primes crate in certain cases, and can be in the same ballpark as primal depending on the workload.​

For n = 500,000 (41,538 primes), the README’s table lists roughly:

• Primer: ~4 KB memory, ~2 ms.​
• primes crate: ~500 KB memory, ~15 ms.​
• primal crate: ~50 KB memory, ~3 ms.​

The README also includes a scaling table up to 100M with estimated memory/time characteristics (e.g., 10M ≈ 80 KB, ~15 ms; 100M ≈ 800 KB, ~200 ms).​

API / examples

The README includes a simple entry point (sieve_primes(limit) -> Vec<u64>) and shows patterns like generating a prime table once at startup and reusing it for things like hashing/partitioning use cases.​

Feedback welcome

I’d love feedback on the approach, API ergonomics, correctness/testing strategy, and benchmark methodology, and I’m very open to making it more idiomatic or adjusting claims if anyone spots an issue.​

Thanks for taking a look!

3 posts - 3 participants

Read full topic