1 use std::collections::BinaryHeap;
3 use rand::{seq::SliceRandom, thread_rng};
4 use test::{black_box, Bencher};
7 fn bench_find_smallest_1000(b: &mut Bencher) {
8 let mut rng = thread_rng();
9 let mut vec: Vec<u32> = (0..100_000).collect();
10 vec.shuffle(&mut rng);
13 let mut iter = vec.iter().copied();
14 let mut heap: BinaryHeap<_> = iter.by_ref().take(1000).collect();
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
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();
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() {
43 // Remove the already minimal overhead of the sift_down
44 std::mem::forget(peek_mut);
49 fn bench_from_vec(b: &mut Bencher) {
50 let mut rng = thread_rng();
51 let mut vec: Vec<u32> = (0..100_000).collect();
52 vec.shuffle(&mut rng);
54 b.iter(|| BinaryHeap::from(vec.clone()))
58 fn bench_into_sorted_vec(b: &mut Bencher) {
59 let bheap: BinaryHeap<i32> = (0..10_000).collect();
61 b.iter(|| bheap.clone().into_sorted_vec())
65 fn bench_push(b: &mut Bencher) {
66 let mut bheap = BinaryHeap::with_capacity(50_000);
67 let mut rng = thread_rng();
68 let mut vec: Vec<u32> = (0..50_000).collect();
69 vec.shuffle(&mut rng);
72 for &i in vec.iter() {
75 black_box(&mut bheap);
81 fn bench_pop(b: &mut Bencher) {
82 let mut bheap = BinaryHeap::with_capacity(10_000);
85 bheap.extend((0..10_000).rev());
86 black_box(&mut bheap);
87 while let Some(elem) = bheap.pop() {