Auto merge of #75974 - SkiFire13:peekmut-opt-sift, r=LukasKalbertodt

Avoid useless sift_down when std::collections::binary_heap::PeekMut is never mutably dereferenced

If `deref_mut` is never called then it's not possible for the element to be mutated without internal mutability, meaning there's no need to call `sift_down`.

This could be a little improvement in cases where you want to mutate the biggest element of the heap only if it satisfies a certain predicate that needs only read access to the element.

3 files changed, 96 insertions, 2 deletions

diff --git a/library/alloc/benches/binary_heap.rs b/library/alloc/benches/binary_heap.rs
new file mode 100644
index 00000000000..5b6538ea6c6
--- /dev/null
+++ b/library/alloc/benches/binary_heap.rs
@@ -0,0 +1,91 @@
+use std::collections::BinaryHeap;
+
+use rand::{seq::SliceRandom, thread_rng};
+use test::{black_box, Bencher};
+
+#[bench]
+fn bench_find_smallest_1000(b: &mut Bencher) {
+    let mut rng = thread_rng();
+    let mut vec: Vec<u32> = (0..100_000).collect();
+    vec.shuffle(&mut rng);
+
+    b.iter(|| {
+        let mut iter = vec.iter().copied();
+        let mut heap: BinaryHeap<_> = iter.by_ref().take(1000).collect();
+
+        for x in iter {
+            let mut max = heap.peek_mut().unwrap();
+            // This comparison should be true only 1% of the time.
+            // Unnecessary `sift_down`s will degrade performance
+            if x < *max {
+                *max = x;
+            }
+        }
+
+        heap
+    })
+}
+
+#[bench]
+fn bench_peek_mut_deref_mut(b: &mut Bencher) {
+    let mut bheap = BinaryHeap::from(vec![42]);
+    let vec: Vec<u32> = (0..1_000_000).collect();
+
+    b.iter(|| {
+        let vec = black_box(&vec);
+        let mut peek_mut = bheap.peek_mut().unwrap();
+        // The compiler shouldn't be able to optimize away the `sift_down`
+        // assignment in `PeekMut`'s `DerefMut` implementation since
+        // the loop may not run.
+        for &i in vec.iter() {
+            *peek_mut = i;
+        }
+        // Remove the already minimal overhead of the sift_down
+        std::mem::forget(peek_mut);
+    })
+}
+
+#[bench]
+fn bench_from_vec(b: &mut Bencher) {
+    let mut rng = thread_rng();
+    let mut vec: Vec<u32> = (0..100_000).collect();
+    vec.shuffle(&mut rng);
+
+    b.iter(|| BinaryHeap::from(vec.clone()))
+}
+
+#[bench]
+fn bench_into_sorted_vec(b: &mut Bencher) {
+    let bheap: BinaryHeap<i32> = (0..10_000).collect();
+
+    b.iter(|| bheap.clone().into_sorted_vec())
+}
+
+#[bench]
+fn bench_push(b: &mut Bencher) {
+    let mut bheap = BinaryHeap::with_capacity(50_000);
+    let mut rng = thread_rng();
+    let mut vec: Vec<u32> = (0..50_000).collect();
+    vec.shuffle(&mut rng);
+
+    b.iter(|| {
+        for &i in vec.iter() {
+            bheap.push(i);
+        }
+        black_box(&mut bheap);
+        bheap.clear();
+    })
+}
+
+#[bench]
+fn bench_pop(b: &mut Bencher) {
+    let mut bheap = BinaryHeap::with_capacity(10_000);
+
+    b.iter(|| {
+        bheap.extend((0..10_000).rev());
+        black_box(&mut bheap);
+        while let Some(elem) = bheap.pop() {
+            black_box(elem);
+        }
+    })
+}
diff --git a/library/alloc/benches/lib.rs b/library/alloc/benches/lib.rs
index 608eafc88d2..32edb86d101 100644
--- a/library/alloc/benches/lib.rs
+++ b/library/alloc/benches/lib.rs
@@ -8,6 +8,7 @@
 
 extern crate test;
 
+mod binary_heap;
 mod btree;
 mod linked_list;
 mod slice;
diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs
index 621c4ff6378..ea75fa21965 100644
--- a/library/alloc/src/collections/binary_heap.rs
+++ b/library/alloc/src/collections/binary_heap.rs
@@ -291,6 +291,7 @@ impl<T: Ord> Deref for PeekMut<'_, T> {
 impl<T: Ord> DerefMut for PeekMut<'_, T> {
     fn deref_mut(&mut self) -> &mut T {
         debug_assert!(!self.heap.is_empty());
+        self.sift = true;
         // SAFE: PeekMut is only instantiated for non-empty heaps
         unsafe { self.heap.data.get_unchecked_mut(0) }
     }
@@ -396,10 +397,11 @@ impl<T: Ord> BinaryHeap<T> {
     ///
     /// # Time complexity
     ///
-    /// Cost is *O*(1) in the worst case.
+    /// If the item is modified then the worst case time complexity is *O*(log(*n*)),
+    /// otherwise it's *O*(1).
     #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")]
     pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> {
-        if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: true }) }
+        if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) }
     }
 
     /// Removes the greatest item from the binary heap and returns it, or `None` if it