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, 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 = crate::bench_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_from_iter_rand_bench {
  58     ($name: ident, $n: expr, $map: ident) => {
  59         #[bench]
  60         pub fn $name(b: &mut Bencher) {
  61             let n: usize = $n;
  62             // setup
  63             let mut rng = crate::bench_rng();
  64             let mut vec = Vec::with_capacity(n);
  65
  66             for _ in 0..n {
  67                 let i = rng.gen::<usize>() % n;
  68                 vec.push((i, i));
  69             }
  70
  71             // measure
  72             b.iter(|| {
  73                 let map: $map<_, _> = vec.iter().copied().collect();
  74                 black_box(map);
  75             });
  76         }
  77     };
  78 }
  79
  80 macro_rules! map_from_iter_seq_bench {
  81     ($name: ident, $n: expr, $map: ident) => {
  82         #[bench]
  83         pub fn $name(b: &mut Bencher) {
  84             let n: usize = $n;
  85             // setup
  86             let mut vec = Vec::with_capacity(n);
  87
  88             for i in 0..n {
  89                 vec.push((i, i));
  90             }
  91
  92             // measure
  93             b.iter(|| {
  94                 let map: $map<_, _> = vec.iter().copied().collect();
  95                 black_box(map);
  96             });
  97         }
  98     };
  99 }
 100
 101 macro_rules! map_find_rand_bench {
 102     ($name: ident, $n: expr, $map: ident) => {
 103         #[bench]
 104         pub fn $name(b: &mut Bencher) {
 105             let mut map = $map::new();
 106             let n: usize = $n;
 107
 108             // setup
 109             let mut rng = crate::bench_rng();
 110             let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
 111
 112             for &k in &keys {
 113                 map.insert(k, k);
 114             }
 115
 116             keys.shuffle(&mut rng);
 117
 118             // measure
 119             let mut i = 0;
 120             b.iter(|| {
 121                 let t = map.get(&keys[i]);
 122                 i = (i + 1) % n;
 123                 black_box(t);
 124             })
 125         }
 126     };
 127 }
 128
 129 macro_rules! map_find_seq_bench {
 130     ($name: ident, $n: expr, $map: ident) => {
 131         #[bench]
 132         pub fn $name(b: &mut Bencher) {
 133             let mut map = $map::new();
 134             let n: usize = $n;
 135
 136             // setup
 137             for i in 0..n {
 138                 map.insert(i, i);
 139             }
 140
 141             // measure
 142             let mut i = 0;
 143             b.iter(|| {
 144                 let x = map.get(&i);
 145                 i = (i + 1) % n;
 146                 black_box(x);
 147             })
 148         }
 149     };
 150 }
 151
 152 map_insert_rand_bench! {insert_rand_100,    100,    BTreeMap}
 153 map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap}
 154
 155 map_insert_seq_bench! {insert_seq_100,    100,    BTreeMap}
 156 map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap}
 157
 158 map_from_iter_rand_bench! {from_iter_rand_100,    100,    BTreeMap}
 159 map_from_iter_rand_bench! {from_iter_rand_10_000, 10_000, BTreeMap}
 160
 161 map_from_iter_seq_bench! {from_iter_seq_100,    100,    BTreeMap}
 162 map_from_iter_seq_bench! {from_iter_seq_10_000, 10_000, BTreeMap}
 163
 164 map_find_rand_bench! {find_rand_100,    100,    BTreeMap}
 165 map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap}
 166
 167 map_find_seq_bench! {find_seq_100,    100,    BTreeMap}
 168 map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap}
 169
 170 fn bench_iteration(b: &mut Bencher, size: i32) {
 171     let mut map = BTreeMap::<i32, i32>::new();
 172     let mut rng = crate::bench_rng();
 173
 174     for _ in 0..size {
 175         map.insert(rng.gen(), rng.gen());
 176     }
 177
 178     b.iter(|| {
 179         for entry in &map {
 180             black_box(entry);
 181         }
 182     });
 183 }
 184
 185 #[bench]
 186 pub fn iteration_20(b: &mut Bencher) {
 187     bench_iteration(b, 20);
 188 }
 189
 190 #[bench]
 191 pub fn iteration_1000(b: &mut Bencher) {
 192     bench_iteration(b, 1000);
 193 }
 194
 195 #[bench]
 196 pub fn iteration_100000(b: &mut Bencher) {
 197     bench_iteration(b, 100000);
 198 }
 199
 200 fn bench_iteration_mut(b: &mut Bencher, size: i32) {
 201     let mut map = BTreeMap::<i32, i32>::new();
 202     let mut rng = crate::bench_rng();
 203
 204     for _ in 0..size {
 205         map.insert(rng.gen(), rng.gen());
 206     }
 207
 208     b.iter(|| {
 209         for kv in map.iter_mut() {
 210             black_box(kv);
 211         }
 212     });
 213 }
 214
 215 #[bench]
 216 pub fn iteration_mut_20(b: &mut Bencher) {
 217     bench_iteration_mut(b, 20);
 218 }
 219
 220 #[bench]
 221 pub fn iteration_mut_1000(b: &mut Bencher) {
 222     bench_iteration_mut(b, 1000);
 223 }
 224
 225 #[bench]
 226 pub fn iteration_mut_100000(b: &mut Bencher) {
 227     bench_iteration_mut(b, 100000);
 228 }
 229
 230 fn bench_first_and_last_nightly(b: &mut Bencher, size: i32) {
 231     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 232     b.iter(|| {
 233         for _ in 0..10 {
 234             black_box(map.first_key_value());
 235             black_box(map.last_key_value());
 236         }
 237     });
 238 }
 239
 240 fn bench_first_and_last_stable(b: &mut Bencher, size: i32) {
 241     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 242     b.iter(|| {
 243         for _ in 0..10 {
 244             black_box(map.iter().next());
 245             black_box(map.iter().next_back());
 246         }
 247     });
 248 }
 249
 250 #[bench]
 251 pub fn first_and_last_0_nightly(b: &mut Bencher) {
 252     bench_first_and_last_nightly(b, 0);
 253 }
 254
 255 #[bench]
 256 pub fn first_and_last_0_stable(b: &mut Bencher) {
 257     bench_first_and_last_stable(b, 0);
 258 }
 259
 260 #[bench]
 261 pub fn first_and_last_100_nightly(b: &mut Bencher) {
 262     bench_first_and_last_nightly(b, 100);
 263 }
 264
 265 #[bench]
 266 pub fn first_and_last_100_stable(b: &mut Bencher) {
 267     bench_first_and_last_stable(b, 100);
 268 }
 269
 270 #[bench]
 271 pub fn first_and_last_10k_nightly(b: &mut Bencher) {
 272     bench_first_and_last_nightly(b, 10_000);
 273 }
 274
 275 #[bench]
 276 pub fn first_and_last_10k_stable(b: &mut Bencher) {
 277     bench_first_and_last_stable(b, 10_000);
 278 }
 279
 280 const BENCH_RANGE_SIZE: i32 = 145;
 281 const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2;
 282
 283 fn bench_range<F, R>(b: &mut Bencher, f: F)
 284 where
 285     F: Fn(i32, i32) -> R,
 286     R: RangeBounds<i32>,
 287 {
 288     let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
 289     b.iter(|| {
 290         let mut c = 0;
 291         for i in 0..BENCH_RANGE_SIZE {
 292             for j in i + 1..BENCH_RANGE_SIZE {
 293                 let _ = black_box(map.range(f(i, j)));
 294                 c += 1;
 295             }
 296         }
 297         debug_assert_eq!(c, BENCH_RANGE_COUNT);
 298     });
 299 }
 300
 301 #[bench]
 302 pub fn range_included_excluded(b: &mut Bencher) {
 303     bench_range(b, |i, j| i..j);
 304 }
 305
 306 #[bench]
 307 pub fn range_included_included(b: &mut Bencher) {
 308     bench_range(b, |i, j| i..=j);
 309 }
 310
 311 #[bench]
 312 pub fn range_included_unbounded(b: &mut Bencher) {
 313     bench_range(b, |i, _| i..);
 314 }
 315
 316 #[bench]
 317 pub fn range_unbounded_unbounded(b: &mut Bencher) {
 318     bench_range(b, |_, _| ..);
 319 }
 320
 321 fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) {
 322     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 323     b.iter(|| {
 324         for _ in 0..repeats {
 325             let _ = black_box(map.iter());
 326         }
 327     });
 328 }
 329
 330 /// Contrast range_unbounded_unbounded with `iter()`.
 331 #[bench]
 332 pub fn range_unbounded_vs_iter(b: &mut Bencher) {
 333     bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE);
 334 }
 335
 336 #[bench]
 337 pub fn iter_0(b: &mut Bencher) {
 338     bench_iter(b, 1_000, 0);
 339 }
 340
 341 #[bench]
 342 pub fn iter_1(b: &mut Bencher) {
 343     bench_iter(b, 1_000, 1);
 344 }
 345
 346 #[bench]
 347 pub fn iter_100(b: &mut Bencher) {
 348     bench_iter(b, 1_000, 100);
 349 }
 350
 351 #[bench]
 352 pub fn iter_10k(b: &mut Bencher) {
 353     bench_iter(b, 1_000, 10_000);
 354 }
 355
 356 #[bench]
 357 pub fn iter_1m(b: &mut Bencher) {
 358     bench_iter(b, 1_000, 1_000_000);
 359 }
 360
 361 const FAT: usize = 256;
 362
 363 // The returned map has small keys and values.
 364 // Benchmarks on it have a counterpart in set.rs with the same keys and no values at all.
 365 fn slim_map(n: usize) -> BTreeMap<usize, usize> {
 366     (0..n).map(|i| (i, i)).collect::<BTreeMap<_, _>>()
 367 }
 368
 369 // The returned map has small keys and large values.
 370 fn fat_val_map(n: usize) -> BTreeMap<usize, [usize; FAT]> {
 371     (0..n).map(|i| (i, [i; FAT])).collect::<BTreeMap<_, _>>()
 372 }
 373
 374 #[bench]
 375 pub fn clone_slim_100(b: &mut Bencher) {
 376     let src = slim_map(100);
 377     b.iter(|| src.clone())
 378 }
 379
 380 #[bench]
 381 pub fn clone_slim_100_and_clear(b: &mut Bencher) {
 382     let src = slim_map(100);
 383     b.iter(|| src.clone().clear())
 384 }
 385
 386 #[bench]
 387 pub fn clone_slim_100_and_drain_all(b: &mut Bencher) {
 388     let src = slim_map(100);
 389     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 390 }
 391
 392 #[bench]
 393 pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
 394     let src = slim_map(100);
 395     b.iter(|| {
 396         let mut map = src.clone();
 397         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 398         assert_eq!(map.len(), 100 / 2);
 399     })
 400 }
 401
 402 #[bench]
 403 pub fn clone_slim_100_and_into_iter(b: &mut Bencher) {
 404     let src = slim_map(100);
 405     b.iter(|| src.clone().into_iter().count())
 406 }
 407
 408 #[bench]
 409 pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
 410     let src = slim_map(100);
 411     b.iter(|| {
 412         let mut map = src.clone();
 413         while map.pop_first().is_some() {}
 414         map
 415     });
 416 }
 417
 418 #[bench]
 419 pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
 420     let src = slim_map(100);
 421     b.iter(|| {
 422         let mut map = src.clone();
 423         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 424             let v = map.remove(&elt);
 425             debug_assert!(v.is_some());
 426         }
 427         map
 428     });
 429 }
 430
 431 #[bench]
 432 pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
 433     let src = slim_map(100);
 434     b.iter(|| {
 435         let mut map = src.clone();
 436         for i in (0..100).step_by(2) {
 437             let v = map.remove(&i);
 438             debug_assert!(v.is_some());
 439         }
 440         assert_eq!(map.len(), 100 / 2);
 441         map
 442     })
 443 }
 444
 445 #[bench]
 446 pub fn clone_slim_10k(b: &mut Bencher) {
 447     let src = slim_map(10_000);
 448     b.iter(|| src.clone())
 449 }
 450
 451 #[bench]
 452 pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
 453     let src = slim_map(10_000);
 454     b.iter(|| src.clone().clear())
 455 }
 456
 457 #[bench]
 458 pub fn clone_slim_10k_and_drain_all(b: &mut Bencher) {
 459     let src = slim_map(10_000);
 460     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 461 }
 462
 463 #[bench]
 464 pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
 465     let src = slim_map(10_000);
 466     b.iter(|| {
 467         let mut map = src.clone();
 468         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 10_000 / 2);
 469         assert_eq!(map.len(), 10_000 / 2);
 470     })
 471 }
 472
 473 #[bench]
 474 pub fn clone_slim_10k_and_into_iter(b: &mut Bencher) {
 475     let src = slim_map(10_000);
 476     b.iter(|| src.clone().into_iter().count())
 477 }
 478
 479 #[bench]
 480 pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
 481     let src = slim_map(10_000);
 482     b.iter(|| {
 483         let mut map = src.clone();
 484         while map.pop_first().is_some() {}
 485         map
 486     });
 487 }
 488
 489 #[bench]
 490 pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
 491     let src = slim_map(10_000);
 492     b.iter(|| {
 493         let mut map = src.clone();
 494         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 495             let v = map.remove(&elt);
 496             debug_assert!(v.is_some());
 497         }
 498         map
 499     });
 500 }
 501
 502 #[bench]
 503 pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
 504     let src = slim_map(10_000);
 505     b.iter(|| {
 506         let mut map = src.clone();
 507         for i in (0..10_000).step_by(2) {
 508             let v = map.remove(&i);
 509             debug_assert!(v.is_some());
 510         }
 511         assert_eq!(map.len(), 10_000 / 2);
 512         map
 513     })
 514 }
 515
 516 #[bench]
 517 pub fn clone_fat_val_100(b: &mut Bencher) {
 518     let src = fat_val_map(100);
 519     b.iter(|| src.clone())
 520 }
 521
 522 #[bench]
 523 pub fn clone_fat_val_100_and_clear(b: &mut Bencher) {
 524     let src = fat_val_map(100);
 525     b.iter(|| src.clone().clear())
 526 }
 527
 528 #[bench]
 529 pub fn clone_fat_val_100_and_drain_all(b: &mut Bencher) {
 530     let src = fat_val_map(100);
 531     b.iter(|| src.clone().drain_filter(|_, _| true).count())
 532 }
 533
 534 #[bench]
 535 pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
 536     let src = fat_val_map(100);
 537     b.iter(|| {
 538         let mut map = src.clone();
 539         assert_eq!(map.drain_filter(|i, _| i % 2 == 0).count(), 100 / 2);
 540         assert_eq!(map.len(), 100 / 2);
 541     })
 542 }
 543
 544 #[bench]
 545 pub fn clone_fat_val_100_and_into_iter(b: &mut Bencher) {
 546     let src = fat_val_map(100);
 547     b.iter(|| src.clone().into_iter().count())
 548 }
 549
 550 #[bench]
 551 pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
 552     let src = fat_val_map(100);
 553     b.iter(|| {
 554         let mut map = src.clone();
 555         while map.pop_first().is_some() {}
 556         map
 557     });
 558 }
 559
 560 #[bench]
 561 pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
 562     let src = fat_val_map(100);
 563     b.iter(|| {
 564         let mut map = src.clone();
 565         while let Some(elt) = map.iter().map(|(&i, _)| i).next() {
 566             let v = map.remove(&elt);
 567             debug_assert!(v.is_some());
 568         }
 569         map
 570     });
 571 }
 572
 573 #[bench]
 574 pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
 575     let src = fat_val_map(100);
 576     b.iter(|| {
 577         let mut map = src.clone();
 578         for i in (0..100).step_by(2) {
 579             let v = map.remove(&i);
 580             debug_assert!(v.is_some());
 581         }
 582         assert_eq!(map.len(), 100 / 2);
 583         map
 584     })
 585 }