High-Performance, Lane-Based Segmented Sieve in Julia

General Usage Performance
1

Hi everyone
I wanted to share a program I’ve been working on within my GC60 project, which focuses on high-magnitude prime searching (beyond the 64-bit barrier). The goal wasn’t just to write a fast sieve, but to explore how a specialized mathematical structure, a Modulo-30 residue system organized into 8 computational lanes, interacts with Julia’s high-level capabilities.

The Challenge:
How can we implement a non-linear, lane-based sieve in a high-level language without being crushed by the overhead of memory management and thread synchronization?

The Implementation:
To achieve near-native performance, I focused on three specific Julia optimizations:

Memory Density: Using BitVector to align segment sizes with CPU L1/L2 cache.
GC Avoidance: Implementing all “Prep” and “Mapping” phases as in-place operations to eliminate mid-computation allocations. Load Balancing: Using Atomic{Int} for a dynamic work-stealing pattern to keep all threads busy despite the irregular distribution of primes across the 8 lanes.

The Results:
In a direct comparison of the core logic:

Primesieve (Kim Walisch):        ~1.911s
M30x8 (Julia Specialized Logic): ~1.046s

Note: While a direct C++ implementation of the M30x8 architecture is faster (~0.6s) due to hardware-level SIMD/AVX2 optimizations, this Julia implementation still significantly outperforms the industry-standard Primesieve (1.911s). This highlights that strategic algorithmic design can often outweigh raw language-level speed in high-performance computing tasks.

Verification:
All results were rigorously validated using SymPy in Python to ensure 100% mathematical correctness.

The full implementation is available on GitHub. The README includes benchmark specifications and timing results up to 10^24, feel free to download it, run it on your own machine, and see for yourself.

Repo: GitHub - Claugo/GC60_M30x8_suffix: High-Performance, Lane-Based Segmented Sieve in Julia · GitHub

2

That’s a really smart approach! I was just working on getting a segmented sieve for Primes.jl (Segmented sieve for `primes`, add `eachprime` iterator. - Pull Request #120 - JuliaMath/Primes.jl - GitHub), but this approach seems much nicer. Would you consider adding it as a PR to Primes (or any objections if I do)?

One other thing worth noting is that your ranges for the benchmarks are pretty small. For such a small range, rather than sieving you’re a lot better off by doing a basic primality test per number.

julia> using Primes
julia> function num_primes(range)
           num = 0
           for i in range
               isprime(i) && (num += 1)
           end
           num
       end
num_primes (generic function with 1 method)

julia> @time num_primes(Int128(10)^19:Int128(10)^19+10^5)
  0.022324 seconds (308.50 k allocations: 12.371 MiB) # vs 1s for the sieve
2263
3

well done!

out of curiosity what is this? (I can’t find it online)

4

Of course you can do that; I’d really appreciate it

5

This GC-60 project was published on Zenodo records 18657440. From there, algorithms were developed capable of reaching 10^27 in just over 3 hours, such as GC60_M30x3_suffix, which precedes X8. This GC60_M30x8_suffix has a slightly different concept and spans 8 columns, which is why I chose to implement it in Julia, as it seemed well-suited to managing the 8 threads very efficiently.

6

Segmented sieve for `primes`, add `eachprime` iterator. - Pull Request #120 - JuliaMath/Primes.jl - GitHub here it is. It ended up being a pretty nice speed increase (~30% faster than the previous version of the segmented sieve I had for no extra code)

7

Thanks Oscar! The test data is outstanding, especially on smaller numbers. I’m really glad the idea turned out to be useful for the Primes package. Good luck with the future development!