[PATCH v5] libstdc++: less pred copying in sort, stable_sort [PR111963]
Nathan Myers
ncm@cantrip.org
Tue May 26 01:46:19 GMT 2026
Changes in v5:
* Do stable_sort's main code path, too.
* Suppress warning about long long on -std=c++98.
Changes in v4:
* Rename to _LocalStack, use C++26 constexpr reinterpret_cast.
Changes in v3:
* Define _IntrosortStack, so only as much local stack as is used
is initialized, and then is destructed after.
* 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 algorithms are _allowed_ to copy their predicate
argument, sort and stable_sort do so with wild abandon, and
unnecessarily. This patch eliminates all predicate copies on
their hot paths, inlining helper functions and passing their
predicate by reference so they can all use the same one,
without indirection. It makes the workhorse helper function
__introsort_loop non-recursive, and modifies two others, for
clean inlining. std::sort and std::stable_sort themselves are
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. Generated-code size, for empty predicates in sort, is
the same; for stable_sort on amd64, ~4kB less. std::sort on 16M
ints with a predicate where copying requires an allocation is
about 40% faster. The outer loop in sort<int*> is just 121
machine instructions.
The rest of <algorithm> may be improved similarly.
libstdc++-v3/ChangeLog:
PR libstdc++/111963
* include/bits/stl_algo.h (_LocalStack): Define helper template.
(__sort, __unguarded_partition_pivot, __unguarded_insertion_sort,
__unguarded_linear_insert, __insertion_sort __unguarded_partition,
__move_median_to_first, __move_merge_adaptive_backward, __move_merge,
__move_merge_adaptive, __merge_adaptive, __merge_sort_with_buffer,
__merge_sort_loop, __chunk_insertion_sort, __stable_sort_adaptive,
__stable_sort): Inline, and take predicate by reference.
(__final_insertion_sort, __chunk_insertion_sort): Same, and rewrite
for better inlining.
(__introsort_loop): Same, and make non-recursive with a local stack.
(sort, stable_sort (3-argument form)): Make non-inline.
(sort, stable_sort (2-argument form)): Delegate to above.
---
libstdc++-v3/include/bits/stl_algo.h | 187 +++++++++++++++++----------
1 file changed, 122 insertions(+), 65 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index adf9b9e0f28..35137c55bff 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,86 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
std::__sort_heap(__first, __middle, __comp);
}
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++26-extensions" // reinterpret_cast
+#pragma GCC diagnostic ignored "-Wlong-long"
+
+ template <typename _Element, int __size>
+ struct _LocalStack
+ {
+ union _Slot { char __bytes[sizeof(_Element)]; long long __aligner; };
+ _Slot* __top;
+ _Slot* __limit;
+ _Slot __storage[__size];
+
+ _GLIBCXX20_CONSTEXPR
+ _LocalStack(int __depth)
+ : __top(__storage), __limit(__storage + min(__depth, __size)) {}
+
+ _GLIBCXX20_CONSTEXPR bool __is_full() { return __top == __limit; }
+ _GLIBCXX20_CONSTEXPR bool __is_empty() { return __top == __storage; }
+
+ _GLIBCXX20_CONSTEXPR void
+ __push(_GLIBCXX_FWDREF(_Element) __e)
+ { ::new(__top++->__bytes) _Element(_GLIBCXX_MOVE(__e)); }
+
+ _GLIBCXX20_CONSTEXPR void
+ __pop(_Element& __element)
+ {
+ __element = _GLIBCXX_MOVE(*reinterpret_cast<_Element*>(--__top));
+ reinterpret_cast<_Element*>(__top)->_Element::~_Element();
+ }
+ };
+
+#pragma GCC diagnostic pop
+
/// 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;
+ _Range __range(__first, __last);
+ _LocalStack<_Range, 64> __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);
}
}
@@ -2250,10 +2297,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the __merge_adaptive routines.
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
- _OutputIterator __result, _Compare __comp)
+ _OutputIterator __result, _Compare& __comp)
{
while (__first1 != __last1 && __first2 != __last2)
{
@@ -2276,13 +2324,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the __merge_adaptive routines.
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BidirectionalIterator3, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
_BidirectionalIterator1 __last1,
_BidirectionalIterator2 __first2,
_BidirectionalIterator2 __last2,
_BidirectionalIterator3 __result,
- _Compare __comp)
+ _Compare& __comp)
{
if (__first1 == __last1)
{
@@ -2357,12 +2406,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the merge routines.
template<typename _BidirectionalIterator, typename _Distance,
typename _Pointer, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__merge_adaptive(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
_BidirectionalIterator __last,
_Distance __len1, _Distance __len2,
- _Pointer __buffer, _Compare __comp)
+ _Pointer __buffer, _Compare& __comp)
{
if (__len1 <= __len2)
{
@@ -2608,10 +2658,11 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
/// This is a helper function for the __merge_sort_loop routines.
template<typename _InputIterator, typename _OutputIterator,
typename _Compare>
- _OutputIterator
+ [[__gnu__::__always_inline__]]
+ inline _OutputIterator
__move_merge(_InputIterator __first1, _InputIterator __last1,
_InputIterator __first2, _InputIterator __last2,
- _OutputIterator __result, _Compare __comp)
+ _OutputIterator __result, _Compare& __comp)
{
while (__first1 != __last1 && __first2 != __last2)
{
@@ -2634,11 +2685,12 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__merge_sort_loop(_RandomAccessIterator1 __first,
_RandomAccessIterator1 __last,
_RandomAccessIterator2 __result, _Distance __step_size,
- _Compare __comp)
+ _Compare& __comp)
{
const _Distance __two_step = 2 * __step_size;
@@ -2658,27 +2710,29 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX20_CONSTEXPR
- void
+ inline void
__chunk_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
- _Distance __chunk_size, _Compare __comp)
+ _Distance __chunk_size, _Compare& __comp)
{
- while (__last - __first >= __chunk_size)
+ while (__first != __last)
{
- std::__insertion_sort(__first, __first + __chunk_size, __comp);
- __first += __chunk_size;
+ _Distance __todo = min(__last - __first, __chunk_size);
+ std::__insertion_sort(__first, __first + __todo, __comp);
+ __first += __todo;
}
- std::__insertion_sort(__first, __last, __comp);
}
enum { _S_chunk_size = 7 };
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__merge_sort_with_buffer(_RandomAccessIterator __first,
_RandomAccessIterator __last,
- _Pointer __buffer, _Compare __comp)
+ _Pointer __buffer, _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;
@@ -2701,11 +2755,12 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
}
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
- void
+ [[__gnu__::__always_inline__]]
+ inline void
__stable_sort_adaptive(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last,
- _Pointer __buffer, _Compare __comp)
+ _Pointer __buffer, _Compare& __comp)
{
std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
@@ -4814,7 +4869,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 +4887,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)
{
@@ -4972,10 +5028,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
}
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__always_inline__]]
_GLIBCXX26_CONSTEXPR
inline void
__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Compare __comp)
+ _Compare& __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -5040,8 +5097,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- _GLIBCXX_STD_A::__stable_sort(__first, __last,
- __gnu_cxx::__ops::less());
+ std::stable_sort(__first, __last, __gnu_cxx::__ops::less());
}
/**
@@ -5062,8 +5118,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* relative ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIterator, typename _Compare>
+ [[__gnu__::__noinline__]]
_GLIBCXX26_CONSTEXPR
- inline void
+ void
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
--
2.54.0
More information about the Libstdc++
mailing list