library/alloc/benches/binary_heap.rs

   1 use std::collections::BinaryHeap;
   2
   3 use rand::seq::SliceRandom;
   4 use test::{black_box, Bencher};
   5
   6 #[bench]
   7 fn bench_find_smallest_1000(b: &mut Bencher) {
   8     let mut rng = crate::bench_rng();
   9     let mut vec: Vec<u32> = (0..100_000).collect();
  10     vec.shuffle(&mut rng);
  11
  12     b.iter(|| {
  13         let mut iter = vec.iter().copied();
  14         let mut heap: BinaryHeap<_> = iter.by_ref().take(1000).collect();
  15
  16         for x in iter {
  17             let mut max = heap.peek_mut().unwrap();
  18             // This comparison should be true only 1% of the time.
  19             // Unnecessary `sift_down`s will degrade performance
  20             if x < *max {
  21                 *max = x;
  22             }
  23         }
  24
  25         heap
  26     })
  27 }
  28
  29 #[bench]
  30 fn bench_peek_mut_deref_mut(b: &mut Bencher) {
  31     let mut bheap = BinaryHeap::from(vec![42]);
  32     let vec: Vec<u32> = (0..1_000_000).collect();
  33
  34     b.iter(|| {
  35         let vec = black_box(&vec);
  36         let mut peek_mut = bheap.peek_mut().unwrap();
  37         // The compiler shouldn't be able to optimize away the `sift_down`
  38         // assignment in `PeekMut`'s `DerefMut` implementation since
  39         // the loop might not run.
  40         for &i in vec.iter() {
  41             *peek_mut = i;
  42         }
  43         // Remove the already minimal overhead of the sift_down
  44         std::mem::forget(peek_mut);
  45     })
  46 }
  47
  48 #[bench]
  49 fn bench_from_vec(b: &mut Bencher) {
  50     let mut rng = crate::bench_rng();
  51     let mut vec: Vec<u32> = (0..100_000).collect();
  52     vec.shuffle(&mut rng);
  53
  54     b.iter(|| BinaryHeap::from(vec.clone()))
  55 }
  56
  57 #[bench]
  58 fn bench_into_sorted_vec(b: &mut Bencher) {
  59     let bheap: BinaryHeap<i32> = (0..10_000).collect();
  60
  61     b.iter(|| bheap.clone().into_sorted_vec())
  62 }
  63
  64 #[bench]
  65 fn bench_push(b: &mut Bencher) {
  66     let mut bheap = BinaryHeap::with_capacity(50_000);
  67     let mut rng = crate::bench_rng();
  68     let mut vec: Vec<u32> = (0..50_000).collect();
  69     vec.shuffle(&mut rng);
  70
  71     b.iter(|| {
  72         for &i in vec.iter() {
  73             bheap.push(i);
  74         }
  75         black_box(&mut bheap);
  76         bheap.clear();
  77     })
  78 }
  79
  80 #[bench]
  81 fn bench_pop(b: &mut Bencher) {
  82     let mut bheap = BinaryHeap::with_capacity(10_000);
  83
  84     b.iter(|| {
  85         bheap.extend((0..10_000).rev());
  86         black_box(&mut bheap);
  87         while let Some(elem) = bheap.pop() {
  88             black_box(elem);
  89         }
  90     })
  91 }