On Mon, May 18, 2026 at 6:34 AM 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.]
>
> 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)
>
The reference here is related to uses of this helper inside priority_queue,
see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67085.
In that case, the user cannot really choose to pass std::ref(comp), as the
calls
are done inside the adaptor code. We could use reference_wrapper as heap
compare, but that is prone to cause dangling references (if queue is copied,
the comparator will still refer to the old one), or data races (if
comparator caches
result, and multiple queues from multiple threads use the same one).
> + _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
>
>
