Parallel Sieve of Eratosthenes in Rust

sieve.rs

extern crate rayon;
extern crate time;

use rayon::prelude::*;

const MAX: usize = 1_000_000_000;
const CHUNK_SIZE: usize = 100_000;
const NUM_PRIMES: usize = 50_847_534;

/// Sieve odd integers for primes up to max (exclusive).
/// (sieve[i]==true -> 2*i+1 is prime)
fn sieve_serial(max: usize) -> Vec<bool> {
    let mut sieve = vec![true; max / 2];
    sieve[0] = false; // 1 is not prime
    for i in 1 .. {
        if sieve[i] {
            let p = 2 * i + 1;
            let mut pp = p * p;
            if pp >= max { break }
            while pp < max {
                sieve[pp / 2] = false;
                pp += 2 * p;
            }
        }
    }
    sieve
}

/// Sieve odd integers for primes up to max (exclusive) -- in parallel!
/// (sieve[i]==true -> 2*i+1 is prime)
fn sieve_parallel(max: usize) -> Vec<bool> {
    // first compute the small primes, up to sqrt(max).
    let small_max = (max as f64).sqrt().ceil() as usize;
    let mut sieve = sieve_serial(small_max);
    sieve.resize(max / 2, true);

    {
        let (low, high) = sieve.split_at_mut(small_max / 2);
        high.par_chunks_mut(CHUNK_SIZE)
            .weight_max() // ensure every single chunk is a separate rayon job
            .enumerate() // so you can figure out where this chunk came from
            .for_each(|(chunk_index, chunk)| {
                let base = (small_max / 2 + chunk_index * CHUNK_SIZE) * 2 + 1;
                let max = base + chunk.len() * 2;
                for (i, &is_prime) in low.iter().enumerate() {
                    if is_prime {
                        let p = 2 * i + 1;
                        let mut pp = p * p;
                        if pp >= max { break }
                        if pp < base {
                            pp = (base + p - 1) / p * p;
                            if pp & 1 == 0 {
                                pp += p;
                            }
                        }
                        while pp < max {
                            chunk[(pp - base) / 2] = false;
                            pp += 2 * p;
                        }
                    }
                }
            });
    }
    sieve
}

fn main() {
    rayon::initialize(rayon::Configuration::new()).unwrap();

    let t0 = time::precise_time_ns();
    let serial = sieve_serial(MAX);
    let t1 = time::precise_time_ns();
    let parallel = sieve_parallel(MAX);
    let t2 = time::precise_time_ns();

    // sanity check the number of primes found
    let num_primes = 1 + serial.iter().filter(|&&b| b).count();
    assert_eq!(num_primes, NUM_PRIMES);

    // make sure parallel got the exact same primes
    assert_eq!(serial.len(), parallel.len());
    assert!(serial == parallel); // too big to print for assert_eq!

    let serial_duration = t1 - t0;
    let parallel_duration = t2 - t1;
    println!("  serial: {} ns", serial_duration);
    println!("parallel: {} ns", parallel_duration);
    println!("-> {:.2}x speedup", serial_duration as f64 / parallel_duration as f64);
}