primal-sieve 0.3.6

A high performance prime sieve.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#[macro_use]
extern crate criterion;

use criterion::{BenchmarkId, Criterion};
use primal_sieve::{Primes, Sieve, StreamingSieve};

const SIZES: [usize; 5] = [100, 10_000, 100_000, 1_000_000, 10_000_000];

macro_rules! create_benchmarks {
    ($(
        fn $group_id: ident($input: expr) {
            $($name: expr => $func: expr,)*
        }
    )*) => {
        $(
            fn $group_id(c: &mut Criterion) {
                let input = $input;
                let mut group = c.benchmark_group(stringify!($group_id));

                $(
                    for i in &input {
                        let id = BenchmarkId::new($name, i);
                        group.bench_with_input(id, i, $func);
                    }
                )*

                group.finish();
            }
        )*
    }
}

create_benchmarks! {
    fn new(SIZES) {
        "Sieve" => |b, upto: &usize| b.iter(|| Sieve::new(*upto)),
    }

    fn prime_pi(SIZES) {
        "Sieve" => |b, upto: &usize| {
            let s = Sieve::new(*upto + 1);
            b.iter(|| s.prime_pi(*upto));
        },
        "Sieve with init" => |b, upto: &usize| {
            b.iter(|| {
                let s = Sieve::new(*upto + 1);
                s.prime_pi(*upto)
            });
        },

        "StreamingSieve" => |b, upto: &usize| {
            b.iter(|| StreamingSieve::prime_pi(*upto))
        },
        "Primes" => |b, upto: &usize| {
            b.iter(|| Primes::all().take_while(|x| *x <= *upto).count())
        },
    }

    fn nth_prime([100, 10_000, 100_000, 1_000_000]) {
        "Sieve" => |b, n: &usize| {
            let (_, hi) = primal_estimate::nth_prime(*n as u64);
            let s = Sieve::new(hi as usize);
            b.iter(|| s.nth_prime(*n));
        },
        "Sieve with init" => |b, n: &usize| {
            b.iter(|| {
                let (_, hi) = primal_estimate::nth_prime(*n as u64);
                let s = Sieve::new(hi as usize);
                s.nth_prime(*n)
            });
        },
        "StreamingSieve" => |b, n: &usize| {
            b.iter(|| StreamingSieve::nth_prime(*n))
        },
        "Primes" => |b, n: &usize| {
            b.iter(|| Primes::all().nth(*n - 1).unwrap())
        },
    }

    fn iterate(SIZES) {
        "Sieve" => |b, upto: &usize| {
            let s = Sieve::new(*upto);
            b.iter(|| s.primes_from(0).count());
        },
        "Sieve with init" => |b, upto: &usize| {
            b.iter(|| {
                let s = Sieve::new(*upto);
                s.primes_from(0).count()
            });
        },
        "Primes" => |b, upto: &usize| {
            b.iter(|| Primes::all().take_while(|p| *p < *upto).count())
        },
    }

    fn factor([131, 7561, 65521, 1048573, 2*3*5*7*11*13*17*19]) {
        "Sieve" => |b, n: &usize| {
            let s = Sieve::new(0x10000);

            b.iter(|| s.factor(*n).ok());
        },
    }
}

criterion_group!(benches, new, prime_pi, nth_prime, factor, iterate);
criterion_main!(benches);