logvec 1.1.1

A cache-friendly Bentley-Saxe logarithmic array data structure.
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

#[path = "support/common.rs"]
mod common;

use common::{LargeStruct, N, shuffled_keys};
use criterion::{BatchSize, Criterion, criterion_group, criterion_main};
use logvec::LogVec;
use std::{collections::BTreeSet, hint::black_box};

fn bench_insert_u64(c: &mut Criterion) {
    let mut group = c.benchmark_group("baseline/insert_u64_10k");
    let random = shuffled_keys(N);

    group.bench_function("logvec", |b| {
        b.iter_batched(
            || random.clone(),
            |input| {
                let mut arr = LogVec::new();
                for key in input {
                    arr.insert(black_box(key));
                }
                arr
            },
            BatchSize::SmallInput,
        )
    });

    group.bench_function("btree_set", |b| {
        b.iter_batched(
            || random.clone(),
            |input| {
                let mut set = BTreeSet::new();
                for key in input {
                    set.insert(black_box(key));
                }
                set
            },
            BatchSize::SmallInput,
        )
    });

    group.bench_function("naive_sorted_vec", |b| {
        b.iter_batched(
            || random.clone(),
            |input| {
                let mut vec = Vec::new();
                for key in input {
                    let val = black_box(key);
                    let pos = vec.binary_search(&val).unwrap_or_else(|e| e);
                    vec.insert(pos, val);
                }
                vec
            },
            BatchSize::SmallInput,
        )
    });
}

fn bench_search_u64(c: &mut Criterion) {
    let mut group = c.benchmark_group("baseline/search_u64_10k");
    let keys = shuffled_keys(N);
    let mut log_arr = LogVec::new();
    let mut btree = BTreeSet::new();
    for key in &keys {
        log_arr.insert(*key);
        btree.insert(*key);
    }

    group.bench_function("logvec", |b| {
        b.iter(|| {
            for i in 0..N as u64 {
                black_box(log_arr.contains(black_box(&i)));
            }
        })
    });

    group.bench_function("btree_set", |b| {
        b.iter(|| {
            for i in 0..N as u64 {
                black_box(btree.contains(black_box(&i)));
            }
        })
    });
}

fn bench_insert_large_struct(c: &mut Criterion) {
    let mut group = c.benchmark_group("baseline/insert_large_struct_10k");
    let random = shuffled_keys(N);

    group.bench_function("logvec", |b| {
        b.iter_batched(
            || random.clone(),
            |input| {
                let mut arr = LogVec::new();
                for key in input {
                    arr.insert(black_box(LargeStruct::new(key)));
                }
                arr
            },
            BatchSize::SmallInput,
        )
    });

    group.bench_function("btree_set", |b| {
        b.iter_batched(
            || random.clone(),
            |input| {
                let mut set = BTreeSet::new();
                for key in input {
                    set.insert(black_box(LargeStruct::new(key)));
                }
                set
            },
            BatchSize::SmallInput,
        )
    });
}

criterion_group!(
    baseline_benches,
    bench_insert_u64,
    bench_search_u64,
    bench_insert_large_struct
);
criterion_main!(baseline_benches);