1 use std::collections::BTreeMap;
2 use std::iter::Iterator;
3 use std::ops::RangeBounds;
6 use rand::{seq::SliceRandom, thread_rng, 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 = thread_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_find_rand_bench {
58 ($name: ident, $n: expr, $map: ident) => {
60 pub fn $name(b: &mut Bencher) {
61 let mut map = $map::new();
65 let mut rng = thread_rng();
66 let mut keys: Vec<_> = (0..n).map(|_| rng.gen::<usize>() % n).collect();
72 keys.shuffle(&mut rng);
77 let t = map.get(&keys[i]);
85 macro_rules! map_find_seq_bench {
86 ($name: ident, $n: expr, $map: ident) => {
88 pub fn $name(b: &mut Bencher) {
89 let mut map = $map::new();
108 map_insert_rand_bench! {insert_rand_100, 100, BTreeMap}
109 map_insert_rand_bench! {insert_rand_10_000, 10_000, BTreeMap}
111 map_insert_seq_bench! {insert_seq_100, 100, BTreeMap}
112 map_insert_seq_bench! {insert_seq_10_000, 10_000, BTreeMap}
114 map_find_rand_bench! {find_rand_100, 100, BTreeMap}
115 map_find_rand_bench! {find_rand_10_000, 10_000, BTreeMap}
117 map_find_seq_bench! {find_seq_100, 100, BTreeMap}
118 map_find_seq_bench! {find_seq_10_000, 10_000, BTreeMap}
120 fn bench_iteration(b: &mut Bencher, size: i32) {
121 let mut map = BTreeMap::<i32, i32>::new();
122 let mut rng = thread_rng();
125 map.insert(rng.gen(), rng.gen());
136 pub fn iteration_20(b: &mut Bencher) {
137 bench_iteration(b, 20);
141 pub fn iteration_1000(b: &mut Bencher) {
142 bench_iteration(b, 1000);
146 pub fn iteration_100000(b: &mut Bencher) {
147 bench_iteration(b, 100000);
150 fn bench_iteration_mut(b: &mut Bencher, size: i32) {
151 let mut map = BTreeMap::<i32, i32>::new();
152 let mut rng = thread_rng();
155 map.insert(rng.gen(), rng.gen());
159 for kv in map.iter_mut() {
166 pub fn iteration_mut_20(b: &mut Bencher) {
167 bench_iteration_mut(b, 20);
171 pub fn iteration_mut_1000(b: &mut Bencher) {
172 bench_iteration_mut(b, 1000);
176 pub fn iteration_mut_100000(b: &mut Bencher) {
177 bench_iteration_mut(b, 100000);
180 fn bench_first_and_last(b: &mut Bencher, size: i32) {
181 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
184 black_box(map.first_key_value());
185 black_box(map.last_key_value());
191 pub fn first_and_last_0(b: &mut Bencher) {
192 bench_first_and_last(b, 0);
196 pub fn first_and_last_100(b: &mut Bencher) {
197 bench_first_and_last(b, 100);
201 pub fn first_and_last_10k(b: &mut Bencher) {
202 bench_first_and_last(b, 10_000);
205 const BENCH_RANGE_SIZE: i32 = 145;
206 const BENCH_RANGE_COUNT: i32 = BENCH_RANGE_SIZE * (BENCH_RANGE_SIZE - 1) / 2;
208 fn bench_range<F, R>(b: &mut Bencher, f: F)
210 F: Fn(i32, i32) -> R,
213 let map: BTreeMap<_, _> = (0..BENCH_RANGE_SIZE).map(|i| (i, i)).collect();
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)));
222 debug_assert_eq!(c, BENCH_RANGE_COUNT);
227 pub fn range_included_excluded(b: &mut Bencher) {
228 bench_range(b, |i, j| i..j);
232 pub fn range_included_included(b: &mut Bencher) {
233 bench_range(b, |i, j| i..=j);
237 pub fn range_included_unbounded(b: &mut Bencher) {
238 bench_range(b, |i, _| i..);
242 pub fn range_unbounded_unbounded(b: &mut Bencher) {
243 bench_range(b, |_, _| ..);
246 fn bench_iter(b: &mut Bencher, repeats: i32, size: i32) {
247 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
249 for _ in 0..repeats {
250 black_box(map.iter());
255 /// Contrast range_unbounded_unbounded with `iter()`.
257 pub fn range_unbounded_vs_iter(b: &mut Bencher) {
258 bench_iter(b, BENCH_RANGE_COUNT, BENCH_RANGE_SIZE);
262 pub fn iter_0(b: &mut Bencher) {
263 bench_iter(b, 1_000, 0);
267 pub fn iter_1(b: &mut Bencher) {
268 bench_iter(b, 1_000, 1);
272 pub fn iter_100(b: &mut Bencher) {
273 bench_iter(b, 1_000, 100);
277 pub fn iter_10k(b: &mut Bencher) {
278 bench_iter(b, 1_000, 10_000);
282 pub fn iter_1m(b: &mut Bencher) {
283 bench_iter(b, 1_000, 1_000_000);
286 const FAT: usize = 256;
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<_, _>>()
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<_, _>>()
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<_, _>>()
305 pub fn clone_slim_100(b: &mut Bencher) {
306 let src = slim_map(100);
307 b.iter(|| src.clone())
311 pub fn clone_slim_100_and_clear(b: &mut Bencher) {
312 let src = slim_map(100);
313 b.iter(|| src.clone().clear())
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())
323 pub fn clone_slim_100_and_drain_half(b: &mut Bencher) {
324 let src = slim_map(100);
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);
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())
339 pub fn clone_slim_100_and_pop_all(b: &mut Bencher) {
340 let src = slim_map(100);
342 let mut map = src.clone();
343 while map.pop_first().is_some() {}
349 pub fn clone_slim_100_and_remove_all(b: &mut Bencher) {
350 let src = slim_map(100);
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());
362 pub fn clone_slim_100_and_remove_half(b: &mut Bencher) {
363 let src = slim_map(100);
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());
370 assert_eq!(map.len(), 100 / 2);
376 pub fn clone_slim_10k(b: &mut Bencher) {
377 let src = slim_map(10_000);
378 b.iter(|| src.clone())
382 pub fn clone_slim_10k_and_clear(b: &mut Bencher) {
383 let src = slim_map(10_000);
384 b.iter(|| src.clone().clear())
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())
394 pub fn clone_slim_10k_and_drain_half(b: &mut Bencher) {
395 let src = slim_map(10_000);
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);
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())
410 pub fn clone_slim_10k_and_pop_all(b: &mut Bencher) {
411 let src = slim_map(10_000);
413 let mut map = src.clone();
414 while map.pop_first().is_some() {}
420 pub fn clone_slim_10k_and_remove_all(b: &mut Bencher) {
421 let src = slim_map(10_000);
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());
433 pub fn clone_slim_10k_and_remove_half(b: &mut Bencher) {
434 let src = slim_map(10_000);
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());
441 assert_eq!(map.len(), 10_000 / 2);
447 pub fn clone_fat_val_100(b: &mut Bencher) {
448 let src = fat_val_map(100);
449 b.iter(|| src.clone())
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())
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())
465 pub fn clone_fat_val_100_and_drain_half(b: &mut Bencher) {
466 let src = fat_val_map(100);
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);
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())
481 pub fn clone_fat_val_100_and_pop_all(b: &mut Bencher) {
482 let src = fat_val_map(100);
484 let mut map = src.clone();
485 while map.pop_first().is_some() {}
491 pub fn clone_fat_val_100_and_remove_all(b: &mut Bencher) {
492 let src = fat_val_map(100);
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());
504 pub fn clone_fat_val_100_and_remove_half(b: &mut Bencher) {
505 let src = fat_val_map(100);
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());
512 assert_eq!(map.len(), 100 / 2);
518 pub fn clone_fat_100(b: &mut Bencher) {
519 let src = fat_map(100);
520 b.iter(|| src.clone())
524 pub fn clone_fat_100_and_clear(b: &mut Bencher) {
525 let src = fat_map(100);
526 b.iter(|| src.clone().clear())
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())
536 pub fn clone_fat_100_and_drain_half(b: &mut Bencher) {
537 let src = fat_map(100);
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);
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())
552 pub fn clone_fat_100_and_pop_all(b: &mut Bencher) {
553 let src = fat_map(100);
555 let mut map = src.clone();
556 while map.pop_first().is_some() {}
562 pub fn clone_fat_100_and_remove_all(b: &mut Bencher) {
563 let src = fat_map(100);
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());
575 pub fn clone_fat_100_and_remove_half(b: &mut Bencher) {
576 let src = fat_map(100);
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());
583 assert_eq!(map.len(), 100 / 2);