1 // This benchmark suite contains some benchmarks along a set of dimensions:
2 // Hasher: std default (SipHash) and crate default (AHash).
3 // Int key distribution: low bit heavy, top bit heavy, and random.
4 // Task: basic functionality: insert, insert_erase, lookup, lookup_fail, iter
5 #![feature(test)]
6
7 extern crate test;
8
9 use test::{black_box, Bencher};
10
11 use hashbrown::hash_map::DefaultHashBuilder;
12 use hashbrown::{HashMap, HashSet};
13 use std::{
14 collections::hash_map::RandomState,
15 sync::atomic::{self, AtomicUsize},
16 };
17
18 const SIZE: usize = 1000;
19
20 // The default hashmap when using this crate directly.
21 type AHashMap<K, V> = HashMap<K, V, DefaultHashBuilder>;
22 // This uses the hashmap from this crate with the default hasher of the stdlib.
23 type StdHashMap<K, V> = HashMap<K, V, RandomState>;
24
25 // A random key iterator.
26 #[derive(Clone, Copy)]
27 struct RandomKeys {
28 state: usize,
29 }
30
31 impl RandomKeys {
new() -> Self32 fn new() -> Self {
33 RandomKeys { state: 0 }
34 }
35 }
36
37 impl Iterator for RandomKeys {
38 type Item = usize;
next(&mut self) -> Option<usize>39 fn next(&mut self) -> Option<usize> {
40 // Add 1 then multiply by some 32 bit prime.
41 self.state = self.state.wrapping_add(1).wrapping_mul(3787392781);
42 Some(self.state)
43 }
44 }
45
46 // Just an arbitrary side effect to make the maps not shortcircuit to the non-dropping path
47 // when dropping maps/entries (most real world usages likely have drop in the key or value)
48 lazy_static::lazy_static! {
49 static ref SIDE_EFFECT: AtomicUsize = AtomicUsize::new(0);
50 }
51
52 #[derive(Clone)]
53 struct DropType(usize);
54 impl Drop for DropType {
drop(&mut self)55 fn drop(&mut self) {
56 SIDE_EFFECT.fetch_add(self.0, atomic::Ordering::SeqCst);
57 }
58 }
59
60 macro_rules! bench_suite {
61 ($bench_macro:ident, $bench_ahash_serial:ident, $bench_std_serial:ident,
62 $bench_ahash_highbits:ident, $bench_std_highbits:ident,
63 $bench_ahash_random:ident, $bench_std_random:ident) => {
64 $bench_macro!($bench_ahash_serial, AHashMap, 0..);
65 $bench_macro!($bench_std_serial, StdHashMap, 0..);
66 $bench_macro!(
67 $bench_ahash_highbits,
68 AHashMap,
69 (0..).map(usize::swap_bytes)
70 );
71 $bench_macro!(
72 $bench_std_highbits,
73 StdHashMap,
74 (0..).map(usize::swap_bytes)
75 );
76 $bench_macro!($bench_ahash_random, AHashMap, RandomKeys::new());
77 $bench_macro!($bench_std_random, StdHashMap, RandomKeys::new());
78 };
79 }
80
81 macro_rules! bench_insert {
82 ($name:ident, $maptype:ident, $keydist:expr) => {
83 #[bench]
84 fn $name(b: &mut Bencher) {
85 let mut m = $maptype::with_capacity_and_hasher(SIZE, Default::default());
86 b.iter(|| {
87 m.clear();
88 for i in ($keydist).take(SIZE) {
89 m.insert(i, (DropType(i), [i; 20]));
90 }
91 black_box(&mut m);
92 });
93 eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
94 }
95 };
96 }
97
98 bench_suite!(
99 bench_insert,
100 insert_ahash_serial,
101 insert_std_serial,
102 insert_ahash_highbits,
103 insert_std_highbits,
104 insert_ahash_random,
105 insert_std_random
106 );
107
108 macro_rules! bench_grow_insert {
109 ($name:ident, $maptype:ident, $keydist:expr) => {
110 #[bench]
111 fn $name(b: &mut Bencher) {
112 b.iter(|| {
113 let mut m = $maptype::default();
114 for i in ($keydist).take(SIZE) {
115 m.insert(i, DropType(i));
116 }
117 black_box(&mut m);
118 })
119 }
120 };
121 }
122
123 bench_suite!(
124 bench_grow_insert,
125 grow_insert_ahash_serial,
126 grow_insert_std_serial,
127 grow_insert_ahash_highbits,
128 grow_insert_std_highbits,
129 grow_insert_ahash_random,
130 grow_insert_std_random
131 );
132
133 macro_rules! bench_insert_erase {
134 ($name:ident, $maptype:ident, $keydist:expr) => {
135 #[bench]
136 fn $name(b: &mut Bencher) {
137 let mut base = $maptype::default();
138 for i in ($keydist).take(SIZE) {
139 base.insert(i, DropType(i));
140 }
141 let skip = $keydist.skip(SIZE);
142 b.iter(|| {
143 let mut m = base.clone();
144 let mut add_iter = skip.clone();
145 let mut remove_iter = $keydist;
146 // While keeping the size constant,
147 // replace the first keydist with the second.
148 for (add, remove) in (&mut add_iter).zip(&mut remove_iter).take(SIZE) {
149 m.insert(add, DropType(add));
150 black_box(m.remove(&remove));
151 }
152 black_box(m);
153 });
154 eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
155 }
156 };
157 }
158
159 bench_suite!(
160 bench_insert_erase,
161 insert_erase_ahash_serial,
162 insert_erase_std_serial,
163 insert_erase_ahash_highbits,
164 insert_erase_std_highbits,
165 insert_erase_ahash_random,
166 insert_erase_std_random
167 );
168
169 macro_rules! bench_lookup {
170 ($name:ident, $maptype:ident, $keydist:expr) => {
171 #[bench]
172 fn $name(b: &mut Bencher) {
173 let mut m = $maptype::default();
174 for i in $keydist.take(SIZE) {
175 m.insert(i, DropType(i));
176 }
177
178 b.iter(|| {
179 for i in $keydist.take(SIZE) {
180 black_box(m.get(&i));
181 }
182 });
183 eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
184 }
185 };
186 }
187
188 bench_suite!(
189 bench_lookup,
190 lookup_ahash_serial,
191 lookup_std_serial,
192 lookup_ahash_highbits,
193 lookup_std_highbits,
194 lookup_ahash_random,
195 lookup_std_random
196 );
197
198 macro_rules! bench_lookup_fail {
199 ($name:ident, $maptype:ident, $keydist:expr) => {
200 #[bench]
201 fn $name(b: &mut Bencher) {
202 let mut m = $maptype::default();
203 let mut iter = $keydist;
204 for i in (&mut iter).take(SIZE) {
205 m.insert(i, DropType(i));
206 }
207
208 b.iter(|| {
209 for i in (&mut iter).take(SIZE) {
210 black_box(m.get(&i));
211 }
212 })
213 }
214 };
215 }
216
217 bench_suite!(
218 bench_lookup_fail,
219 lookup_fail_ahash_serial,
220 lookup_fail_std_serial,
221 lookup_fail_ahash_highbits,
222 lookup_fail_std_highbits,
223 lookup_fail_ahash_random,
224 lookup_fail_std_random
225 );
226
227 macro_rules! bench_iter {
228 ($name:ident, $maptype:ident, $keydist:expr) => {
229 #[bench]
230 fn $name(b: &mut Bencher) {
231 let mut m = $maptype::default();
232 for i in ($keydist).take(SIZE) {
233 m.insert(i, DropType(i));
234 }
235
236 b.iter(|| {
237 for i in &m {
238 black_box(i);
239 }
240 })
241 }
242 };
243 }
244
245 bench_suite!(
246 bench_iter,
247 iter_ahash_serial,
248 iter_std_serial,
249 iter_ahash_highbits,
250 iter_std_highbits,
251 iter_ahash_random,
252 iter_std_random
253 );
254
255 #[bench]
clone_small(b: &mut Bencher)256 fn clone_small(b: &mut Bencher) {
257 let mut m = HashMap::new();
258 for i in 0..10 {
259 m.insert(i, DropType(i));
260 }
261
262 b.iter(|| {
263 black_box(m.clone());
264 })
265 }
266
267 #[bench]
clone_from_small(b: &mut Bencher)268 fn clone_from_small(b: &mut Bencher) {
269 let mut m = HashMap::new();
270 let mut m2 = HashMap::new();
271 for i in 0..10 {
272 m.insert(i, DropType(i));
273 }
274
275 b.iter(|| {
276 m2.clone_from(&m);
277 black_box(&mut m2);
278 })
279 }
280
281 #[bench]
clone_large(b: &mut Bencher)282 fn clone_large(b: &mut Bencher) {
283 let mut m = HashMap::new();
284 for i in 0..1000 {
285 m.insert(i, DropType(i));
286 }
287
288 b.iter(|| {
289 black_box(m.clone());
290 })
291 }
292
293 #[bench]
clone_from_large(b: &mut Bencher)294 fn clone_from_large(b: &mut Bencher) {
295 let mut m = HashMap::new();
296 let mut m2 = HashMap::new();
297 for i in 0..1000 {
298 m.insert(i, DropType(i));
299 }
300
301 b.iter(|| {
302 m2.clone_from(&m);
303 black_box(&mut m2);
304 })
305 }
306
307 #[bench]
rehash_in_place(b: &mut Bencher)308 fn rehash_in_place(b: &mut Bencher) {
309 b.iter(|| {
310 let mut set = HashSet::new();
311
312 // Each loop triggers one rehash
313 for _ in 0..10 {
314 for i in 0..224 {
315 set.insert(i);
316 }
317
318 assert_eq!(
319 set.capacity(),
320 224,
321 "The set must be at or close to capacity to trigger a re hashing"
322 );
323
324 for i in 100..1400 {
325 set.remove(&(i - 100));
326 set.insert(i);
327 }
328 set.clear();
329 }
330 });
331 }
332