Change in v2: Mention correct PR number in commit text.
While std::sort is allowed to copy its predicate argument, it
does so with wild abandon, unnecessarily. This patch eliminates
all but one copy on the hot path, inlining helper functions and
taking their predicate by reference so they can re-use the
first copy without indirection. It recasts the workhorse helper
function __introsort_loop without recursion to inline cleanly.
std::sort itself is made non-inline, so each specialization may
be called from many places without bloat.
The effect is largest for predicates whose copy ctors are not
trivial. The changes have little effect on compiled code size,
otherwise. The rest of <algorithm> may be treated similarly.
libstdc++-v3/ChangeLog:
PR libstdc++/111963
* include/bits/stl_algo.h (__sort, __unguarded_partition_pivot,
__move_median_to_first, __unguarded_partition, __final_insertion_sort,
__unguarded_insertion_sort, __unguarded_linear_insert):
Inline, take predicate argument by reference.
(__introsort_loop): Same, and rewrite to use an explicit local stack.
(sort (3-argument form)): Make non-inline.
(sort (2-argument form)): Same, and pass a non-const predicate.
---
libstdc++-v3/include/bits/stl_algo.h | 83 ++++++++++++++++------------
1 file changed, 49 insertions(+), 34 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index adf9b9e0f28..69dd1d24c67 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -83,10 +83,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- void
+ inline void
__move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b,
- _Iterator __c, _Compare __comp)
+ _Iterator __c, _Compare& __comp)
{
if (__comp(*__a, *__b))
{
@@ -1745,10 +1746,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- void
+ inline void
__unguarded_linear_insert(_RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last);
@@ -1791,10 +1793,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last, _Compare __comp)
+ _RandomAccessIterator __last, _Compare& __comp)
{
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, __comp);
@@ -1808,10 +1811,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- void
+ inline void
__final_insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last, _Compare __comp)
+ _RandomAccessIterator __last, _Compare& __comp)
{
typename iterator_traits<_RandomAccessIterator>::difference_type
__threshold = _S_threshold;
@@ -1828,11 +1832,12 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- _RandomAccessIterator
+ inline _RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
- _RandomAccessIterator __pivot, _Compare __comp)
+ _RandomAccessIterator __pivot, _Compare& __comp)
{
while (true)
{
@@ -1850,10 +1855,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
- _RandomAccessIterator __last, _Compare __comp)
+ _RandomAccessIterator __last, _Compare& __comp)
{
typedef iterator_traits<_RandomAccessIterator> _IterTraits;
typedef typename _IterTraits::difference_type _Dist;
@@ -1877,28 +1883,38 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
std::__sort_heap(__first, __middle, __comp);
}
- /// This is a helper function for the sort routine.
- template<typename _RandomAccessIterator, typename _Size, typename _Compare>
+ template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- void
+ inline void
__introsort_loop(_RandomAccessIterator __first,
- _RandomAccessIterator __last,
- _Size __depth_limit, _Compare __comp)
+ _RandomAccessIterator __last, _Compare& __comp)
{
- while (__last - __first > int(_S_threshold))
+ typedef pair<_RandomAccessIterator, _RandomAccessIterator> _Range;
+ const int __stack_size = 128;
+ _Range __stack[__stack_size];
+ int __top = -1;
+ _Range __range(__first, __last);
+ while (true)
{
- if (__depth_limit == 0)
- {
- std::__partial_sort(__first, __last, __last, __comp);
- return;
- }
- --__depth_limit;
- _RandomAccessIterator __cut =
- std::__unguarded_partition_pivot(__first, __last, __comp);
- std::__introsort_loop(__cut, __last, __depth_limit, __comp);
- __last = __cut;
+ if (__range.second - __range.first > int(_S_threshold))
+ if (__builtin_expect(__top < __stack_size - 1, true))
+ {
+ _RandomAccessIterator __cut = std::__unguarded_partition_pivot(
+ __range.first, __range.second, __comp);
+ __stack[++__top] = _Range(__cut, __range.second);
+ // __stack[++__top] = _Range(range_first, __cut);
+ // Skip push-and-pop, do immediately:
+ { __range.second = __cut; continue; }
+ }
+ else std::__partial_sort(__range.first, __range.second,
+ __range.second, __comp);
+
+ if (__builtin_expect(__top < 0, false))
+ break;
+ __range = __stack[__top--];
}
- }
+ }
// sort
@@ -1906,13 +1922,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
_GLIBCXX20_CONSTEXPR
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
if (__first != __last)
{
- std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2,
- __comp);
+ std::__introsort_loop(__first, __last, __comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
@@ -4803,7 +4817,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
*/
template<typename _RandomAccessIterator>
_GLIBCXX20_CONSTEXPR
- inline void
+ void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
@@ -4814,7 +4828,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- std::__sort(__first, __last, __gnu_cxx::__ops::less());
+ __gnu_cxx::__ops::less __comp;
+ std::__sort(__first, __last, __comp);
}
/**
@@ -4833,7 +4848,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
*/
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
- inline void
+ void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
--
2.54.0
