benchmark.txt

➜  src git:(master) ✗ cargo bench -j 2
    Finished release [optimized] target(s) in 0.0 secs
     Running /home/cblades/dev/rust/prime_sieve/target/release/deps/prime_sieve-6cf5846238c99524

running 3 tests
test tests::bench_sundaram_hashset_1000 ... bench:   1,641,005 ns/iter (+/- 87,741)
test tests::bench_sundaram_vec_1000     ... bench:      81,529 ns/iter (+/- 3,800)
test tests::bench_sundaram_vec_10000    ... bench:   7,592,283 ns/iter (+/- 426,879)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured

prime_sieve_of_sundaram.rs

#![feature(test)]
extern crate test;
use std::collections::HashSet;

fn sieve_of_sundaram(max: usize) -> Vec<usize> {
    let max_n: usize = max / 2; // sieve produces primes from 3 to 2n+1
    let mut space: HashSet<usize> = (1..max_n + 1).collect();
    for i in 1..max_n {
        for j in i..max_n {
            space.remove(&(i + j + (2 * i * j)));
        }
    }

    space.iter().map(|&n| (2 * n) + 1).collect()
}

fn sieve_of_sundaram_vec(max: usize) -> Vec<usize> {
    let max_n: usize = max / 2; // sieve produces primes from 3 to 2n+1
    let mut space: Vec<bool> = (0..max_n + 1).map(|x| x % 2 != 0).collect();
    for i in 1..max_n {
        for j in i..max_n {
            let deselect = i + j + (2 * i * j);
            if deselect < max_n {
                space[deselect] = false;
            }
        }
    }

    space[2] = true;

    space.iter()
        .enumerate()
        .filter_map(|(n, &v)| if v { Some(n) } else { None })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_sundaram_hashset_1000(b: &mut Bencher) {
        b.iter(|| sieve_of_sundaram(1000));
    }

    #[bench]
    fn bench_sundaram_vec_1000(b: &mut Bencher) {
        b.iter(|| sieve_of_sundaram_vec(1000));
    }

    // #[bench]
    // fn bench_sundaram_hashset_10000(b: &mut Bencher) {
    //     b.iter(|| sieve_of_sundaram(10000));
    // }

    #[bench]
    fn bench_sundaram_vec_10000(b: &mut Bencher) {
        b.iter(|| sieve_of_sundaram_vec(10000));
    }
}