vob 4.0.0

Vector of Bits with Vec-like API and usize backing storage
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use criterion::{criterion_group, criterion_main, Criterion};
use rand::prelude::*;
use std::collections::HashSet;

const SIZE: usize = 10000;

/// This benchmark compares the performance of HashSet, Vob, and Vec
/// in a scenario where an algorithm needs to keep track of visited indices.
#[cfg(test)]
fn comparative(c: &mut Criterion) {
    // Generate 10000 random (seeded) points
    let mut rng: StdRng = SeedableRng::from_seed([42; 32]);
    let mut indices: Vec<usize> = (0..SIZE).collect();

    indices.shuffle(&mut rng);

    c.bench_function("HashSet comparative", |b| {
        b.iter(|| {
            let mut hash_set = HashSet::new();
            // set half of the set to "true"
            for index in indices.iter().skip(SIZE / 2) {
                hash_set.insert(index);
            }

            for index in indices.iter().take(SIZE / 2) {
                assert!(
                    !hash_set.contains(index),
                    "index {} is supposed to be cleared",
                    index
                );
            }
            for index in indices.iter().skip(SIZE / 2) {
                assert!(
                    hash_set.contains(index),
                    "index {} is supposed to be set",
                    index
                );
            }
        })
    });

    c.bench_function("Vob comparative", |b| {
        b.iter(|| {
            let mut vob = vob::Vob::<u32>::from_elem_with_storage_type(false, SIZE);

            // set half of the vob to true
            for index in indices.iter().skip(SIZE / 2) {
                vob.set(*index, true);
            }

            for index in indices.iter().take(SIZE / 2) {
                assert!(!vob[*index], "index {} is supposed to be cleared", index);
            }
            for index in indices.iter().skip(SIZE / 2) {
                assert!(vob[*index], "index {} is supposed to be set", index);
            }
        })
    });

    c.bench_function("Vob unchecked comparative", |b| {
        b.iter(|| {
            let mut vob = vob::Vob::<u32>::from_elem_with_storage_type(false, SIZE);

            unsafe {
                // set half of the vob to true
                for index in indices.iter().skip(SIZE / 2) {
                    vob.set_unchecked(*index, true);
                }

                for index in indices.iter().take(SIZE / 2) {
                    assert!(
                        !vob.get_unchecked(*index),
                        "index {} is supposed to be cleared",
                        index
                    );
                }
                for index in indices.iter().skip(SIZE / 2) {
                    assert!(
                        vob.get_unchecked(*index),
                        "index {} is supposed to be set",
                        index
                    );
                }
            }
        })
    });

    c.bench_function("Vec comparative", |b| {
        b.iter(|| {
            let mut vec: Vec<bool> = vec![false; SIZE];

            // set half of the vec to true
            for index in indices.iter().skip(SIZE / 2) {
                vec[*index] = true;
            }

            for index in indices.iter().take(SIZE / 2) {
                assert!(!vec[*index], "index {} is supposed to be cleared", index);
            }
            for index in indices.iter().skip(SIZE / 2) {
                assert!(vec[*index], "index {} is supposed to be set", index);
            }
        })
    });

    c.bench_function("Vec unchecked comparative", |b| {
        b.iter(|| {
            let mut vec: Vec<bool> = vec![false; SIZE];
            unsafe {
                // set half of the vec to true
                for index in indices.iter().skip(SIZE / 2) {
                    *vec.get_unchecked_mut(*index) = true;
                }

                for index in indices.iter().take(SIZE / 2) {
                    assert!(
                        !vec.get_unchecked(*index),
                        "index {} is supposed to be cleared",
                        index
                    );
                }
                for index in indices.iter().skip(SIZE / 2) {
                    assert!(
                        vec.get_unchecked(*index),
                        "index {} is supposed to be set",
                        index
                    );
                }
            }
        })
    });
}

criterion_group!(benches, comparative);
criterion_main!(benches);