# High-Performance, Lane-Based Segmented Sieve in Julia

**URL:** <https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854>\
**Category:** Performance\
**Created:** [June 29, 2026, 5:47pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854 "2026-06-29T17:47:19Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Claugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claugo/32/222296_2.png) [@Claugo](https://discourse.julialang.org/u/Claugo)\
**Post date:** [June 29, 2026, 5:47pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/1 "2026-06-29T17:47:19Z")

</div>

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](https://github.com/Claugo/GC60_M30x8_suffix)

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [June 29, 2026, 6:21pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/2 "2026-06-29T18:21:28Z")

</div>

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](https://github.com/JuliaMath/Primes.jl/pull/120)), 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-auto
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
```

---

<div class="post-metadata">

**Author:** ![langestefan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/langestefan/32/207923_2.png) [@langestefan](https://discourse.julialang.org/u/langestefan)\
**Post date:** [June 29, 2026, 6:29pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/3 "2026-06-29T18:29:20Z")

</div>

well done!

> [@Claugo](#):
>
> GC60 project

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

---

<div class="post-metadata">

**Author:** ![Claugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claugo/32/222296_2.png) [@Claugo](https://discourse.julialang.org/u/Claugo)\
**Post date:** [June 29, 2026, 6:41pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/4 "2026-06-29T18:41:06Z")

</div>

> [@Oscar\_Smith](#):
>
> ma questo approccio sembra molto migliore. Prenderesti in considerazione l’idea di aggiungerlo come pull request a Primes (o hai obiezioni se lo facessi)?

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

---

<div class="post-metadata">

**Author:** ![Claugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claugo/32/222296_2.png) [@Claugo](https://discourse.julialang.org/u/Claugo)\
**Post date:** [June 29, 2026, 6:49pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/5 "2026-06-29T18:49:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [June 30, 2026, 9:36pm UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/6 "2026-06-30T21:36:29Z")

</div>

[Segmented sieve for `primes`, add `eachprime` iterator. - Pull Request #120 - JuliaMath/Primes.jl - GitHub](https://github.com/JuliaMath/Primes.jl/pull/120) 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)

---

<div class="post-metadata">

**Author:** ![Claugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claugo/32/222296_2.png) [@Claugo](https://discourse.julialang.org/u/Claugo)\
**Post date:** [July 1, 2026, 10:27am UTC](https://discourse.julialang.org/t/high-performance-lane-based-segmented-sieve-in-julia/137854/7 "2026-07-01T10:27:47Z")

</div>

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!