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

[Vamsi Krishna Reddy Satti]

Hello!

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.

P.S. Sorry if this is not the right place to ask this question. Please let me know if I'm mistaken, since I wanted to clarify before filing the improvement as a bug.