1 use std::collections::BTreeMap;
2 use std::iter::Iterator;
3 use std::ops::RangeBounds;
6 use rand::{seq::SliceRandom, Rng};
7 use test::{black_box, Bencher};
9 macro_rules! map_insert_rand_bench {
10 ($name: ident, $n: expr, $map: ident) => {
12 pub fn $name(b: &mut Bencher) {
14 let mut map = $map::new();
16 let mut rng = crate::bench_rng();
19 let i = rng.gen::<usize>() % n;
25 let k = rng.gen::<usize>() % n;
34 macro_rules! map_insert_seq_bench {
35 ($name: ident, $n: expr, $map: ident) => {
37 pub fn $name(b: &mut Bencher) {
38 let mut map = $map::new();
42 map.insert(i * 2, i * 2);
57 macro_rules! map_from_iter_rand_bench {
58 ($name: ident, $n: expr, $map: ident) => {
60 pub fn $name(b: &mut Bencher) {
63 let mut rng = crate::bench_rng();
64 let mut vec = Vec::with_capacity(n);
67 let i = rng.gen::<usize>() % n;
73 let map: $map<_, _> = vec.iter().copied().collect();
80 macro_rules! map_from_iter_seq_bench {
81 ($name: ident, $n: expr, $map: ident) => {
83 pub fn $name(b: &mut Bencher) {
86 let mut vec = Vec::with_capacity(n);
94 let map: $map<_, _> = vec.iter().copied().collect();
101 macro_rules! map_find_rand_bench {
102 ($name: ident, $n: expr, $map: ident) => {
104 pub fn $name(b: &mut Bencher) {
105 let mut map = $map::new();
109 let mut rng = crate::bench_rng();
110 let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
116 keys.shuffle(&mut rng);
121 let t = map.get(&keys[i]);
129 macro_rules! map_find_seq_bench {
130 ($name: ident, $n: expr, $map: ident) => {
132 pub fn $name(b: &mut Bencher) {
133 let mut map = $map::new();
152 map_insert_rand_bench! {insert_rand_100, 100, BTreeMap}
153 map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap}
155 map_insert_seq_bench! {insert_seq_100, 100, BTreeMap}
156 map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap}
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}
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}
164 map_find_rand_bench! {find_rand_100, 100, BTreeMap}
165 map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap}
167 map_find_seq_bench! {find_seq_100, 100, BTreeMap}
168 map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap}
170 fn bench_iteration(b: &mut Bencher, size: i32) {
171 let mut map = BTreeMap::<i32, i32>::new();
172 let mut rng = crate::bench_rng();
175 map.insert(rng.gen(), rng.gen());
186 pub fn iteration_20(b: &mut Bencher) {
187 bench_iteration(b, 20);
191 pub fn iteration_1000(b: &mut Bencher) {
192 bench_iteration(b, 1000);
196 pub fn iteration_100000(b: &mut Bencher) {
197 bench_iteration(b, 100000);
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();
205 map.insert(rng.gen(), rng.gen());
209 for kv in map.iter_mut() {
216 pub fn iteration_mut_20(b: &mut Bencher) {
217 bench_iteration_mut(b, 20);
221 pub fn iteration_mut_1000(b: &mut Bencher) {
222 bench_iteration_mut(b, 1000);
226 pub fn iteration_mut_100000(b: &mut Bencher) {
227 bench_iteration_mut(b, 100000);
230 fn bench_first_and_last_nightly(b: &mut Bencher, size: i32) {
231 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
234 black_box(map.first_key_value());
235 black_box(map.last_key_value());
240 fn bench_first_and_last_stable(b: &mut Bencher, size: i32) {
241 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
244 black_box(map.iter().next());
245 black_box(map.iter().next_back());
251 pub fn first_and_last_0_nightly(b: &mut Bencher) {
252 bench_first_and_last_nightly(b, 0);
256 pub fn first_and_last_0_stable(b: &mut Bencher) {
257 bench_first_and_last_stable(b, 0);
261 pub fn first_and_last_100_nightly(b: &mut Bencher) {
262 bench_first_and_last_nightly(b, 100);
266 pub fn first_and_last_100_stable(b: &mut Bencher) {
267 bench_first_and_last_stable(b, 100);
271 pub fn first_and_last_10k_nightly(b: &mut Bencher) {
272 bench_first_and_last_nightly(b, 10_000);
276 pub fn first_and_last_10k_stable(b: &mut Bencher) {
277 bench_first_and_last_stable(b, 10_000);
280 const BENCH_RANGE_SIZE: i32 = 145;
281 const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2;
283 fn bench_range<F, R>(b: &mut Bencher, f: F)
285 F: Fn(i32, i32) -> R,
288 let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
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)));
297 debug_assert_eq!(c, BENCH_RANGE_COUNT);
302 pub fn range_included_excluded(b: &mut Bencher) {
303 bench_range(b, |i, j| i..j);
307 pub fn range_included_included(b: &mut Bencher) {
308 bench_range(b, |i, j| i..=j);
312 pub fn range_included_unbounded(b: &mut Bencher) {
313 bench_range(b, |i, _| i..);
317 pub fn range_unbounded_unbounded(b: &mut Bencher) {
318 bench_range(b, |_, _| ..);
321 fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) {
322 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
324 for _ in 0..repeats {
325 let _ = black_box(map.iter());
330 /// Contrast range_unbounded_unbounded with `iter()`.
332 pub fn range_unbounded_vs_iter(b: &mut Bencher) {
333 bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE);
337 pub fn iter_0(b: &mut Bencher) {
338 bench_iter(b, 1_000, 0);
342 pub fn iter_1(b: &mut Bencher) {
343 bench_iter(b, 1_000, 1);
347 pub fn iter_100(b: &mut Bencher) {
348 bench_iter(b, 1_000, 100);
352 pub fn iter_10k(b: &mut Bencher) {
353 bench_iter(b, 1_000, 10_000);
357 pub fn iter_1m(b: &mut Bencher) {
358 bench_iter(b, 1_000, 1_000_000);
361 const FAT: usize = 256;
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<_, _>>()
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<_, _>>()
375 pub fn clone_slim_100(b: &mut Bencher) {
376 let src = slim_map(100);
377 b.iter(|| src.clone())
381 pub fn clone_slim_100_and_clear(b: &mut Bencher) {
382 let src = slim_map(100);
383 b.iter(|| src.clone().clear())
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())
393 pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
394 let src = slim_map(100);
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);
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())
409 pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
410 let src = slim_map(100);
412 let mut map = src.clone();
413 while map.pop_first().is_some() {}
419 pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
420 let src = slim_map(100);
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());
432 pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
433 let src = slim_map(100);
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());
440 assert_eq!(map.len(), 100 / 2);
446 pub fn clone_slim_10k(b: &mut Bencher) {
447 let src = slim_map(10_000);
448 b.iter(|| src.clone())
452 pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
453 let src = slim_map(10_000);
454 b.iter(|| src.clone().clear())
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())
464 pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
465 let src = slim_map(10_000);
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);
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())
480 pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
481 let src = slim_map(10_000);
483 let mut map = src.clone();
484 while map.pop_first().is_some() {}
490 pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
491 let src = slim_map(10_000);
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());
503 pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
504 let src = slim_map(10_000);
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());
511 assert_eq!(map.len(), 10_000 / 2);
517 pub fn clone_fat_val_100(b: &mut Bencher) {
518 let src = fat_val_map(100);
519 b.iter(|| src.clone())
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())
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())
535 pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
536 let src = fat_val_map(100);
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);
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())
551 pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
552 let src = fat_val_map(100);
554 let mut map = src.clone();
555 while map.pop_first().is_some() {}
561 pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
562 let src = fat_val_map(100);
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());
574 pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
575 let src = fat_val_map(100);
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());
582 assert_eq!(map.len(), 100 / 2);