A Lane-Based Segmented Sieve Implementation for High-Magnitude Prime Searching in Julia

[Claugo]

Hi everyone,

I wanted to share a project 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 (C++ Standard Sieve): ~1.911s
M30x8 (Julia Specialized Logic): ~1.046s

Note: I am aware that a native C++ implementation of the M30x8 logic would outperform this Julia version (achieving ~0.6s through SIMD/AVX2 vectorization). However, the significance of this result lies in the comparison with the industry-standard Primesieve (1.911s). The fact that this specialized algorithmic approach, implemented in Julia, still outperforms a highly optimized C++ standard library is a compelling demonstration of how algorithmic innovation can effectively bridge the gap between high-level languages and low-level systems code.

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

I'd love to hear your thoughts on the implementation or any suggestions on further optimizing the lane-based traversal in Julia.

https://github.com/Claugo/GC60_M30x8_suffix

[vchuravy]

Hello @Claugo , the right place for a conversation like this is the community forum at https://discourse.julialang.org that ensures that this discussion has a wider visibility