vecmap 0.1.0

Vec-based Map and Set data structures.
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

extern crate rand;
extern crate vecmap;

use criterion::{
    black_box, criterion_group, criterion_main, Bencher, BenchmarkId, Criterion, Throughput,
};
use rand::prelude::*;
use std::collections::HashMap;
use vecmap::VecMap;

fn bench_fill_vecmap(b: &mut Bencher, &size: &i32) {
    let numbers: Vec<i32> = rand::distributions::Uniform::new(0, size)
        .sample_iter(thread_rng())
        .take(size as usize)
        .collect();
    b.iter(|| {
        let mut map: VecMap<i32, i32> = VecMap::new();
        for i in 0..size {
            map.insert(numbers[i as usize], i);
        }
        black_box(map.get(&0));
    });
}

fn bench_fill_hashmap(b: &mut Bencher, &size: &i32) {
    let numbers: Vec<i32> = rand::distributions::Uniform::new(0, size)
        .sample_iter(thread_rng())
        .take(size as usize)
        .collect();
    b.iter(|| {
        let mut map: HashMap<i32, i32> = HashMap::new();
        for i in 0..size {
            map.insert(numbers[i as usize], i);
        }
        black_box(map.get(&0));
    });
}

fn bench_fill(c: &mut Criterion) {
    let mut group = c.benchmark_group("Fill");
    for size in [1, 10, 100, 1000, 10000].iter() {
        group.throughput(Throughput::Elements(*size as u64));
        group.bench_with_input(BenchmarkId::new("VecMap", size), size, bench_fill_vecmap);
        group.bench_with_input(BenchmarkId::new("HashMap", size), size, bench_fill_hashmap);
    }
    group.finish();
}

fn bench_entry_vecmap(b: &mut Bencher, &size: &i32) {
    let mut map: VecMap<i32, i32> = VecMap::new();
    let mut rng = thread_rng();
    let distr = rand::distributions::Uniform::new(0, size);
    for i in 0..size {
        map.insert(distr.sample(&mut rng), i);
    }
    b.iter(|| {
        black_box(map.entry(distr.sample(&mut rng)));
    });
}

fn bench_entry_hashmap(b: &mut Bencher, &size: &i32) {
    let mut map: HashMap<i32, i32> = HashMap::new();
    let mut rng = thread_rng();
    let distr = rand::distributions::Uniform::new(0, size);
    for i in 0..size {
        map.insert(distr.sample(&mut rng), i);
    }
    b.iter(|| {
        black_box(map.entry(distr.sample(&mut rng)));
    });
}

fn bench_entry(c: &mut Criterion) {
    let mut group = c.benchmark_group("Entry");
    for size in [1, 10, 100, 1000, 10000].iter() {
        group.bench_with_input(BenchmarkId::new("VecMap", size), size, bench_entry_vecmap);
        group.bench_with_input(BenchmarkId::new("HashMap", size), size, bench_entry_hashmap);
    }
    group.finish();
}

fn bench_counting_vecmap(b: &mut Bencher, &size: &i32) {
    let mut map: VecMap<i32, i32> = VecMap::new();
    let mut rng = thread_rng();
    let distr = rand::distributions::Uniform::new(0, size);
    b.iter(|| {
        *map.entry(distr.sample(&mut rng)).or_insert(0) += 1;
    });
    black_box(map);
}

fn bench_counting_hashmap(b: &mut Bencher, &size: &i32) {
    let mut map: HashMap<i32, i32> = HashMap::new();
    let mut rng = thread_rng();
    let distr = rand::distributions::Uniform::new(0, size);
    b.iter(|| {
        *map.entry(distr.sample(&mut rng)).or_insert(0) += 1;
    });
    black_box(map);
}

fn bench_counting(c: &mut Criterion) {
    let mut group = c.benchmark_group("Counting");
    for size in [1, 10, 100, 1000, 10000].iter() {
        group.bench_with_input(
            BenchmarkId::new("VecMap", size),
            size,
            bench_counting_vecmap,
        );
        group.bench_with_input(
            BenchmarkId::new("HashMap", size),
            size,
            bench_counting_hashmap,
        );
    }
    group.finish();
}

criterion_group!(benches, bench_fill, bench_entry, bench_counting);
criterion_main!(benches);