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 // The returned map has large keys and values.
 300 fn fat_map(n: usize) -> BTreeMap<[usize; FAT], [usize; FAT]> {
 301     (0..n).map(|i| ([i; FAT], [i; FAT])).collect::<BTreeMap<_, _>>()
 302 }
 303
 304 #[bench]
 305 pub fn clone_slim_100(b: &mut Bencher) {
 306     let src = slim_map(100);
 307     b.iter(|| src.clone())
 308 }
 309
 310 #[bench]
 311 pub fn clone_slim_100_and_clear(b: &mut Bencher) {
 312     let src = slim_map(100);
 313     b.iter(|| src.clone().clear())
 314 }
 315
 316 #[bench]
 317 pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
 318     let src = slim_map(100);
 319     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 320 }
 321
 322 #[bench]
 323 pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
 324     let src = slim_map(100);
 325     b.iter(|| {
 326         let mut map = src.clone();
 327         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 328         assert_eq!(map.len(), 100 / 2);
 329     })
 330 }
 331
 332 #[bench]
 333 pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
 334     let src = slim_map(100);
 335     b.iter(|| src.clone().into_iter().count())
 336 }
 337
 338 #[bench]
 339 pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
 340     let src = slim_map(100);
 341     b.iter(|| {
 342         let mut map = src.clone();
 343         while map.pop_first().is_some() {}
 344         map
 345     });
 346 }
 347
 348 #[bench]
 349 pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
 350     let src = slim_map(100);
 351     b.iter(|| {
 352         let mut map = src.clone();
 353         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 354             let v = map.remove(&elt);
 355             debug_assert!(v.is_some());
 356         }
 357         map
 358     });
 359 }
 360
 361 #[bench]
 362 pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
 363     let src = slim_map(100);
 364     b.iter(|| {
 365         let mut map = src.clone();
 366         for i in (0..100).step_by(2) {
 367             let v = map.remove(&i);
 368             debug_assert!(v.is_some());
 369         }
 370         assert_eq!(map.len(), 100 / 2);
 371         map
 372     })
 373 }
 374
 375 #[bench]
 376 pub fn clone_slim_10k(b: &mut Bencher) {
 377     let src = slim_map(10_000);
 378     b.iter(|| src.clone())
 379 }
 380
 381 #[bench]
 382 pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
 383     let src = slim_map(10_000);
 384     b.iter(|| src.clone().clear())
 385 }
 386
 387 #[bench]
 388 pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
 389     let src = slim_map(10_000);
 390     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 391 }
 392
 393 #[bench]
 394 pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
 395     let src = slim_map(10_000);
 396     b.iter(|| {
 397         let mut map = src.clone();
 398         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
 399         assert_eq!(map.len(), 10_000 / 2);
 400     })
 401 }
 402
 403 #[bench]
 404 pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
 405     let src = slim_map(10_000);
 406     b.iter(|| src.clone().into_iter().count())
 407 }
 408
 409 #[bench]
 410 pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
 411     let src = slim_map(10_000);
 412     b.iter(|| {
 413         let mut map = src.clone();
 414         while map.pop_first().is_some() {}
 415         map
 416     });
 417 }
 418
 419 #[bench]
 420 pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
 421     let src = slim_map(10_000);
 422     b.iter(|| {
 423         let mut map = src.clone();
 424         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 425             let v = map.remove(&elt);
 426             debug_assert!(v.is_some());
 427         }
 428         map
 429     });
 430 }
 431
 432 #[bench]
 433 pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
 434     let src = slim_map(10_000);
 435     b.iter(|| {
 436         let mut map = src.clone();
 437         for i in (0..10_000).step_by(2) {
 438             let v = map.remove(&i);
 439             debug_assert!(v.is_some());
 440         }
 441         assert_eq!(map.len(), 10_000 / 2);
 442         map
 443     })
 444 }
 445
 446 #[bench]
 447 pub fn clone_fat_val_100(b: &mut Bencher) {
 448     let src = fat_val_map(100);
 449     b.iter(|| src.clone())
 450 }
 451
 452 #[bench]
 453 pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
 454     let src = fat_val_map(100);
 455     b.iter(|| src.clone().clear())
 456 }
 457
 458 #[bench]
 459 pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
 460     let src = fat_val_map(100);
 461     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 462 }
 463
 464 #[bench]
 465 pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
 466     let src = fat_val_map(100);
 467     b.iter(|| {
 468         let mut map = src.clone();
 469         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 470         assert_eq!(map.len(), 100 / 2);
 471     })
 472 }
 473
 474 #[bench]
 475 pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
 476     let src = fat_val_map(100);
 477     b.iter(|| src.clone().into_iter().count())
 478 }
 479
 480 #[bench]
 481 pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
 482     let src = fat_val_map(100);
 483     b.iter(|| {
 484         let mut map = src.clone();
 485         while map.pop_first().is_some() {}
 486         map
 487     });
 488 }
 489
 490 #[bench]
 491 pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
 492     let src = fat_val_map(100);
 493     b.iter(|| {
 494         let mut map = src.clone();
 495         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 496             let v = map.remove(&elt);
 497             debug_assert!(v.is_some());
 498         }
 499         map
 500     });
 501 }
 502
 503 #[bench]
 504 pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
 505     let src = fat_val_map(100);
 506     b.iter(|| {
 507         let mut map = src.clone();
 508         for i in (0..100).step_by(2) {
 509             let v = map.remove(&i);
 510             debug_assert!(v.is_some());
 511         }
 512         assert_eq!(map.len(), 100 / 2);
 513         map
 514     })
 515 }
 516
 517 #[bench]
 518 pub fn clone_fat_100(b: &mut Bencher) {
 519     let src = fat_map(100);
 520     b.iter(|| src.clone())
 521 }
 522
 523 #[bench]
 524 pub fn clone_fat_100_and_clear(b: &mut Bencher) {
 525     let src = fat_map(100);
 526     b.iter(|| src.clone().clear())
 527 }
 528
 529 #[bench]
 530 pub fn clone_fat_100_and_drain_all(b: &mut Bencher) {
 531     let src = fat_map(100);
 532     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 533 }
 534
 535 #[bench]
 536 pub fn clone_fat_100_and_drain_half(b: &mut Bencher) {
 537     let src = fat_map(100);
 538     b.iter(|| {
 539         let mut map = src.clone();
 540         assert_eq!(map.drain_filter(|i, _| i[0] % 2 == 0).count(), 100 / 2);
 541         assert_eq!(map.len(), 100 / 2);
 542     })
 543 }
 544
 545 #[bench]
 546 pub fn clone_fat_100_and_into_iter(b: &mut Bencher) {
 547     let src = fat_map(100);
 548     b.iter(|| src.clone().into_iter().count())
 549 }
 550
 551 #[bench]
 552 pub fn clone_fat_100_and_pop_all(b: &mut Bencher) {
 553     let src = fat_map(100);
 554     b.iter(|| {
 555         let mut map = src.clone();
 556         while map.pop_first().is_some() {}
 557         map
 558     });
 559 }
 560
 561 #[bench]
 562 pub fn clone_fat_100_and_remove_all(b: &mut Bencher) {
 563     let src = fat_map(100);
 564     b.iter(|| {
 565         let mut map = src.clone();
 566         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 567             let v = map.remove(&elt);
 568             debug_assert!(v.is_some());
 569         }
 570         map
 571     });
 572 }
 573
 574 #[bench]
 575 pub fn clone_fat_100_and_remove_half(b: &mut Bencher) {
 576     let src = fat_map(100);
 577     b.iter(|| {
 578         let mut map = src.clone();
 579         for i in (0..100).step_by(2) {
 580             let v = map.remove(&[i; FAT]);
 581             debug_assert!(v.is_some());
 582         }
 583         assert_eq!(map.len(), 100 / 2);
 584         map
 585     })
 586 }