ZOn Tue, 15 Oct 2024, Jonathan Wakely wrote:
> Tested x86_64-linux.
>
> -- >8 --
>
> There doesn't seem to be a lot of benefit in reusing __find_if with
> __gnu_cxx::__ops predicates, since they aren't going to actually
> instantiate any less code if we use different predicates every time
> (e.g. __ops::__negate, or __ops::__iter_equals_val, or
> __ops::__pred_iter).
>
> And now that std::find no longer calls __find_if (because it just does a
> loop directly), we can make the _Iter_equals_val case of __find_if call
> std::find, to take advantage of its memchr optimization. This benefits
> other algos like search_n which use __find_if with _Iter_equals_val.
Makes sense, LGTM
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/stl_algo.h (__find_if_not): Do loop here instead
> of using __find_if with __gnu_cxx::__ops predicate.
> (find_if): Likewise.
> (find): Move to ...
> * include/bits/stl_algobase.h (find): ... here.
> (__find_if): Overload for _Iter_equals_val predicate.
> ---
> libstdc++-v3/include/bits/stl_algo.h | 63 +++---------------------
> libstdc++-v3/include/bits/stl_algobase.h | 61 +++++++++++++++++++++++
> 2 files changed, 68 insertions(+), 56 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> index 489ce7e14d2..05c1dbd07b6 100644
> --- a/libstdc++-v3/include/bits/stl_algo.h
> +++ b/libstdc++-v3/include/bits/stl_algo.h
> @@ -105,15 +105,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> std::iter_swap(__result, __b);
> }
>
> - /// Provided for stable_partition to use.
> + // Used by std::find_if_not and __stable_partition.
> template<typename _InputIterator, typename _Predicate>
> _GLIBCXX20_CONSTEXPR
> inline _InputIterator
> __find_if_not(_InputIterator __first, _InputIterator __last,
> _Predicate __pred)
> {
> - return std::__find_if(__first, __last,
> - __gnu_cxx::__ops::__negate(__pred));
> + while (__first != __last && __pred(__first))
> + ++__first;
> + return __first;
> }
>
> /// Like find_if_not(), but uses and updates a count of the
> @@ -3810,57 +3811,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> }
> #endif // C++17
>
> - /**
> - * @brief Find the first occurrence of a value in a sequence.
> - * @ingroup non_mutating_algorithms
> - * @param __first An input iterator.
> - * @param __last An input iterator.
> - * @param __val The value to find.
> - * @return The first iterator @c i in the range @p [__first,__last)
> - * such that @c *i == @p __val, or @p __last if no such iterator exists.
> - */
> - template<typename _InputIterator, typename _Tp>
> - _GLIBCXX20_CONSTEXPR
> - inline _InputIterator
> - find(_InputIterator __first, _InputIterator __last, const _Tp& __val)
> - {
> - // concept requirements
> - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
> - __glibcxx_function_requires(_EqualOpConcept<
> - typename iterator_traits<_InputIterator>::value_type, _Tp>)
> - __glibcxx_requires_valid_range(__first, __last);
> -
> -#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
> - using _ValT = typename iterator_traits<_InputIterator>::value_type;
> - if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
> - if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
> -#if __cpp_lib_concepts
> - || contiguous_iterator<_InputIterator>
> -#endif
> - )
> - {
> - // If conversion to the 1-byte value_type alters the value,
> - // it would not be found by std::find using equality comparison.
> - // We need to check this here, because otherwise something like
> - // memchr("a", 'a'+256, 1) would give a false positive match.
> - if (!(static_cast<_ValT>(__val) == __val))
> - return __last;
> - else if (!__is_constant_evaluated())
> - {
> - const void* __p0 = std::__to_address(__first);
> - const int __ival = static_cast<int>(__val);
> - if (auto __n = std::distance(__first, __last); __n > 0)
> - if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
> - return __first + ((const char*)__p1 - (const char*)__p0);
> - return __last;
> - }
> - }
> -#endif
> -
> - return std::__find_if(__first, __last,
> - __gnu_cxx::__ops::__iter_equals_val(__val));
> - }
> -
> /**
> * @brief Find the first element in a sequence for which a
> * predicate is true.
> @@ -3883,8 +3833,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> typename iterator_traits<_InputIterator>::value_type>)
> __glibcxx_requires_valid_range(__first, __last);
>
> - return std::__find_if(__first, __last,
> - __gnu_cxx::__ops::__pred_iter(__pred));
> + while (__first != __last && !__pred(*__first))
> + ++__first;
> + return __first;
> }
>
> /**
> diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> b/libstdc++-v3/include/bits/stl_algobase.h
> index 5f77b00be9b..34e1cf7322f 100644
> --- a/libstdc++-v3/include/bits/stl_algobase.h
> +++ b/libstdc++-v3/include/bits/stl_algobase.h
> @@ -2077,6 +2077,58 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> }
> #endif
>
> + /**
> + * @brief Find the first occurrence of a value in a sequence.
> + * @ingroup non_mutating_algorithms
> + * @param __first An input iterator.
> + * @param __last An input iterator.
> + * @param __val The value to find.
> + * @return The first iterator @c i in the range @p [__first,__last)
> + * such that @c *i == @p __val, or @p __last if no such iterator exists.
> + */
> + template<typename _InputIterator, typename _Tp>
> + _GLIBCXX20_CONSTEXPR
> + inline _InputIterator
> + find(_InputIterator __first, _InputIterator __last, const _Tp& __val)
> + {
> + // concept requirements
> + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
> + __glibcxx_function_requires(_EqualOpConcept<
> + typename iterator_traits<_InputIterator>::value_type, _Tp>)
> + __glibcxx_requires_valid_range(__first, __last);
> +
> +#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
> + using _ValT = typename iterator_traits<_InputIterator>::value_type;
> + if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
> + if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
> +#if __cpp_lib_concepts
> + || contiguous_iterator<_InputIterator>
> +#endif
> + )
> + {
> + // If conversion to the 1-byte value_type alters the value,
> + // it would not be found by std::find using equality comparison.
> + // We need to check this here, because otherwise something like
> + // memchr("a", 'a'+256, 1) would give a false positive match.
> + if (!(static_cast<_ValT>(__val) == __val))
> + return __last;
> + else if (!__is_constant_evaluated())
> + {
> + const void* __p0 = std::__to_address(__first);
> + const int __ival = static_cast<int>(__val);
> + if (auto __n = std::distance(__first, __last); __n > 0)
> + if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
> + return __first + ((const char*)__p1 - (const char*)__p0);
> + return __last;
> + }
> + }
> +#endif
> +
> + while (__first != __last && !(*__first == __val))
> + ++__first;
> + return __first;
> + }
> +
> _GLIBCXX_END_NAMESPACE_ALGO
>
> // Implementation of std::find_if, also used in std::remove_if and others.
> @@ -2091,6 +2143,15 @@ _GLIBCXX_END_NAMESPACE_ALGO
> return __first;
> }
>
> + // When the predicate is just comparing to a value we can use std::find,
> + // which is optimized to memchr for some types.
> + template<typename _Iterator, typename _Value>
> + _GLIBCXX20_CONSTEXPR
> + inline _Iterator
> + __find_if(_Iterator __first, _Iterator __last,
> + __gnu_cxx::__ops::_Iter_equals_val<_Value> __pred)
> + { return _GLIBCXX_STD_A::find(__first, __last, __pred._M_value); }
> +
> template<typename _InputIterator, typename _Predicate>
> _GLIBCXX20_CONSTEXPR
> typename iterator_traits<_InputIterator>::difference_type
> --
> 2.46.2
>
>
