src/libcollections/benches/btree/map.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11
  12 use std::iter::Iterator;
  13 use std::vec::Vec;
  14 use std::collections::BTreeMap;
  15 use std::__rand::{Rng, thread_rng};
  16 use test::{Bencher, black_box};
  17
  18 macro_rules! map_insert_rand_bench {
  19     ($name: ident, $n: expr, $map: ident) => (
  20         #[bench]
  21         pub fn $name(b: &mut Bencher) {
  22             let n: usize = $n;
  23             let mut map = $map::new();
  24             // setup
  25             let mut rng = thread_rng();
  26
  27             for _ in 0..n {
  28                 let i = rng.gen::<usize>() % n;
  29                 map.insert(i, i);
  30             }
  31
  32             // measure
  33             b.iter(|| {
  34                 let k = rng.gen::<usize>() % n;
  35                 map.insert(k, k);
  36                 map.remove(&k);
  37             });
  38             black_box(map);
  39         }
  40     )
  41 }
  42
  43 macro_rules! map_insert_seq_bench {
  44     ($name: ident, $n: expr, $map: ident) => (
  45         #[bench]
  46         pub fn $name(b: &mut Bencher) {
  47             let mut map = $map::new();
  48             let n: usize = $n;
  49             // setup
  50             for i in 0..n {
  51                 map.insert(i * 2, i * 2);
  52             }
  53
  54             // measure
  55             let mut i = 1;
  56             b.iter(|| {
  57                 map.insert(i, i);
  58                 map.remove(&i);
  59                 i = (i + 2) % n;
  60             });
  61             black_box(map);
  62         }
  63     )
  64 }
  65
  66 macro_rules! map_find_rand_bench {
  67     ($name: ident, $n: expr, $map: ident) => (
  68         #[bench]
  69         pub fn $name(b: &mut Bencher) {
  70             let mut map = $map::new();
  71             let n: usize = $n;
  72
  73             // setup
  74             let mut rng = thread_rng();
  75             let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
  76
  77             for &k in &keys {
  78                 map.insert(k, k);
  79             }
  80
  81             rng.shuffle(&mut keys);
  82
  83             // measure
  84             let mut i = 0;
  85             b.iter(|| {
  86                 let t = map.get(&keys[i]);
  87                 i = (i + 1) % n;
  88                 black_box(t);
  89             })
  90         }
  91     )
  92 }
  93
  94 macro_rules! map_find_seq_bench {
  95     ($name: ident, $n: expr, $map: ident) => (
  96         #[bench]
  97         pub fn $name(b: &mut Bencher) {
  98             let mut map = $map::new();
  99             let n: usize = $n;
 100
 101             // setup
 102             for i in 0..n {
 103                 map.insert(i, i);
 104             }
 105
 106             // measure
 107             let mut i = 0;
 108             b.iter(|| {
 109                 let x = map.get(&i);
 110                 i = (i + 1) % n;
 111                 black_box(x);
 112             })
 113         }
 114     )
 115 }
 116
 117 map_insert_rand_bench!{insert_rand_100,    100,    BTreeMap}
 118 map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
 119
 120 map_insert_seq_bench!{insert_seq_100,    100,    BTreeMap}
 121 map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
 122
 123 map_find_rand_bench!{find_rand_100,    100,    BTreeMap}
 124 map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
 125
 126 map_find_seq_bench!{find_seq_100,    100,    BTreeMap}
 127 map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
 128
 129 fn bench_iter(b: &mut Bencher, size: i32) {
 130     let mut map = BTreeMap::<i32, i32>::new();
 131     let mut rng = thread_rng();
 132
 133     for _ in 0..size {
 134         map.insert(rng.gen(), rng.gen());
 135     }
 136
 137     b.iter(|| {
 138         for entry in &map {
 139             black_box(entry);
 140         }
 141     });
 142 }
 143
 144 #[bench]
 145 pub fn iter_20(b: &mut Bencher) {
 146     bench_iter(b, 20);
 147 }
 148
 149 #[bench]
 150 pub fn iter_1000(b: &mut Bencher) {
 151     bench_iter(b, 1000);
 152 }
 153
 154 #[bench]
 155 pub fn iter_100000(b: &mut Bencher) {
 156     bench_iter(b, 100000);
 157 }