https://gcc.gnu.org/g:e69456ff9a54ba3e9c93842b05757b7d8fff6d9d
commit r15-2356-ge69456ff9a54ba3e9c93842b05757b7d8fff6d9d
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Thu Jul 4 12:01:29 2024 +0100
libstdc++: Remove __find_if unrolling for random access iterators
As the numbers in PR libstdc++/88545 show, the manual loop unrolling in
std::__find_if doesn't actually help these days, and it prevents the
compiler from auto-vectorizing.
Remove the dispatching on iterator_category and just use the simple loop
for all iterator categories.
libstdc++-v3/ChangeLog:
* include/bits/stl_algobase.h (__find_if): Remove overloads for
dispatching on iterator_category. Do not unroll loop manually.
* include/bits/stl_algo.h (__find_if_not): Remove
iterator_category argument from __find_if call.
Diff:
---
libstdc++-v3/include/bits/stl_algo.h | 3 +-
libstdc++-v3/include/bits/stl_algobase.h | 70 ++------------------------------
2 files changed, 5 insertions(+), 68 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index d250b2e04d4d..541f588883b2 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -110,8 +110,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Predicate __pred)
{
return std::__find_if(__first, __last,
- __gnu_cxx::__ops::__negate(__pred),
- std::__iterator_category(__first));
+ __gnu_cxx::__ops::__negate(__pred));
}
/// Like find_if_not(), but uses and updates a count of the
diff --git a/libstdc++-v3/include/bits/stl_algobase.h
b/libstdc++-v3/include/bits/stl_algobase.h
index dec1e4c79d86..27f6c377ad6f 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -2098,77 +2098,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
_GLIBCXX_END_NAMESPACE_ALGO
- /// This is an overload used by find algos for the Input Iterator case.
- template<typename _InputIterator, typename _Predicate>
- _GLIBCXX20_CONSTEXPR
- inline _InputIterator
- __find_if(_InputIterator __first, _InputIterator __last,
- _Predicate __pred, input_iterator_tag)
- {
- while (__first != __last && !__pred(__first))
- ++__first;
- return __first;
- }
-
- /// This is an overload used by find algos for the RAI case.
- template<typename _RandomAccessIterator, typename _Predicate>
- _GLIBCXX20_CONSTEXPR
- _RandomAccessIterator
- __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _Predicate __pred, random_access_iterator_tag)
- {
- typename iterator_traits<_RandomAccessIterator>::difference_type
- __trip_count = (__last - __first) >> 2;
-
- for (; __trip_count > 0; --__trip_count)
- {
- if (__pred(__first))
- return __first;
- ++__first;
-
- if (__pred(__first))
- return __first;
- ++__first;
-
- if (__pred(__first))
- return __first;
- ++__first;
-
- if (__pred(__first))
- return __first;
- ++__first;
- }
-
- switch (__last - __first)
- {
- case 3:
- if (__pred(__first))
- return __first;
- ++__first;
- // FALLTHRU
- case 2:
- if (__pred(__first))
- return __first;
- ++__first;
- // FALLTHRU
- case 1:
- if (__pred(__first))
- return __first;
- ++__first;
- // FALLTHRU
- case 0:
- default:
- return __last;
- }
- }
-
+ // Implementation of std::find_if, also used in std::remove_if and others.
template<typename _Iterator, typename _Predicate>
_GLIBCXX20_CONSTEXPR
inline _Iterator
__find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
{
- return __find_if(__first, __last, __pred,
- std::__iterator_category(__first));
+ while (__first != __last && !__pred(__first))
+ ++__first;
+ return __first;
}
template<typename _InputIterator, typename _Predicate>
