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

[Vamsi Krishna Reddy Satti]

Thank you for the links. I realize now that the code was intentional approach to minimize comparisons made. I was not aware of this idea earlier.

Also, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69565 might be explained by the fact that the benchmark was done over integers.
libc++ implements the mentioned heap operations using Floyd's method (the one I was suggesting here). Since comparisons are cheap
for integers, the benchmarks favoured libc++ implementation.

It probably seems via. bug 69565 that my original suggestion makes sense for data types where comparison is cheap like the primitive types.
Does it make sense to use a normal siftUp / heapifyUp operation instead of __adjust_heap for primitive types separately?
________________________________
From: Marc Glisse <marc.glisse@inria.fr>
Sent: 25 July 2020 01:19 PM
To: Vamsi Krishna Reddy Satti <vamsi3@outlook.com>
Cc: libstdc++@gcc.gnu.org <libstdc++@gcc.gnu.org>
Subject: Re: Potential efficiency improvement to std::make_heap and std::pop_heap functions.

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