diff options
author | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2021-12-29 22:11:46 +0300 |
---|---|---|
committer | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2022-03-08 21:48:21 +0300 |
commit | 79d08e398c17e83b118b837ab0b52107fd294c3e (patch) | |
tree | 5df7c0a35dd5a6c1baca3f9aac90136c3b30f5eb /libcxx | |
parent | e3d3755c4745aee33b55ad4e5ab72c46e4133a8e (diff) |
[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
Diffstat (limited to 'libcxx')
-rw-r--r-- | libcxx/docs/ReleaseNotes.rst | 5 | ||||
-rw-r--r-- | libcxx/include/__algorithm/pop_heap.h | 18 | ||||
-rw-r--r-- | libcxx/include/__algorithm/sift_down.h | 33 | ||||
-rw-r--r-- | libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp | 4 |
4 files changed, 55 insertions, 5 deletions
diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst index ea7235e4abf8..d78549edb10c 100644 --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -39,8 +39,13 @@ 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 ----------- diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h index 2a69f6ee47f0..2932a5e31dbc 100644 --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -11,10 +11,11 @@ #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 @@ -28,10 +29,21 @@ 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); + } } } diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h index b636da78b0cc..6a6646d0442d 100644 --- a/libcxx/include/__algorithm/sift_down.h +++ b/libcxx/include/__algorithm/sift_down.h @@ -9,6 +9,7 @@ #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> @@ -73,6 +74,38 @@ __sift_down(_RandomAccessIterator __first, _Compare __comp, *__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 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 160798382304..dbf808a0b850 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 @@ -64,9 +64,9 @@ int main(int, char**) 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())); |