| 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 { |
| 32 |
fn new() -> Self { |
| 33 |
RandomKeys { state: 0 } |
| 34 |
} |
| 35 |
} |
| 36 |
|
| 37 |
impl Iterator for RandomKeys { |
| 38 |
type Item = 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(3_787_392_781); |
| 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 { |
| 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] |
| 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] |
| 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] |
| 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] |
| 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] |
| 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 |
} |