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

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

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

fn bench_insert(c: &mut Criterion) {
    let mut group = c.benchmark_group("core/insert");
    let random = shuffled_keys(N);

    group.bench_function("u64_sequential_10k/logvec", |b| {
        b.iter_batched(
            || (),
            |()| {
                let mut arr = LogVec::new();
                for i in 0..N as u64 {
                    arr.insert(black_box(i));
                }
                arr
            },
            BatchSize::SmallInput,
        )
    });

    group.bench_function("u64_random_10k/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,
        )
    });
}

fn bench_contains(c: &mut Criterion) {
    let mut group = c.benchmark_group("core/contains");
    let random = shuffled_keys(N);
    let mut arr = LogVec::new();
    for key in &random {
        arr.insert(*key);
    }

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

    group.bench_function("u64_miss_seq_10k/logvec", |b| {
        b.iter(|| {
            for i in N as u64..(2 * N) as u64 {
                black_box(arr.contains(black_box(&i)));
            }
        })
    });

    let mixed_queries: Vec<u64> = (0..N).flat_map(|i| [i as u64, (N + i) as u64]).collect();
    group.bench_function("u64_mixed_hit_miss_20k/logvec", |b| {
        b.iter(|| {
            for q in &mixed_queries {
                black_box(arr.contains(black_box(q)));
            }
        })
    });
}

fn bench_delete(c: &mut Criterion) {
    let mut group = c.benchmark_group("core/delete");
    let random = shuffled_keys(N);
    let deletions: Vec<u64> = random.iter().take(N / 2).copied().collect();

    group.bench_function("u64_delete_half_random_10k/logvec", |b| {
        b.iter_batched(
            || {
                let mut arr = LogVec::new();
                for key in &random {
                    arr.insert(*key);
                }
                arr
            },
            |mut arr| {
                for key in &deletions {
                    black_box(arr.delete(black_box(key)));
                }
                arr
            },
            BatchSize::SmallInput,
        )
    });
}

criterion_group!(core_benches, bench_insert, bench_contains, bench_delete);
criterion_main!(core_benches);