]>
Commit | Line | Data |
---|---|---|
1b1a35ee XL |
1 | use std::collections::BinaryHeap; |
2 | ||
04454e1e | 3 | use rand::seq::SliceRandom; |
1b1a35ee XL |
4 | use test::{black_box, Bencher}; |
5 | ||
6 | #[bench] | |
7 | fn bench_find_smallest_1000(b: &mut Bencher) { | |
04454e1e | 8 | let mut rng = crate::bench_rng(); |
1b1a35ee XL |
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 | |
94222f64 | 39 | // the loop might not run. |
1b1a35ee XL |
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) { | |
04454e1e | 50 | let mut rng = crate::bench_rng(); |
1b1a35ee XL |
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); | |
04454e1e | 67 | let mut rng = crate::bench_rng(); |
1b1a35ee XL |
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 | } |