Vectorize equality-comparing algorithms for more types (#5527)

AlexGuteniev · StephanTLavavej · web-flow · commit 3da7d27db7d7 · 2025-05-22T13:39:56.000-07:00
Co-authored-by: Stephan T. Lavavej &lt;stl@microsoft.com&gt;
diff --git a/stl/inc/algorithm b/stl/inc/algorithm
@@ -351,11 +351,6 @@ _Ty* _Unique_copy_vectorized(const _Ty* const _First, const _Ty* const _Last, _T
         _STL_INTERNAL_STATIC_ASSERT(false); // Unexpected size
     }
 }
-
-// Can we activate the vector algorithms for find_first_of?
-template <class _It1, class _It2, class _Pr>
-constexpr bool _Vector_alg_in_find_first_of_is_safe = _Equal_memcmp_is_safe<_It1, _It2, _Pr>;
-
 // Can we activate the vector algorithms for replace?
 template <class _Iter, class _Ty1>
 constexpr bool _Vector_alg_in_replace_is_safe = _Vector_alg_in_find_is_safe<_Iter, _Ty1> // can search for the value
@@ -376,7 +371,7 @@ constexpr bool _Vector_alg_in_search_n_is_safe = _Vector_alg_in_find_is_safe<_It
                                                   equal_to<>>;
 // Can we activate the vector algorithms for unique?
 template <class _Iter, class _Pr>
-constexpr bool _Vector_alg_in_unique_is_safe = _Equal_memcmp_is_safe<_Iter, _Iter, _Pr>;
+constexpr bool _Vector_alg_in_unique_is_safe = _Vector_alg_in_search_is_safe<_Iter, _Iter, _Pr>;
 
 // Can we use this output iterator for remove_copy or unique_copy?
 template <class _Out, class _In>
@@ -712,7 +707,7 @@ _NODISCARD _CONSTEXPR20 _FwdIt adjacent_find(const _FwdIt _First, _FwdIt _Last,
     auto _ULast  = _STD _Get_unwrapped(_Last);
     if (_UFirst != _ULast) {
 #if _USE_STD_VECTOR_ALGORITHMS
-        if constexpr (_Equal_memcmp_is_safe<decltype(_UFirst), decltype(_UFirst), _Pr>) {
+        if constexpr (_Vector_alg_in_search_is_safe<decltype(_UFirst), decltype(_UFirst), _Pr>) {
             if (!_STD _Is_constant_evaluated()) {
                 const auto _First_ptr = _STD _To_address(_UFirst);
                 const auto _Result    = _STD _Adjacent_find_vectorized(_First_ptr, _STD _To_address(_ULast));
@@ -888,7 +883,7 @@ _NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(_InIt1 _First1, const _InI
     const auto _ULast1 = _STD _Get_unwrapped(_Last1);
     auto _UFirst2      = _STD _Get_unwrapped_n(_First2, _STD _Idl_distance<_InIt1>(_UFirst1, _ULast1));
 #if _USE_STD_VECTOR_ALGORITHMS
-    if constexpr (_Equal_memcmp_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
+    if constexpr (_Vector_alg_in_search_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
         if (!_STD _Is_constant_evaluated()) {
             constexpr size_t _Elem_size = sizeof(_Iter_value_t<_InIt1>);
 
@@ -952,7 +947,7 @@ _NODISCARD _CONSTEXPR20 pair<_InIt1, _InIt2> mismatch(
         const auto _Count = static_cast<_Iter_diff_t<_InIt1>>((_STD min)(_Count1, _Count2));
         _ULast1           = _UFirst1 + _Count;
 #if _USE_STD_VECTOR_ALGORITHMS
-        if constexpr (_Equal_memcmp_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
+        if constexpr (_Vector_alg_in_search_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
             if (!_STD _Is_constant_evaluated()) {
                 constexpr size_t _Elem_size = sizeof(_Iter_value_t<_InIt1>);
 
@@ -3796,7 +3791,7 @@ _NODISCARD _CONSTEXPR20 _FwdIt1 find_first_of(
     }
 
 #if _USE_STD_VECTOR_ALGORITHMS
-    if constexpr (_Vector_alg_in_find_first_of_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
+    if constexpr (_Vector_alg_in_search_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
         if (!_STD _Is_constant_evaluated() && _ULast1 - _UFirst1 >= _Threshold_find_first_of) {
             const auto _First1_ptr = _STD _To_address(_UFirst1);
             const auto _Result     = _STD _Find_first_of_vectorized(
@@ -3900,7 +3895,7 @@ namespace ranges {
             }
 
 #if _USE_STD_VECTOR_ALGORITHMS
-            if constexpr (_Vector_alg_in_find_first_of_is_safe<_It1, _It2, _Pr> && sized_sentinel_for<_Se1, _It1>
+            if constexpr (_Vector_alg_in_search_is_safe<_It1, _It2, _Pr> && sized_sentinel_for<_Se1, _It1>
                           && sized_sentinel_for<_Se2, _It2> && is_same_v<_Pj1, identity> && is_same_v<_Pj2, identity>) {
                 if (!_STD is_constant_evaluated() && _Last1 - _First1 >= _Threshold_find_first_of) {
                     const auto _Count1     = static_cast<ptrdiff_t>(_Last1 - _First1);
diff --git a/stl/inc/xutility b/stl/inc/xutility
@@ -63,6 +63,14 @@ _STL_DISABLE_CLANG_WARNINGS
 #endif // _USE_STD_VECTOR_FLOATING_ALGORITHMS && !_USE_STD_VECTOR_ALGORITHMS
 #endif // ^^^ defined(_USE_STD_VECTOR_FLOATING_ALGORITHMS) ^^^
 
+#ifndef _USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE
+#if defined(__clang__) && __clang_major__ >= 19
+#define _USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE 1
+#else // ^^^ defined(__clang__) && __clang_major__ >= 19 / !defined(__clang__) || __clang_major__ < 19 vvv
+#define _USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE 0
+#endif // ^^^ !defined(__clang__) || __clang_major__ < 19 ^^^
+#endif // ^^^ !defined(_USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE) ^^^
+
 #if _USE_STD_VECTOR_ALGORITHMS
 extern "C" {
 // The "noalias" attribute tells the compiler optimizer that pointers going into these hand-vectorized algorithms
@@ -5481,8 +5489,14 @@ inline constexpr bool _Can_memcmp_elements<byte, byte, false> = true;
 template <class _Ty1, class _Ty2>
 constexpr bool _Can_memcmp_elements<_Ty1*, _Ty2*, false> = _Is_pointer_address_comparable<_Ty1, _Ty2>;
 
+#if _USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE
+template <class _Elem1, class _Elem2>
+constexpr bool _Can_memcmp_elements<_Elem1, _Elem2, false> =
+    is_same_v<_Elem1, _Elem2> && __is_trivially_equality_comparable(_Elem1);
+#else // ^^^ _USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE / !_USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE vvv
 template <class _Elem1, class _Elem2>
 constexpr bool _Can_memcmp_elements<_Elem1, _Elem2, false> = false;
+#endif // ^^^ !_USE_BUILTIN_IS_TRIVIALLY_EQUALITY_COMPARABLE ^^^
 
 // _Can_memcmp_elements_with_pred<_Elem1, _Elem2, _Pr> reports whether the memcmp optimization is applicable,
 // given contiguously stored elements. (This avoids having to repeat the metaprogramming that finds the element types.)
@@ -5519,9 +5533,15 @@ template <class _Iter1, class _Iter2, class _Pr>
 constexpr bool _Equal_memcmp_is_safe =
     _Equal_memcmp_is_safe_helper<remove_const_t<_Iter1>, remove_const_t<_Iter2>, remove_const_t<_Pr>>;
 
+#if _USE_STD_VECTOR_ALGORITHMS
+template <size_t _Size>
+constexpr bool _Is_vector_element_size = _Size == 1 || _Size == 2 || _Size == 4 || _Size == 8;
+
 // Can we activate the vector algorithms for std::search?
 template <class _It1, class _It2, class _Pr>
-constexpr bool _Vector_alg_in_search_is_safe = _Equal_memcmp_is_safe<_It1, _It2, _Pr>;
+constexpr bool _Vector_alg_in_search_is_safe =
+    _Equal_memcmp_is_safe<_It1, _It2, _Pr> && _Is_vector_element_size<sizeof(_Iter_value_t<_It1>)>;
+#endif // _USE_STD_VECTOR_ALGORITHMS
 
 template <class _CtgIt1, class _CtgIt2>
 _NODISCARD int _Memcmp_count(_CtgIt1 _First1, _CtgIt2 _First2, const size_t _Count) {
@@ -5679,7 +5699,7 @@ namespace ranges {
         _It1 _First1, _It2 _First2, iter_difference_t<_It1> _Count, _Pr _Pred, _Pj1 _Proj1, _Pj2 _Proj2) {
         _STL_INTERNAL_CHECK(_Count >= 0);
 #if _USE_STD_VECTOR_ALGORITHMS
-        if constexpr (_Equal_memcmp_is_safe<_It1, _It2, _Pr> && is_same_v<_Pj1, identity>
+        if constexpr (_Vector_alg_in_search_is_safe<_It1, _It2, _Pr> && is_same_v<_Pj1, identity>
                       && is_same_v<_Pj2, identity>) {
             if (!_STD is_constant_evaluated()) {
                 constexpr size_t _Elem_size = sizeof(iter_value_t<_It1>);
@@ -6829,7 +6849,7 @@ namespace ranges {
             }
 
 #if _USE_STD_VECTOR_ALGORITHMS
-            if constexpr (_Equal_memcmp_is_safe<_It, _It, _Pr> && sized_sentinel_for<_Se, _It>
+            if constexpr (_Vector_alg_in_search_is_safe<_It, _It, _Pr> && sized_sentinel_for<_Se, _It>
                           && is_same_v<_Pj, identity>) {
                 if (!_STD is_constant_evaluated()) {
                     const auto _First_ptr = _STD _To_address(_First);
diff --git a/tests/std/tests/GH_000431_equal_memcmp_is_safe/test.compile.pass.cpp b/tests/std/tests/GH_000431_equal_memcmp_is_safe/test.compile.pass.cpp
@@ -12,6 +12,12 @@
 #include <type_traits>
 #include <vector>
 
+#ifdef __clang__
+constexpr bool magic = true;
+#else
+constexpr bool magic = false;
+#endif
+
 using namespace std;
 
 #define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)
@@ -137,6 +143,22 @@ struct StatefulDerived2 : EmptyBase, StatefulBase {};
 
 struct StatefulPrivatelyDerived2 : private EmptyBase, private StatefulBase {};
 
+#if _HAS_CXX20
+struct DefaultComparison {
+    int i;
+
+    bool operator==(const DefaultComparison&) const noexcept = default;
+};
+
+struct DefaultComparisonOddSize {
+    int i;
+    int j;
+    int k;
+
+    bool operator==(const DefaultComparisonOddSize&) const noexcept = default;
+};
+#endif // _HAS_CXX20
+
 #ifdef __cpp_lib_is_pointer_interconvertible
 STATIC_ASSERT(is_pointer_interconvertible_base_of_v<EmptyBase, EmptyDerived>);
 STATIC_ASSERT(is_pointer_interconvertible_base_of_v<EmptyBase, EmptyPrivatelyDerived>);
@@ -485,21 +507,34 @@ STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, void (*)(), void (*)(in
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<is_convertible_v<void (*)(int), void*>, void (*)(int), void*>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<is_convertible_v<void (*)(int), void*>, void*, void (*)(int)>());
 
-// Don't allow member object pointers
-STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int EmptyBase::*, int EmptyBase::*>());
-STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int EmptyDerived::*, int EmptyDerived::*>());
+// Don't allow member object pointers, unless magic happens
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, int EmptyBase::*, int EmptyBase::*>());
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, int EmptyDerived::*, int EmptyDerived::*>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int EmptyBase::*, int EmptyDerived::*>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int EmptyDerived::*, int EmptyBase::*>());
 
-// Don't allow member function pointers
-STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int (EmptyBase::*)(), int (EmptyBase::*)()>());
-STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int (EmptyDerived::*)(), int (EmptyDerived::*)()>());
+// Don't allow member function pointers, unless magic happens
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, int (EmptyBase::*)(), int (EmptyBase::*)()>());
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, int (EmptyDerived::*)(), int (EmptyDerived::*)()>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int (EmptyBase::*)(), int (EmptyDerived::*)()>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, int (EmptyDerived::*)(), int (EmptyBase::*)()>());
 
 // Don't allow user-defined types
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<false, StatefulBase, StatefulBase>());
 
+#if _HAS_CXX20
+// Don't allow user-defined types with default comparison, unless magic happens
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, DefaultComparison, DefaultComparison>());
+STATIC_ASSERT(test_equal_memcmp_is_safe_for_types<magic, DefaultComparisonOddSize, DefaultComparisonOddSize>());
+// The only difference between _Equal_memcmp_is_safe and _Vector_alg_in_search_is_safe is how the magic works
+STATIC_ASSERT(_Equal_memcmp_is_safe<DefaultComparison*, DefaultComparison*, equal_to<>> == magic);
+STATIC_ASSERT(_Equal_memcmp_is_safe<DefaultComparisonOddSize*, DefaultComparisonOddSize*, equal_to<>> == magic);
+#if _USE_STD_VECTOR_ALGORITHMS
+STATIC_ASSERT(_Vector_alg_in_search_is_safe<DefaultComparison*, DefaultComparison*, equal_to<>> == magic);
+STATIC_ASSERT(!_Vector_alg_in_search_is_safe<DefaultComparisonOddSize*, DefaultComparisonOddSize*, equal_to<>>);
+#endif // _USE_STD_VECTOR_ALGORITHMS
+#endif // _HAS_CXX20
+
 // Test _Std_char_traits_eq
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_pred<true, char, char, _Std_char_traits_eq<char>>());
 STATIC_ASSERT(test_equal_memcmp_is_safe_for_pred<true, wchar_t, wchar_t, _Std_char_traits_eq<wchar_t>>());
