library/alloc/benches/btree/map.rs

   1 use std::collections::BTreeMap;
   2 use std::iter::Iterator;
   3 use std::ops::RangeBounds;
   4 use std::vec::Vec;
   5
   6 use rand::{seq::SliceRandom, thread_rng, Rng};
   7 use test::{black_box, Bencher};
   8
   9 macro_rules! map_insert_rand_bench {
  10     ($name: ident, $n: expr, $map: ident) => {
  11         #[bench]
  12         pub fn $name(b: &mut Bencher) {
  13             let n: usize = $n;
  14             let mut map = $map::new();
  15             // setup
  16             let mut rng = thread_rng();
  17
  18             for _ in 0..n {
  19                 let i = rng.gen::<usize>() % n;
  20                 map.insert(i, i);
  21             }
  22
  23             // measure
  24             b.iter(|| {
  25                 let k = rng.gen::<usize>() % n;
  26                 map.insert(k, k);
  27                 map.remove(&k);
  28             });
  29             black_box(map);
  30         }
  31     };
  32 }
  33
  34 macro_rules! map_insert_seq_bench {
  35     ($name: ident, $n: expr, $map: ident) => {
  36         #[bench]
  37         pub fn $name(b: &mut Bencher) {
  38             let mut map = $map::new();
  39             let n: usize = $n;
  40             // setup
  41             for i in 0..n {
  42                 map.insert(i * 2, i * 2);
  43             }
  44
  45             // measure
  46             let mut i = 1;
  47             b.iter(|| {
  48                 map.insert(i, i);
  49                 map.remove(&i);
  50                 i = (i + 2) % n;
  51             });
  52             black_box(map);
  53         }
  54     };
  55 }
  56
  57 macro_rules! map_find_rand_bench {
  58     ($name: ident, $n: expr, $map: ident) => {
  59         #[bench]
  60         pub fn $name(b: &mut Bencher) {
  61             let mut map = $map::new();
  62             let n: usize = $n;
  63
  64             // setup
  65             let mut rng = thread_rng();
  66             let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
  67
  68             for &k in &keys {
  69                 map.insert(k, k);
  70             }
  71
  72             keys.shuffle(&mut rng);
  73
  74             // measure
  75             let mut i = 0;
  76             b.iter(|| {
  77                 let t = map.get(&keys[i]);
  78                 i = (i + 1) % n;
  79                 black_box(t);
  80             })
  81         }
  82     };
  83 }
  84
  85 macro_rules! map_find_seq_bench {
  86     ($name: ident, $n: expr, $map: ident) => {
  87         #[bench]
  88         pub fn $name(b: &mut Bencher) {
  89             let mut map = $map::new();
  90             let n: usize = $n;
  91
  92             // setup
  93             for i in 0..n {
  94                 map.insert(i, i);
  95             }
  96
  97             // measure
  98             let mut i = 0;
  99             b.iter(|| {
 100                 let x = map.get(&i);
 101                 i = (i + 1) % n;
 102                 black_box(x);
 103             })
 104         }
 105     };
 106 }
 107
 108 map_insert_rand_bench! {insert_rand_100,    100,    BTreeMap}
 109 map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap}
 110
 111 map_insert_seq_bench! {insert_seq_100,    100,    BTreeMap}
 112 map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap}
 113
 114 map_find_rand_bench! {find_rand_100,    100,    BTreeMap}
 115 map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap}
 116
 117 map_find_seq_bench! {find_seq_100,    100,    BTreeMap}
 118 map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap}
 119
 120 fn bench_iteration(b: &mut Bencher, size: i32) {
 121     let mut map = BTreeMap::<i32, i32>::new();
 122     let mut rng = thread_rng();
 123
 124     for _ in 0..size {
 125         map.insert(rng.gen(), rng.gen());
 126     }
 127
 128     b.iter(|| {
 129         for entry in &map {
 130             black_box(entry);
 131         }
 132     });
 133 }
 134
 135 #[bench]
 136 pub fn iteration_20(b: &mut Bencher) {
 137     bench_iteration(b, 20);
 138 }
 139
 140 #[bench]
 141 pub fn iteration_1000(b: &mut Bencher) {
 142     bench_iteration(b, 1000);
 143 }
 144
 145 #[bench]
 146 pub fn iteration_100000(b: &mut Bencher) {
 147     bench_iteration(b, 100000);
 148 }
 149
 150 fn bench_iteration_mut(b: &mut Bencher, size: i32) {
 151     let mut map = BTreeMap::<i32, i32>::new();
 152     let mut rng = thread_rng();
 153
 154     for _ in 0..size {
 155         map.insert(rng.gen(), rng.gen());
 156     }
 157
 158     b.iter(|| {
 159         for kv in map.iter_mut() {
 160             black_box(kv);
 161         }
 162     });
 163 }
 164
 165 #[bench]
 166 pub fn iteration_mut_20(b: &mut Bencher) {
 167     bench_iteration_mut(b, 20);
 168 }
 169
 170 #[bench]
 171 pub fn iteration_mut_1000(b: &mut Bencher) {
 172     bench_iteration_mut(b, 1000);
 173 }
 174
 175 #[bench]
 176 pub fn iteration_mut_100000(b: &mut Bencher) {
 177     bench_iteration_mut(b, 100000);
 178 }
 179
 180 fn bench_first_and_last(b: &mut Bencher, size: i32) {
 181     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 182     b.iter(|| {
 183         for _ in 0..10 {
 184             black_box(map.first_key_value());
 185             black_box(map.last_key_value());
 186         }
 187     });
 188 }
 189
 190 #[bench]
 191 pub fn first_and_last_0(b: &mut Bencher) {
 192     bench_first_and_last(b, 0);
 193 }
 194
 195 #[bench]
 196 pub fn first_and_last_100(b: &mut Bencher) {
 197     bench_first_and_last(b, 100);
 198 }
 199
 200 #[bench]
 201 pub fn first_and_last_10k(b: &mut Bencher) {
 202     bench_first_and_last(b, 10_000);
 203 }
 204
 205 const BENCH_RANGE_SIZE: i32 = 145;
 206 const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2;
 207
 208 fn bench_range<F, R>(b: &mut Bencher, f: F)
 209 where
 210     F: Fn(i32, i32) -> R,
 211     R: RangeBounds<i32>,
 212 {
 213     let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
 214     b.iter(|| {
 215         let mut c = 0;
 216         for i in 0..BENCH_RANGE_SIZE {
 217             for j in i + 1..BENCH_RANGE_SIZE {
 218                 black_box(map.range(f(i, j)));
 219                 c += 1;
 220             }
 221         }
 222         debug_assert_eq!(c, BENCH_RANGE_COUNT);
 223     });
 224 }
 225
 226 #[bench]
 227 pub fn range_included_excluded(b: &mut Bencher) {
 228     bench_range(b, |i, j| i..j);
 229 }
 230
 231 #[bench]
 232 pub fn range_included_included(b: &mut Bencher) {
 233     bench_range(b, |i, j| i..=j);
 234 }
 235
 236 #[bench]
 237 pub fn range_included_unbounded(b: &mut Bencher) {
 238     bench_range(b, |i, _| i..);
 239 }
 240
 241 #[bench]
 242 pub fn range_unbounded_unbounded(b: &mut Bencher) {
 243     bench_range(b, |_, _| ..);
 244 }
 245
 246 fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) {
 247     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 248     b.iter(|| {
 249         for _ in 0..repeats {
 250             black_box(map.iter());
 251         }
 252     });
 253 }
 254
 255 /// Contrast range_unbounded_unbounded with `iter()`.
 256 #[bench]
 257 pub fn range_unbounded_vs_iter(b: &mut Bencher) {
 258     bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE);
 259 }
 260
 261 #[bench]
 262 pub fn iter_0(b: &mut Bencher) {
 263     bench_iter(b, 1_000, 0);
 264 }
 265
 266 #[bench]
 267 pub fn iter_1(b: &mut Bencher) {
 268     bench_iter(b, 1_000, 1);
 269 }
 270
 271 #[bench]
 272 pub fn iter_100(b: &mut Bencher) {
 273     bench_iter(b, 1_000, 100);
 274 }
 275
 276 #[bench]
 277 pub fn iter_10k(b: &mut Bencher) {
 278     bench_iter(b, 1_000, 10_000);
 279 }
 280
 281 #[bench]
 282 pub fn iter_1m(b: &mut Bencher) {
 283     bench_iter(b, 1_000, 1_000_000);
 284 }
 285
 286 const FAT: usize = 256;
 287
 288 // The returned map has small keys and values.
 289 // Benchmarks on it have a counterpart in set.rs with the same keys and no values at all.
 290 fn slim_map(n: usize) -> BTreeMap<usize, usize> {
 291     (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
 292 }
 293
 294 // The returned map has small keys and large values.
 295 fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> {
 296     (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
 297 }
 298
 299 #[bench]
 300 pub fn clone_slim_100(b: &mut Bencher) {
 301     let src = slim_map(100);
 302     b.iter(|| src.clone())
 303 }
 304
 305 #[bench]
 306 pub fn clone_slim_100_and_clear(b: &mut Bencher) {
 307     let src = slim_map(100);
 308     b.iter(|| src.clone().clear())
 309 }
 310
 311 #[bench]
 312 pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
 313     let src = slim_map(100);
 314     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 315 }
 316
 317 #[bench]
 318 pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
 319     let src = slim_map(100);
 320     b.iter(|| {
 321         let mut map = src.clone();
 322         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 323         assert_eq!(map.len(), 100 / 2);
 324     })
 325 }
 326
 327 #[bench]
 328 pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
 329     let src = slim_map(100);
 330     b.iter(|| src.clone().into_iter().count())
 331 }
 332
 333 #[bench]
 334 pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
 335     let src = slim_map(100);
 336     b.iter(|| {
 337         let mut map = src.clone();
 338         while map.pop_first().is_some() {}
 339         map
 340     });
 341 }
 342
 343 #[bench]
 344 pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
 345     let src = slim_map(100);
 346     b.iter(|| {
 347         let mut map = src.clone();
 348         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 349             let v = map.remove(&elt);
 350             debug_assert!(v.is_some());
 351         }
 352         map
 353     });
 354 }
 355
 356 #[bench]
 357 pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
 358     let src = slim_map(100);
 359     b.iter(|| {
 360         let mut map = src.clone();
 361         for i in (0..100).step_by(2) {
 362             let v = map.remove(&i);
 363             debug_assert!(v.is_some());
 364         }
 365         assert_eq!(map.len(), 100 / 2);
 366         map
 367     })
 368 }
 369
 370 #[bench]
 371 pub fn clone_slim_10k(b: &mut Bencher) {
 372     let src = slim_map(10_000);
 373     b.iter(|| src.clone())
 374 }
 375
 376 #[bench]
 377 pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
 378     let src = slim_map(10_000);
 379     b.iter(|| src.clone().clear())
 380 }
 381
 382 #[bench]
 383 pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
 384     let src = slim_map(10_000);
 385     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 386 }
 387
 388 #[bench]
 389 pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
 390     let src = slim_map(10_000);
 391     b.iter(|| {
 392         let mut map = src.clone();
 393         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
 394         assert_eq!(map.len(), 10_000 / 2);
 395     })
 396 }
 397
 398 #[bench]
 399 pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
 400     let src = slim_map(10_000);
 401     b.iter(|| src.clone().into_iter().count())
 402 }
 403
 404 #[bench]
 405 pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
 406     let src = slim_map(10_000);
 407     b.iter(|| {
 408         let mut map = src.clone();
 409         while map.pop_first().is_some() {}
 410         map
 411     });
 412 }
 413
 414 #[bench]
 415 pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
 416     let src = slim_map(10_000);
 417     b.iter(|| {
 418         let mut map = src.clone();
 419         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 420             let v = map.remove(&elt);
 421             debug_assert!(v.is_some());
 422         }
 423         map
 424     });
 425 }
 426
 427 #[bench]
 428 pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
 429     let src = slim_map(10_000);
 430     b.iter(|| {
 431         let mut map = src.clone();
 432         for i in (0..10_000).step_by(2) {
 433             let v = map.remove(&i);
 434             debug_assert!(v.is_some());
 435         }
 436         assert_eq!(map.len(), 10_000 / 2);
 437         map
 438     })
 439 }
 440
 441 #[bench]
 442 pub fn clone_fat_val_100(b: &mut Bencher) {
 443     let src = fat_val_map(100);
 444     b.iter(|| src.clone())
 445 }
 446
 447 #[bench]
 448 pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
 449     let src = fat_val_map(100);
 450     b.iter(|| src.clone().clear())
 451 }
 452
 453 #[bench]
 454 pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
 455     let src = fat_val_map(100);
 456     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 457 }
 458
 459 #[bench]
 460 pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
 461     let src = fat_val_map(100);
 462     b.iter(|| {
 463         let mut map = src.clone();
 464         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 465         assert_eq!(map.len(), 100 / 2);
 466     })
 467 }
 468
 469 #[bench]
 470 pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
 471     let src = fat_val_map(100);
 472     b.iter(|| src.clone().into_iter().count())
 473 }
 474
 475 #[bench]
 476 pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
 477     let src = fat_val_map(100);
 478     b.iter(|| {
 479         let mut map = src.clone();
 480         while map.pop_first().is_some() {}
 481         map
 482     });
 483 }
 484
 485 #[bench]
 486 pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
 487     let src = fat_val_map(100);
 488     b.iter(|| {
 489         let mut map = src.clone();
 490         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 491             let v = map.remove(&elt);
 492             debug_assert!(v.is_some());
 493         }
 494         map
 495     });
 496 }
 497
 498 #[bench]
 499 pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
 500     let src = fat_val_map(100);
 501     b.iter(|| {
 502         let mut map = src.clone();
 503         for i in (0..100).step_by(2) {
 504             let v = map.remove(&i);
 505             debug_assert!(v.is_some());
 506         }
 507         assert_eq!(map.len(), 100 / 2);
 508         map
 509     })
 510 }