On Mon, 18 May 2026 at 05:34, Nathan Myers <[email protected]> wrote:
>
> [As a WIP, this patch is mostly limited to std::sort and what
> it uses, also touching heap primitives. Covering the rest of
> stl_algo.h will go quickly if we decide we want that.]
My assumption was that we'd just deal with the low-hanging fruit and
add _GLIBCXX_MOVE everywhere that the predicate was just passed to
another function and not used again.
Refactoring the sort algos seems like starting with the fruit higher
up the tree, and my general rule is we don't touch the sort algos
without extensive profiling covering a variety of element types and
functors.
>
> In GCC 16, algorithms like std::sort pass predicates exclusively
> by copying. This patch replaces all such copies with move
> construction and move assignment, passing function objects into
> helper functions that then return them so they may be passed
> along to the next operation.
>
> The number of moves performed approximates twice the number of
> copies in GCC 16, corresponding to predicates moved into and
> returned from helper functions, and half the number of calls
> to the predicates. It is possible that minor reorganizing can
> reduce the number of moves substantially.
>
> This probably slows down C++98 sorting, but uglifying with a
> pair of macros should be able to mitigate that, if we care.
>
> libstdc++-v3/Changelog:
> PR libstdc++/111963
> * include/bits/stl_algo.h: [Many functions touched.]
> * include/bits/stl_heap.h: likewise.
> ---
> libstdc++-v3/include/bits/stl_algo.h | 168 ++++++++++++++++-----------
> libstdc++-v3/include/bits/stl_heap.h | 35 +++---
> 2 files changed, 120 insertions(+), 83 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> index adf9b9e0f28..bee340d08be 100644
> --- a/libstdc++-v3/include/bits/stl_algo.h
> +++ b/libstdc++-v3/include/bits/stl_algo.h
> @@ -84,10 +84,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
> template<typename _Iterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> - __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b,
> - _Iterator __c, _Compare __comp)
> + pair<_Compare, _Iterator>
> + __move_median_to_first(pair<_Compare, _Iterator> __cmp_result,
> + _Iterator __a, _Iterator __b, _Iterator __c)
> {
> + _Compare& __comp = __cmp_result.first;
> + _Iterator __result = __cmp_result.second;
> if (__comp(*__a, *__b))
> {
> if (__comp(*__b, *__c))
> @@ -103,6 +105,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> std::iter_swap(__result, __c);
> else
> std::iter_swap(__result, __b);
> + return __cmp_result;
> }
>
> /// Provided for stable_partition to use.
> @@ -1585,15 +1588,17 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> /// This is a helper function for the sort routines.
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __heap_select(_RandomAccessIterator __first,
> _RandomAccessIterator __middle,
> _RandomAccessIterator __last, _Compare __comp)
> {
> - std::__make_heap(__first, __middle, __comp);
> + __comp = std::__make_heap(__first, __middle, _GLIBCXX_MOVE(__comp));
> for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
> if (__comp(*__i, *__first))
> - std::__pop_heap(__first, __middle, __i, __comp);
> + __comp = std::__pop_heap(
> + __first, __middle, __i, _GLIBCXX_MOVE(__comp));
> + return __comp;
> }
>
> // partial_sort
> @@ -1622,17 +1627,20 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> ++__first;
> }
>
> - std::__make_heap(__result_first, __result_real_last, __comp);
> + __comp = std::__make_heap(
> + __result_first, __result_real_last, _GLIBCXX_MOVE(__comp));
> while (__first != __last)
> {
> if (__comp(*__first, *__result_first))
> - std::__adjust_heap(__result_first, _DistanceType(0),
> + __comp = std::__adjust_heap(__result_first, _DistanceType(0),
> _DistanceType(__result_real_last
> - __result_first),
> - _InputValueType(*__first), __comp);
> + _InputValueType(*__first),
> + _GLIBCXX_MOVE(__comp));
> ++__first;
> }
> - std::__sort_heap(__result_first, __result_real_last, __comp);
> + std::__sort_heap(__result_first, __result_real_last,
> + _GLIBCXX_MOVE(__comp));
> return __result_real_last;
> }
>
> @@ -1746,7 +1754,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> /// This is a helper function for the sort routine.
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __unguarded_linear_insert(_RandomAccessIterator __last,
> _Compare __comp)
> {
> @@ -1761,17 +1769,18 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> --__next;
> }
> *__last = _GLIBCXX_MOVE(__val);
> + return __comp;
> }
>
> /// This is a helper function for the sort routine.
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __insertion_sort(_RandomAccessIterator __first,
> _RandomAccessIterator __last, _Compare __comp)
> {
> if (__first == __last)
> - return;
> + return __comp;
>
> typedef iterator_traits<_RandomAccessIterator> _IterTraits;
> typedef typename _IterTraits::difference_type _Dist;
> @@ -1785,19 +1794,21 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> *__first = _GLIBCXX_MOVE(__val);
> }
> else
> - std::__unguarded_linear_insert(__i, __comp);
> + __comp = std::__unguarded_linear_insert(__i,
> _GLIBCXX_MOVE(__comp));
> }
> + return __comp;
> }
>
> /// This is a helper function for the sort routine.
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - inline void
> + inline _Compare
> __unguarded_insertion_sort(_RandomAccessIterator __first,
> _RandomAccessIterator __last, _Compare __comp)
> {
> for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
> - std::__unguarded_linear_insert(__i, __comp);
> + __comp = std::__unguarded_linear_insert(__i, _GLIBCXX_MOVE(__comp));
> + return __comp;
> }
>
> /**
> @@ -1818,86 +1829,99 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
>
> if (__last - __first > __threshold)
> {
> - std::__insertion_sort(__first, __first + __threshold, __comp);
> - std::__unguarded_insertion_sort(__first + __threshold, __last,
> - __comp);
> + __comp = std::__insertion_sort(
> + __first, __first + __threshold, _GLIBCXX_MOVE(__comp));
> + std::__unguarded_insertion_sort(
> + __first + __threshold, __last, _GLIBCXX_MOVE(__comp));
> }
> else
> - std::__insertion_sort(__first, __last, __comp);
> + std::__insertion_sort(__first, __last, _GLIBCXX_MOVE(__comp));
> }
>
> /// This is a helper function...
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - _RandomAccessIterator
> - __unguarded_partition(_RandomAccessIterator __first,
> - _RandomAccessIterator __last,
> - _RandomAccessIterator __pivot, _Compare __comp)
> + pair<_Compare, _RandomAccessIterator>
> + __unguarded_partition(pair<_Compare, _RandomAccessIterator> __cmp_pivot,
> + _RandomAccessIterator __first,
> + _RandomAccessIterator __last)
> {
> while (true)
> {
> + _Compare& __comp = __cmp_pivot.first;
> + _RandomAccessIterator __pivot = __cmp_pivot.second;
> while (__comp(*__first, *__pivot))
> ++__first;
> --__last;
> while (__comp(*__pivot, *__last))
> --__last;
> if (!(__first < __last))
> - return __first;
> + break;
> std::iter_swap(__first, __last);
> ++__first;
> }
> + __cmp_pivot.second = __first;
> + return __cmp_pivot;
> }
>
> /// This is a helper function...
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - inline _RandomAccessIterator
> - __unguarded_partition_pivot(_RandomAccessIterator __first,
> - _RandomAccessIterator __last, _Compare __comp)
> + inline pair<_Compare, _RandomAccessIterator>
> + __unguarded_partition_pivot(
> + pair<_Compare, _RandomAccessIterator> __cmp_first,
> + _RandomAccessIterator __last)
> {
> - typedef iterator_traits<_RandomAccessIterator> _IterTraits;
> - typedef typename _IterTraits::difference_type _Dist;
> + typedef _RandomAccessIterator _Iter;
> + typedef typename iterator_traits<_Iter>::difference_type _Dist;
>
> - _RandomAccessIterator __mid = __first + _Dist((__last - __first) / 2);
> - _RandomAccessIterator __second = __first + _Dist(1);
> - std::__move_median_to_first(__first, __second, __mid, __last -
> _Dist(1),
> - __comp);
> - return std::__unguarded_partition(__second, __last, __first, __comp);
> + const _Iter __first = __cmp_first.second;
> + const _Iter __mid = __first + _Dist((__last - __first) / 2);
> + const _Iter __second = __first + _Dist(1);
> + __cmp_first = std::__move_median_to_first(
> + _GLIBCXX_MOVE(__cmp_first), __second, __mid, __last - _Dist(1));
> + return std::__unguarded_partition(
> + _GLIBCXX_MOVE(__cmp_first), __second, __last);
> }
>
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - inline void
> + inline _Compare
> __partial_sort(_RandomAccessIterator __first,
> _RandomAccessIterator __middle,
> _RandomAccessIterator __last,
> _Compare __comp)
> {
> - std::__heap_select(__first, __middle, __last, __comp);
> - std::__sort_heap(__first, __middle, __comp);
> + __comp = std::__heap_select(
> + __first, __middle, __last, _GLIBCXX_MOVE(__comp));
> + return std::__sort_heap(__first, __middle, _GLIBCXX_MOVE(__comp));
> }
>
> /// This is a helper function for the sort routine.
> template<typename _RandomAccessIterator, typename _Size, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> - __introsort_loop(_RandomAccessIterator __first,
> - _RandomAccessIterator __last,
> - _Size __depth_limit, _Compare __comp)
> + pair<_Compare, _RandomAccessIterator>
> + __introsort_loop(pair<_Compare, _RandomAccessIterator> __cmp_first,
> + _RandomAccessIterator __last, _Size __depth_limit)
> {
> + const _RandomAccessIterator __first = __cmp_first.second;
> while (__last - __first > int(_S_threshold))
> {
> if (__depth_limit == 0)
> {
> - std::__partial_sort(__first, __last, __last, __comp);
> - return;
> + __cmp_first.first = std::__partial_sort(
> + __first, __last, __last, _GLIBCXX_MOVE(__cmp_first.first));
> + break;
> }
> --__depth_limit;
> - _RandomAccessIterator __cut =
> - std::__unguarded_partition_pivot(__first, __last, __comp);
> - std::__introsort_loop(__cut, __last, __depth_limit, __comp);
> - __last = __cut;
> + __cmp_first = std::__unguarded_partition_pivot(
> + _GLIBCXX_MOVE(__cmp_first), __last),
> + __cmp_first = std::__introsort_loop(
> + _GLIBCXX_MOVE(__cmp_first), __last, __depth_limit);
> + __last = __cmp_first.second;
> + __cmp_first.second = __first;
> }
> + return __cmp_first;
> }
>
> // sort
> @@ -1905,15 +1929,16 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> inline void
> - __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
> - _Compare __comp)
> + __sort(pair<_Compare, _RandomAccessIterator> __cmp_first,
> + _RandomAccessIterator __last)
> {
> + const _RandomAccessIterator __first = __cmp_first.second;
> if (__first != __last)
> {
> - std::__introsort_loop(__first, __last,
> - std::__lg(__last - __first) * 2,
> - __comp);
> - std::__final_insertion_sort(__first, __last, __comp);
> + __cmp_first = std::__introsort_loop(
> + _GLIBCXX_MOVE(__cmp_first), __last, std::__lg(__last-__first) *
> 2);
> + std::__final_insertion_sort(__first, __last,
> + _GLIBCXX_MOVE(__cmp_first.first));
> }
> }
>
> @@ -1927,24 +1952,29 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> _RandomAccessIterator __after_nth = __nth;
> ++__after_nth;
>
> + typedef pair<_Compare, _RandomAccessIterator> _CmpFirst;
> + _CmpFirst __cmp_first(_GLIBCXX_MOVE(__comp), __first);
> while (__last - __first > 3)
> {
> if (__depth_limit == 0)
> {
> - std::__heap_select(__first, __after_nth, __last, __comp);
> + std::__heap_select(
> + __first, __after_nth, __last, __cmp_first.first);
> // Place the nth largest element in its final position.
> std::iter_swap(__first, __nth);
> return;
> }
> --__depth_limit;
> - _RandomAccessIterator __cut =
> - std::__unguarded_partition_pivot(__first, __last, __comp);
> + __cmp_first.second = __first;
> + __cmp_first = std::__unguarded_partition_pivot(
> + __GLIBCXX_MOVE(__cmp_first), __last);
> + _RandomAccessIterator __cut = __cmp_first.second;
> if (__cut <= __nth)
> __first = __cut;
> else
> __last = __cut;
> }
> - std::__insertion_sort(__first, __last, __comp);
> + std::__insertion_sort(__first, __last, __cmp_first.first);
> }
>
> /// @endcond
> @@ -2666,10 +2696,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> {
> while (__last - __first >= __chunk_size)
> {
> - std::__insertion_sort(__first, __first + __chunk_size, __comp);
> + __comp = std::__insertion_sort(
> + __first, __first + __chunk_size, _GLIBCXX_MOVE(__comp));
> __first += __chunk_size;
> }
> - std::__insertion_sort(__first, __last, __comp);
> + std::__insertion_sort(__first, __last, _GLIBCXX_MOVE(__comp));
> }
>
> enum { _S_chunk_size = 7 };
> @@ -2751,16 +2782,16 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> {
> if (__last - __first < 15)
> {
> - std::__insertion_sort(__first, __last, __comp);
> + std::__insertion_sort(__first, __last, _GLIBCXX_MOVE(__comp));
> return;
> }
> _RandomAccessIterator __middle = __first + (__last - __first) / 2;
> - std::__inplace_stable_sort(__first, __middle, __comp);
> - std::__inplace_stable_sort(__middle, __last, __comp);
> + __comp = std::__inplace_stable_sort(
> + __first, __middle, _GLIBCXX_MOVE(__comp));
> + __comp = std::__inplace_stable_sort(
> + __middle, __last, _GLIBCXX_MOVE(__comp));
> std::__merge_without_buffer(__first, __middle, __last,
> - __middle - __first,
> - __last - __middle,
> - __comp);
> + __middle - __first, __last - __middle, _GLIBCXX_MOVE(__comp));
> }
>
> // stable_sort
> @@ -4814,7 +4845,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> __glibcxx_requires_valid_range(__first, __last);
> __glibcxx_requires_irreflexive(__first, __last);
>
> - std::__sort(__first, __last, __gnu_cxx::__ops::less());
> + std::sort(__first, __last, __gnu_cxx::__ops::less());
> }
>
> /**
> @@ -4846,7 +4877,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> __glibcxx_requires_valid_range(__first, __last);
> __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
>
> - std::__sort(__first, __last, __comp);
> + typedef pair<_Compare, _RandomAccessIterator> _CmpFirst;
> + std::__sort(_CmpFirst(_GLIBCXX_MOVE(__comp), __first), __last);
> }
>
> template<typename _InputIterator1, typename _InputIterator2,
> diff --git a/libstdc++-v3/include/bits/stl_heap.h
> b/libstdc++-v3/include/bits/stl_heap.h
> index 8c5c5df5266..458803e0c45 100644
> --- a/libstdc++-v3/include/bits/stl_heap.h
> +++ b/libstdc++-v3/include/bits/stl_heap.h
> @@ -224,7 +224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> template<typename _RandomAccessIterator, typename _Distance,
> typename _Tp, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
> _Distance __len, _Tp __value, _Compare __comp)
> {
> @@ -248,13 +248,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> }
> std::__push_heap(__first, __holeIndex, __topIndex,
> _GLIBCXX_MOVE(__value), __comp);
> + return __comp;
> }
>
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - inline void
> + inline _Compare
> __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
> - _RandomAccessIterator __result, _Compare& __comp)
> + _RandomAccessIterator __result, _GLIBCXX_FWDREF(_Compare)
> __comp)
> {
> typedef typename iterator_traits<_RandomAccessIterator>::value_type
> _ValueType;
> @@ -263,9 +264,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
> _ValueType __value = _GLIBCXX_MOVE(*__result);
> *__result = _GLIBCXX_MOVE(*__first);
> - std::__adjust_heap(__first, _DistanceType(0),
> + return std::__adjust_heap(__first, _DistanceType(0),
> _DistanceType(__last - __first),
> - _GLIBCXX_MOVE(__value), __comp);
> + _GLIBCXX_MOVE(__value),
> + _GLIBCXX_FORWARD(_Compare, __comp));
> }
>
> /**
> @@ -330,15 +332,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> if (__last - __first > 1)
> {
> --__last;
> - std::__pop_heap(__first, __last, __last, __comp);
> + std::__pop_heap(__first, __last, __last, _GLIBCXX_MOVE(__comp));
> }
> }
>
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
> - _Compare& __comp)
> + _Compare __comp)
> {
> typedef typename iterator_traits<_RandomAccessIterator>::value_type
> _ValueType;
> @@ -346,19 +348,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _DistanceType;
>
> if (__last - __first < 2)
> - return;
> + return __comp;
>
> const _DistanceType __len = __last - __first;
> _DistanceType __parent = (__len - 2) / 2;
> while (true)
> {
> _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
> - std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
> - __comp);
> + __comp = std::__adjust_heap( __first, __parent, __len,
> + _GLIBCXX_MOVE(__value), _GLIBCXX_MOVE(__comp));
> if (__parent == 0)
> - return;
> + break;
> __parent--;
> }
> + return __comp;
> }
>
> /**
> @@ -413,15 +416,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
> template<typename _RandomAccessIterator, typename _Compare>
> _GLIBCXX20_CONSTEXPR
> - void
> + _Compare
> __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
> - _Compare& __comp)
> + _Compare __comp)
> {
> while (__last - __first > 1)
> {
> --__last;
> - std::__pop_heap(__first, __last, __last, __comp);
> + __comp = std::__pop_heap(
> + __first, __last, __last, _GLIBCXX_MOVE(__comp));
> }
> + return __comp;
> }
>
> /**
> --
> 2.54.0
>
