[libc++] Floyd's improvement to pop_heap

[• Quuxplusone]

Summary

[libc++] "Bottom-up heapsort" improvement to sort_heap.

https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort
In `pop_heap` specifically, the item we insert at the top and
sift downward is guaranteed to be leaf-sized, so we expect it
to go pretty far down. Sift it down as if it were INT_MIN, and
then bubble it back up if needed.
Also known as "heapsort with bounce."

Numbers are here: https://godbolt.org/z/cvfnYW6fe

Fixes #10008.

Differential Revision: https://reviews.llvm.org/D118003

Fixes https://github.com/llvm/llvm-project/issues/10008

As the issue description says:

[__sift_down] is normally used to put in the correct position an element that was previously a leaf of a heap
(as in the pop_heap implementation). [When] that element was a leaf, it is likely that it will move down when
placed in the root.

An optimization is to move down the empty space at the root by swapping it with the largest child.
When the empty space becomes a leaf, the last element is moved to its place and moved up if necessary.

The advantage is that only one comparison per step is needed to move the empty space down.

A demo is here: https://godbolt.org/z/M8do8sWhT
For the same 100,000 random elements made into a heap using make_heap:
libstdc++ sort_heap takes 1,934,727 moves; 1,534,715 comparisons.
libc++ trunk sort_heap takes 1,900,731 moves; 2,831,757 comparisons.
libc++ after this patch takes 1,764,997 moves; 1,534,701 comparisons.
(Note that this really is apples to apples: hashing proves that libstdc++'s make_heap produces the exact same 100,000-element sequence as libc++'s make_heap.)

[philnik]

LGTM % nits, but I'm not exactly an expert here.

libcxx/include/__algorithm/pop_heap.h

32

34–47

I'd rather see an early return, but I may be alone.

libcxx/include/__algorithm/sift_down.h

78

Is _LIBCPP_HIDE_FROM_ABI purposefully not here?

82

104–106

[Mordante]

I'm not too familiar with this code, but I see no real issues.

libcxx/include/__algorithm/sift_down.h

79

Since you use a know algorithm, please provide a link to the algorithm. Since the OP didn't know which paper I'm happy with just using https://en.wikipedia.org/wiki/Heapsort#Floyd's_heap_construction.

79

Can you add a benchmark for the new algorithm?

[• Quuxplusone]

libcxx/include/__algorithm/sift_down.h

78

Nope, accidental... but maybe it should be on purpose? We don't put either inline _LIBCPP_HIDE_FROM_ABI or inline _LIBCPP_INLINE_VISIBILITY on ordinary __sift_down either; nor on __make_heap; nor on __nth_element... It seems like (at least in this old code) the visibility macro is intentionally affiliated with the inline keyword, and the inline keyword goes only on short functions. I don't know whether we should be following that rule, or fixing it. My default of course is to leave it as-is (i.e. not add _LIBCPP_HIDE_FROM_ABI here).

79

https://en.wikipedia.org/wiki/Heapsort#Floyd's_heap_construction is describing the make_heap side of things (which we already implement): make_heap can be done with push_heap in a loop but that's slow. This PR is the sort_heap side of things: sort_heap is still done with pop_heap in a loop but pop_heap itself can be faster.

Ah, but this is the very next subsection: https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort I'll add a link to the commit message and also change the summary to mention "bottom-up heapsort / heapsort with bounce" since those are more googleable than "Floyd's improvement" :)

I'll investigate benchmarking. See the current commit message for my informal benchmark https://godbolt.org/z/M8do8sWhT ; it probably won't take much to turn it into a libcxx/benchmark/ test... although at the same time I don't know that anyone ever actually notices regressions in those benchmarks.

82

FWIW this is not libc++'s historical style, but since Clang C++03 supports using= now, I'm cool with it if everyone else is. Will fix.

[• Quuxplusone]

libcxx/include/__algorithm/sift_down.h

79

Turns out we already have libcxx/benchmarks/ code for this!
https://pastebin.com/iewiGLcN (before-bench.txt)
https://pastebin.com/MLP8f7y4 (after-bench.txt)

My hot takes are that:

• it's really noisy (he says defensively); note the changes (mostly badwards) in MakeHeap, whose actual code is unaffected by this patch
• this might be a pessimization for short arrays of trivial types, e.g. BM_MakeThenSortHeap_uint64_Random_262144 goes from 101ns to 104ns
• this is, as expected, a major win for very long arrays of non-trivial types, e.g. BM_MakeThenSortHeap_string_Random_262144 goes from 832ns to 669ns

[• Quuxplusone]

s/typedef/using/
s/_VSTD/std/
I claim this is ready to land. @ldionne?

[ldionne]

Can you add a release note? This is a nice improvement. I'd also like us to add a libc++ specific test that counts the number of comparisons. It can be pretty basic, but I'd like to regression-lock this improvement.

I tried poking holes into the implementation by grabbing the patch, making small changes (e.g. introducing off-by-ones) and literally every single line I touched would make the tests fail. In other words, I am fairly confident this is correct, not because I trust myself to validate the algorithm itself, but because I think our test coverage in that area is pretty solid.

LGTM with a regression test that checks for the number of comparisons and my __assert comment.

libcxx/include/__algorithm/sift_down.h

14

You want to include <__assert> here instead.

[• Quuxplusone]

Add complexity.pass.cpp for sort_heap and also for make_heap, since I've got those numbers already.
I thought of trying to make the assertions "fuzzy," but couldn't see a mathematically justifiable way of doing that, and besides, these numbers should never change unless they're deliberately being changed by someone who cares about these numbers! (As in this PR.)

Will land the tests first, with the old numbers, so that the main commit can braggingly update the numbers in place:

diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
index 28f82d61da33..8c10f81d767e 100644
--- a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
@@ -65,8 +65,8 @@ int main(int, char**)
   stats = {};
   std::sort_heap(v.begin(), v.end());
   assert(stats.copied == 0);
-  assert(stats.moved == 1'900'731);
-  assert(stats.compared == 2'831'757);
+  assert(stats.moved == 1'764'997);
+  assert(stats.compared == 1'534'701);
 
   assert(std::is_sorted(v.begin(), v.end()));

Re-poking CI, though, to make sure all platforms agree about these numbers. (They're deterministic AFAIK, but I could be wrong.)

[• Quuxplusone]

Oops, also add a release note. @ldionne LGTY?

[• Quuxplusone]

Argh. Unsupport the new complexity test on C++11 because it lacks 1'000'000 literals, and I think the 's are nice enough that I don't feel like losing them. It seems unimaginable that C++03/11 would have different complexity characteristics from C++14/17/20/2b (and if they did, really, I'm not sure we'd care).

[• Quuxplusone]

For now, skip asserting the number of comparisons in debug mode (attn @ldionne, this is relevant to your interests).
I think the GCC11 failure in https://buildkite.com/llvm-project/libcxx-ci/builds/9373 was a fluke, but let's see if it happens again.

[EricWF]

libcxx/include/__algorithm/sift_down.h

83

LIBCPP_ASSERT is not meant to guard against internal library logic errors.

101

You move __child_i here, but you reference it again at the start of the next loop iteration

[• Quuxplusone]

libcxx/include/__algorithm/sift_down.h

83

You (or anyone) got any better suggestions? Should this just be a comment // __len >= 2 at this point?

101

Yikes! Thanks, fixed in 2b0ec7ca44ea227665f25b7dc3a3c097f16673cb — but tomorrow I'll think about ways to test for this. I wonder if the test iterators (like forward_iterator<T>) should be augmented to globally detect use-after-move.

[EricWF]

libcxx/include/__algorithm/sift_down.h

83

Write a test that would fail were this to be called (failing only under ASAN or MSAN is fine).

[• Quuxplusone]

libcxx/include/__algorithm/sift_down.h

83

Write a test that would fail were this to be called

@EricWF: I don't understand that comment. My intention is that __floyd_sift_down is never called with __len < 2. If it were ever called with __len < 2, bad stuff would happen. In other words, what we really mean here is something like [[pre: __len >= 2]] or __builtin_assume(len >= 2), but libc++ traditionally hasn't used those, so I just reached for _LIBCPP_ASSERT as the handiest documentation tool. As I suggested above, I could just replace it with a comment // Precondition: __len >= 2, but I'm soliciting better suggestions.

libcxx/docs/ReleaseNotes.rst

 
 What's New in Libc++ 15.0.0?
 ============================
 
 New Features
 ------------
 
  - Implemented P0627R6 (Function to mark unreachable code)
+
  - Implemented P1165R1 (Make stateful allocator propagation more consistent for ``operator+(basic_string)``)
 
+ - `pop_heap` now uses an algorithm known as "bottom-up heapsort" or
+   "heapsort with bounce" to reduce the number of comparisons, and rearranges
+   elements using move-assignment instead of `swap`.
+
 API Changes
 -----------
 
 - The ``_LIBCPP_ABI_UNSTABLE`` macro has been removed in favour of setting
   ``_LIBCPP_ABI_VERSION=2``. This should not have any impact on users because
   they were not supposed to set ``_LIBCPP_ABI_UNSTABLE`` manually, however we
   still feel that it is worth mentioning in the release notes in case some users
   had been doing it.

libcxx/include/__algorithm/pop_heap.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_POP_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
+    using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+
     if (__len > 1)
     {
-        swap(*__first, *--__last);
-        _VSTD::__sift_down<_Compare>(__first, __comp, __len - 1, __first);
+        value_type __top = std::move(*__first);  // create a hole at __first
+        _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len);
+        --__last;
+        if (__hole == __last) {
+            *__hole = std::move(__top);
+        } else {
+            *__hole = std::move(*__last);
+            ++__hole;
+            *__last = std::move(__top);
+            std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first);
+        }
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;

libcxx/include/__algorithm/sift_down.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
+#include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
do
             ++__child;
         }
 
         // check if we are in heap-order
     } while (!__comp(*__child_i, __top));
     *__start = _VSTD::move(__top);
 }
 
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
+__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
+                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
+{
+    using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+    _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2");
+
+    _RandomAccessIterator __hole = __first;
+    _RandomAccessIterator __child_i = __first;
+    difference_type __child = 0;
+
+    while (true) {
+        __child_i += difference_type(__child + 1);
+        __child = 2 * __child + 1;
+
+        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+            // right-child exists and is greater than left-child
+            ++__child_i;
+            ++__child;
+        }
+
+        // swap __hole with its largest child
+        *__hole = std::move(*__child_i);
+        __hole = std::move(__child_i);
+
+        // if __hole is now a leaf, we're done
+        if (__child > (__len - 2) / 2)
+            return __hole;
+    }
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H

libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

int main(int, char**)
   // The exact stats of our current implementation are recorded here.
   // If something changes to make them go a bit up or down, that's probably fine,
   // and we can just update this test.
   // But if they suddenly leap upward, that's a bad thing.
 
   stats = {};
   std::sort_heap(v.begin(), v.end());
   assert(stats.copied == 0);
-  assert(stats.moved == 1'900'731);
+  assert(stats.moved == 1'764'997);
 #ifndef _LIBCPP_DEBUG
-  assert(stats.compared == 2'831'757);
+  assert(stats.compared == 1'534'701);
 #endif
 
   assert(std::is_sorted(v.begin(), v.end()));
 
   return 0;
 }