Improve sift_down performance in BinaryHeap

Because child > 0, the two statements are equivalent, but using
saturating_sub and <= yields in faster code. This is most notable in the
binary_heap::bench_into_sorted_vec benchmark, which shows a speedup of
1.26x, which uses sift_down_range internally. The speedup of pop (that
uses sift_down_to_bottom internally) is much less significant as the
sifting method is not called in a loop.

1 files changed, 2 insertions, 2 deletions

diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs
index 33bd98d467c..e025da74da4 100644
--- a/library/alloc/src/collections/binary_heap.rs
+++ b/library/alloc/src/collections/binary_heap.rs
@@ -565,7 +565,7 @@ impl<T: Ord> BinaryHeap<T> {
         let mut child = 2 * hole.pos() + 1;
 
         // Loop invariant: child == 2 * hole.pos() + 1.
-        while child < end - 1 {
+        while child <= end.saturating_sub(2) {
             // compare with the greater of the two children
             // SAFETY: child < end - 1 < self.len() and
             //  child + 1 < end <= self.len(), so they're valid indexes.
@@ -624,7 +624,7 @@ impl<T: Ord> BinaryHeap<T> {
         let mut child = 2 * hole.pos() + 1;
 
         // Loop invariant: child == 2 * hole.pos() + 1.
-        while child < end - 1 {
+        while child <= end.saturating_sub(2) {
             // SAFETY: child < end - 1 < self.len() and
             //  child + 1 < end <= self.len(), so they're valid indexes.
             //  child == 2 * hole.pos() + 1 != hole.pos() and