[PATCH 4/7] libstdc++: Remove indirection to __find_if in std::find etc.

[Jonathan Wakely]

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
>