[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)
+ _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
