On 15/10/24 15:20 +0100, 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.
Hmm, I wonder if inverting the relationship below (__find_if calls
find, instead of vice versa) can cause an ABI problem if one TU has an
instantiation of the old find that calls __find_if, and another TU has
an instantiation of the new __find_if that calls find, and they end up
calling each other recursively until the stack overflows.
We might need to mangle one of them differently.
- /**
- * @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));
- }
[...]
+ // 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
