Potential efficiency improvement to std::make_heap and std::pop_heap functions.

[Marc Glisse]

On Sat, 25 Jul 2020, Vamsi Krishna Reddy Satti via Libstdc++ wrote:

> I was having a look over the implementation of std::make_heap and std::pop_heap in "include/bits/stl_heap.h" on the latest source. I suspect that the implementation is inefficient and possibly does some unnecessary operations.
>
> Most of my concern comes from the __adjust_heap function which is used in common by above two functions. From my understanding, __adjust_heap just needs to perform the textbook shift-down or heapify-down operation for correctness of std::make_heap and std::pop_heap functions.
>
>    template<typename _RandomAccessIterator, typename _Distance,
>                        typename _Tp, typename _Compare>
>        _GLIBCXX20_CONSTEXPR
>        void
>        __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
>            _Distance __len, _Tp __value, _Compare __comp)
>        {
>            const _Distance __topIndex = __holeIndex;
>            _Distance __secondChild = __holeIndex;
>            while (__secondChild < (__len - 1) / 2)
>            {
>                __secondChild = 2 * (__secondChild + 1);
>                if (__comp(__first + __secondChild,
>                        __first + (__secondChild - 1)))
>                    __secondChild--;
>                *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
>                __holeIndex = __secondChild;
>            }
>            if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
>            {
>                __secondChild = 2 * (__secondChild + 1);
>                *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
>                                                                                                        + (__secondChild - 1)));
>                __holeIndex = __secondChild - 1;
>            }
>            __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
>                __cmp(_GLIBCXX_MOVE(__comp));
>            std::__push_heap(__first, __holeIndex, __topIndex,
>                     _GLIBCXX_MOVE(__value), __cmp);
>        }
>
>
> But the __adjust_heap function right now takes the __holeIndex all the way down to a leaf unconditionally. And then calls the __push_heap function which performs the textbook shift-up or heapify-up operation.
>
> I believe that instead, we should add checks to compare (using __comp) the value at index __secondChild and __value to determine if we should stop proceeding further. In that way, a call to push_heap at the end is also not required and instead we just assign __value to the iterator at index __secondChild in the container.

I think the version in libstdc++ is one of the variants described in 
https://en.wikipedia.org/wiki/Heapsort

What you suggest makes going down slower (more comparisons at each step), 
so if in most cases the walk goes almost to the end, the gain is not 
obvious.

It is quite possible (even likely) that the implementation can be 
improved. However, we would need to see benchmarks comparing the new 
implementation to the old one for various scenarios (small that fits in 
cache vs very large requiring a lot of memory accesses, cheap/expensive 
comparisons and moves, make_heap or push_heap, random order or already 
(almost) sorted, etc) for a significant design change (we may not need all 
the cases I mention, but at least some benchmarks).

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69565
could help a little bit, although it is starting to be a bit old.

-- 
Marc Glisse