indexset 0.16.0

A two-level BTree with fast iteration and indexing operations
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

use criterion::{criterion_group, criterion_main, Criterion};
use rand::seq::SliceRandom;
use rand::thread_rng;
use scc::TreeIndex;
use std::hint::black_box;

fn criterion_benchmark(c: &mut Criterion) {
    let n = 100000;
    let mut input: Vec<usize> = (0..n).collect();
    input.shuffle(&mut thread_rng());

    c.bench_function("stdlib insert 100k", |b| {
        b.iter(|| {
            let mut btreeset = std::collections::BTreeSet::new();

            input.iter().for_each(|item| {
                black_box(btreeset.insert(item));
            });

            assert_eq!(btreeset.len(), n);
        })
    });
    c.bench_function("indexset insert 100k", |b| {
        b.iter(|| {
            let mut indexset = indexset::BTreeSet::new();

            input.iter().for_each(|item| {
                black_box(indexset.insert(*item));
            });

            assert_eq!(indexset.len(), n);
        })
    });
    c.bench_function("concurrent indexset insert 100k", |b| {
        b.iter(|| {
            let indexset: indexset::concurrent::set::BTreeSet<usize> = indexset::concurrent::set::BTreeSet::new();

            input.iter().for_each(|item| {
                black_box(indexset.insert(*item));
            });

            assert_eq!(indexset.len(), n);
        })
    });
    c.bench_function("treeindex insert 100k", |b| {
        b.iter(|| {
            let treeindex = TreeIndex::new();

            input.iter().for_each(|item| {
                black_box(treeindex.insert(*item, ()).unwrap());
            });

            assert_eq!(treeindex.len(), n);
        })
    });

    let stdlib = std::collections::BTreeSet::from_iter(input.iter());
    let indexset = indexset::BTreeSet::from_iter(input.iter());
    let concurrent_indexset: indexset::concurrent::set::BTreeSet<usize> = indexset::concurrent::set::BTreeSet::new();
    for i in &input {
        concurrent_indexset.insert(*i);
    }
    let treeindex = TreeIndex::new();
    for i in &input {
        let _ = treeindex.insert(*i, ());
    }

    c.bench_function("stdlib contains 100k", |b| {
        b.iter(|| {
            input.iter().for_each(|item| {
                stdlib.contains(black_box(item));
            })
        })
    });
    c.bench_function("indexset contains 100k", |b| {
        b.iter(|| {
            input.iter().for_each(|item| {
                indexset.contains(black_box(item));
            })
        })
    });
    c.bench_function("concurrent indexset contains 100k", |b| {
        b.iter(|| {
            input.iter().for_each(|item| {
                indexset.contains(black_box(item));
            })
        })
    });
    c.bench_function("treeindex contains 100k", |b| {
        b.iter(|| {
            input.iter().for_each(|item| {
                treeindex.contains(black_box(item));
            })
        })
    });

    // c.bench_function("stdlib get i-th 100k", |b| {
    //     b.iter(|| {
    //         input.iter().for_each(|item| {
    //             stdlib.iter().nth(black_box(*item));
    //         })
    //     })
    // });
    c.bench_function("indexset get i-th 100k", |b| {
        b.iter(|| {
            input.iter().for_each(|item| {
                black_box(indexset.get_index(black_box(*item)));
            })
        })
    });

    c.bench_function("stdlib collect 100k into vec", |b| {
        b.iter(|| std::hint::black_box(stdlib.iter().collect::<Vec<&&usize>>()))
    });

    c.bench_function("indexset collect 100k into vec", |b| {
        b.iter(|| std::hint::black_box(indexset.iter().collect::<Vec<&&usize>>()))
    });
}

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