vendor/hashbrown-0.5.0/benches/bench.rs

   1 // This benchmark suite contains some benchmarks along a set of dimensions:
   2 //   Hasher: std default (SipHash) and crate default (FxHash).
   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;
  13 use std::collections::hash_map::RandomState;
  14
  15 const SIZE: usize = 1000;
  16
  17 // The default hashmap when using this crate directly.
  18 type FxHashMap<K, V> = HashMap<K, V, DefaultHashBuilder>;
  19 // This uses the hashmap from this crate with the default hasher of the stdlib.
  20 type StdHashMap<K, V> = HashMap<K, V, RandomState>;
  21
  22 // A random key iterator.
  23 #[derive(Clone, Copy)]
  24 struct RandomKeys {
  25     state: usize,
  26 }
  27
  28 impl RandomKeys {
  29     fn new() -> Self {
  30         RandomKeys { state: 0 }
  31     }
  32 }
  33
  34 impl Iterator for RandomKeys {
  35     type Item = usize;
  36     fn next(&mut self) -> Option<usize> {
  37         // Add 1 then multiply by some 32 bit prime.
  38         self.state = self.state.wrapping_add(1).wrapping_mul(3787392781);
  39         Some(self.state)
  40     }
  41 }
  42
  43 macro_rules! bench_suite {
  44     ($bench_macro:ident, $bench_fx_serial:ident, $bench_std_serial:ident,
  45      $bench_fx_highbits:ident, $bench_std_highbits:ident,
  46      $bench_fx_random:ident, $bench_std_random:ident) => {
  47         $bench_macro!($bench_fx_serial, FxHashMap, 0..);
  48         $bench_macro!($bench_std_serial, StdHashMap, 0..);
  49         $bench_macro!($bench_fx_highbits, FxHashMap, (0..).map(usize::swap_bytes));
  50         $bench_macro!(
  51             $bench_std_highbits,
  52             StdHashMap,
  53             (0..).map(usize::swap_bytes)
  54         );
  55         $bench_macro!($bench_fx_random, FxHashMap, RandomKeys::new());
  56         $bench_macro!($bench_std_random, StdHashMap, RandomKeys::new());
  57     };
  58 }
  59
  60 macro_rules! bench_insert {
  61     ($name:ident, $maptype:ident, $keydist:expr) => {
  62         #[bench]
  63         fn $name(b: &mut Bencher) {
  64             b.iter(|| {
  65                 let mut m = $maptype::default();
  66                 for i in ($keydist).take(SIZE) {
  67                     m.insert(i, i);
  68                 }
  69                 black_box(m);
  70             })
  71         }
  72     };
  73 }
  74
  75 bench_suite!(
  76     bench_insert,
  77     insert_fx_serial,
  78     insert_std_serial,
  79     insert_fx_highbits,
  80     insert_std_highbits,
  81     insert_fx_random,
  82     insert_std_random
  83 );
  84
  85 macro_rules! bench_insert_erase {
  86     ($name:ident, $maptype:ident, $keydist:expr) => {
  87         #[bench]
  88         fn $name(b: &mut Bencher) {
  89             let mut m = $maptype::default();
  90             let mut add_iter = $keydist;
  91             for i in (&mut add_iter).take(SIZE) {
  92                 m.insert(i, i);
  93             }
  94             let mut remove_iter = $keydist;
  95             b.iter(|| {
  96                 // While keeping the size constant,
  97                 // replace the first keydist with the second.
  98                 for (add, remove) in (&mut add_iter).zip(&mut remove_iter).take(SIZE) {
  99                     m.insert(add, add);
 100                     black_box(m.remove(&remove));
 101                 }
 102             })
 103         }
 104     };
 105 }
 106
 107 bench_suite!(
 108     bench_insert_erase,
 109     insert_erase_fx_serial,
 110     insert_erase_std_serial,
 111     insert_erase_fx_highbits,
 112     insert_erase_std_highbits,
 113     insert_erase_fx_random,
 114     insert_erase_std_random
 115 );
 116
 117 macro_rules! bench_lookup {
 118     ($name:ident, $maptype:ident, $keydist:expr) => {
 119         #[bench]
 120         fn $name(b: &mut Bencher) {
 121             let mut m = $maptype::default();
 122             for i in $keydist.take(SIZE) {
 123                 m.insert(i, i);
 124             }
 125
 126             b.iter(|| {
 127                 for i in $keydist.take(SIZE) {
 128                     black_box(m.get(&i));
 129                 }
 130             })
 131         }
 132     };
 133 }
 134
 135 bench_suite!(
 136     bench_lookup,
 137     lookup_fx_serial,
 138     lookup_std_serial,
 139     lookup_fx_highbits,
 140     lookup_std_highbits,
 141     lookup_fx_random,
 142     lookup_std_random
 143 );
 144
 145 macro_rules! bench_lookup_fail {
 146     ($name:ident, $maptype:ident, $keydist:expr) => {
 147         #[bench]
 148         fn $name(b: &mut Bencher) {
 149             let mut m = $maptype::default();
 150             let mut iter = $keydist;
 151             for i in (&mut iter).take(SIZE) {
 152                 m.insert(i, i);
 153             }
 154
 155             b.iter(|| {
 156                 for i in (&mut iter).take(SIZE) {
 157                     black_box(m.get(&i));
 158                 }
 159             })
 160         }
 161     };
 162 }
 163
 164 bench_suite!(
 165     bench_lookup_fail,
 166     lookup_fail_fx_serial,
 167     lookup_fail_std_serial,
 168     lookup_fail_fx_highbits,
 169     lookup_fail_std_highbits,
 170     lookup_fail_fx_random,
 171     lookup_fail_std_random
 172 );
 173
 174 macro_rules! bench_iter {
 175     ($name:ident, $maptype:ident, $keydist:expr) => {
 176         #[bench]
 177         fn $name(b: &mut Bencher) {
 178             let mut m = $maptype::default();
 179             for i in ($keydist).take(SIZE) {
 180                 m.insert(i, i);
 181             }
 182
 183             b.iter(|| {
 184                 for i in &m {
 185                     black_box(i);
 186                 }
 187             })
 188         }
 189     };
 190 }
 191
 192 bench_suite!(
 193     bench_iter,
 194     iter_fx_serial,
 195     iter_std_serial,
 196     iter_fx_highbits,
 197     iter_std_highbits,
 198     iter_fx_random,
 199     iter_std_random
 200 );