[PATCH v3] libstdc++: minimize predicate copying in std::sort [PR111963]
Nathan Myers
ncm@cantrip.org
Sat May 23 11:02:41 GMT 2026
Changes in v3:
* Define _IntrosortStack, so only as much local stack as is used
is initialized, and then destructed when unused.
* Restore using the log of the input size as the stack depth limit.
* Simplify __final_insertion_sort for better inlining.
* Inline __insertion_sort too.
* Quiet __introsort_loop "ambiguous else" warning.
Changes 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 predicate copies on the hot path, inlining helper functions
and passing their predicate by reference so they can re-use
std::sort's without indirection. It makes the workhorse helper
function __introsort_loop non-recursive, 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 (_IntrosortStack): Define.
(__sort, __unguarded_partition_pivot, __unguarded_partition,
__move_median_to_first, __final_insertion_sort,
__unguarded_insertion_sort, __unguarded_linear_insert): Inline, and
take predicate argument by reference.
(__insertion_sort): Same, and rewrite for better inlining.
(__introsort_loop): Same, and make non-recursive with a local stack.
(sort (3-argument form)): Make non-inline.
(sort (2-argument form)): Delegate to it.
---
libstdc++-v3/include/bits/stl_algo.h | 130 ++++++++++++++++++---------
1 file changed, 88 insertions(+), 42 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index adf9b9e0f28..b1cecefb142 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);
@@ -1765,10 +1767,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
__insertion_sort(_RandomAccessIterator __first,
- _RandomAccessIterator __last, _Compare __comp)
+ _RandomAccessIterator __last, _Compare& __comp)
{
if (__first == __last)
return;
@@ -1791,10 +1794,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,31 +1812,29 @@ _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;
-
- if (__last - __first > __threshold)
- {
- std::__insertion_sort(__first, __first + __threshold, __comp);
- std::__unguarded_insertion_sort(__first + __threshold, __last,
- __comp);
- }
- else
- std::__insertion_sort(__first, __last, __comp);
+ __threshold = int(_S_threshold);
+ _RandomAccessIterator __step =
+ __threshold < __last - __first ? __first + __threshold : __last;
+ std::__insertion_sort(__first, __step, __comp);
+ if (__step != __last)
+ std::__unguarded_insertion_sort(__step, __last, __comp);
}
/// 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 +1852,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,42 +1880,84 @@ _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 _Element, int __size = 64>
+ struct _IntrosortStack
+ {
+ union _Slot { char __bytes[sizeof(_Element)]; long long __aligner; };
+ _Element* __end;
+ _Slot* __top;
+ _Slot* __limit;
+ _Slot __storage[__size];
+
+ _GLIBCXX20_CONSTEXPR
+ _IntrosortStack(int __depth)
+ : __top(__storage), __limit(__storage + min(__depth, int(__size))) {}
+
+ _GLIBCXX20_CONSTEXPR bool
+ __is_full() const { return __top == __limit; }
+
+ _GLIBCXX20_CONSTEXPR bool
+ __is_empty() const { return __top == __storage; }
+
+ _GLIBCXX20_CONSTEXPR void
+ __push(_GLIBCXX_FWDREF(_Element) __e)
+ { __end = 1 + ::new(__top++->__bytes) _Element(_GLIBCXX_MOVE(__e)); }
+
+ _GLIBCXX20_CONSTEXPR void
+ __pop(_Element& __element)
+ {
+ __element = _GLIBCXX_MOVE(*--__end);
+ __end->_Element::~_Element();
+ --__top;
+ }
+ };
+
+ 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;
+ _Range __range(__first, __last);
+ _IntrosortStack<_Range> __stack(std::__lg(__last - __first) * 2);
+ while (true)
{
- if (__depth_limit == 0)
+ if (__range.second - __range.first > int(_S_threshold))
{
- std::__partial_sort(__first, __last, __last, __comp);
- return;
+ if (__builtin_expect(!__stack.__is_full(), true))
+ {
+ _RandomAccessIterator __cut =
+ std::__unguarded_partition_pivot(
+ __range.first, __range.second, __comp);
+ // Schedule high half for later.
+ __stack.__push(_Range(__cut, __range.second));
+ // Partition the low half immediately.
+ { __range.second = __cut; continue; }
+ }
+ else std::__partial_sort(
+ __range.first, __range.second, __range.second, __comp);
}
- --__depth_limit;
- _RandomAccessIterator __cut =
- std::__unguarded_partition_pivot(__first, __last, __comp);
- std::__introsort_loop(__cut, __last, __depth_limit, __comp);
- __last = __cut;
+
+ if (__builtin_expect(__stack.__is_empty(), false))
+ break;
+ __stack.__pop(__range);
}
}
// sort
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_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);
}
}
@@ -4814,7 +4859,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());
}
/**
@@ -4832,8 +4877,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* `stable_sort()` if this is needed.
*/
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__noinline__]]
_GLIBCXX20_CONSTEXPR
- inline void
+ void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
--
2.54.0
More information about the Libstdc++
mailing list