[libc++] Vectorize mismatch (#73255)

```
---------------------------------------------------
Benchmark                           old         new
---------------------------------------------------
bm_mismatch<char>/1           0.835 ns      2.37 ns
bm_mismatch<char>/2            1.44 ns      2.60 ns
bm_mismatch<char>/3            2.06 ns      2.83 ns
bm_mismatch<char>/4            2.60 ns      3.29 ns
bm_mismatch<char>/5            3.15 ns      3.77 ns
bm_mismatch<char>/6            3.82 ns      4.17 ns
bm_mismatch<char>/7            4.29 ns      4.52 ns
bm_mismatch<char>/8            4.78 ns      4.86 ns
bm_mismatch<char>/16           9.06 ns      7.54 ns
bm_mismatch<char>/64           31.7 ns      19.1 ns
bm_mismatch<char>/512           249 ns      8.16 ns
bm_mismatch<char>/4096         1956 ns      44.2 ns
bm_mismatch<char>/32768       15498 ns       501 ns
bm_mismatch<char>/262144     123965 ns      4479 ns
bm_mismatch<char>/1048576    495668 ns     21306 ns
bm_mismatch<short>/1          0.710 ns      2.12 ns
bm_mismatch<short>/2           1.03 ns      2.66 ns
bm_mismatch<short>/3           1.29 ns      3.56 ns
bm_mismatch<short>/4           1.68 ns      4.29 ns
bm_mismatch<short>/5           1.96 ns      5.18 ns
bm_mismatch<short>/6           2.59 ns      5.91 ns
bm_mismatch<short>/7           2.86 ns      6.63 ns
bm_mismatch<short>/8           3.19 ns      7.33 ns
bm_mismatch<short>/16          5.48 ns      13.0 ns
bm_mismatch<short>/64          16.6 ns      4.06 ns
bm_mismatch<short>/512          130 ns      13.8 ns
bm_mismatch<short>/4096         985 ns      93.8 ns
bm_mismatch<short>/32768       7846 ns      1002 ns
bm_mismatch<short>/262144     63217 ns     10637 ns
bm_mismatch<short>/1048576   251782 ns     42471 ns
bm_mismatch<int>/1            0.716 ns      1.91 ns
bm_mismatch<int>/2             1.21 ns      2.49 ns
bm_mismatch<int>/3             1.38 ns      3.46 ns
bm_mismatch<int>/4             1.71 ns      4.04 ns
bm_mismatch<int>/5             2.00 ns      4.98 ns
bm_mismatch<int>/6             2.43 ns      5.67 ns
bm_mismatch<int>/7             3.05 ns      6.38 ns
bm_mismatch<int>/8             3.22 ns      7.09 ns
bm_mismatch<int>/16            5.18 ns      12.8 ns
bm_mismatch<int>/64            16.6 ns      5.28 ns
bm_mismatch<int>/512            129 ns      25.2 ns
bm_mismatch<int>/4096          1009 ns       201 ns
bm_mismatch<int>/32768         7776 ns      2144 ns
bm_mismatch<int>/262144       62371 ns     20551 ns
bm_mismatch<int>/1048576     254750 ns     90097 ns
```

2 files changed, 154 insertions, 179 deletions

diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch.pass.cpp
index cc588c0..e7f3994 100644
--- a/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch.pass.cpp
@@ -16,79 +16,173 @@
 // template<InputIterator Iter1, InputIterator Iter2Pred>
 //   constexpr pair<Iter1, Iter2>   // constexpr after c++17
 //   mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2); // C++14
+//
+// template<InputIterator Iter1, InputIterator Iter2,
+//          Predicate<auto, Iter1::value_type, Iter2::value_type> Pred>
+//   requires CopyConstructible<Pred>
+//   constexpr pair<Iter1, Iter2>   // constexpr after c++17
+//   mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Pred pred);
+//
+// template<InputIterator Iter1, InputIterator Iter2, Predicate Pred>
+//   constexpr pair<Iter1, Iter2>   // constexpr after c++17
+//   mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Pred pred); // C++14
+
+// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=50000000
+// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=100000000
 
 #include <algorithm>
+#include <array>
 #include <cassert>
+#include <vector>
 
 #include "test_macros.h"
 #include "test_iterators.h"
-
-#if TEST_STD_VER > 17
-TEST_CONSTEXPR bool test_constexpr() {
-    int ia[] = {1, 3, 6, 7};
-    int ib[] = {1, 3};
-    int ic[] = {1, 3, 5, 7};
-    typedef cpp17_input_iterator<int*>         II;
-    typedef bidirectional_iterator<int*> BI;
-
-    auto p1 = std::mismatch(std::begin(ia), std::end(ia), std::begin(ic));
-    if (p1.first != ia+2 || p1.second != ic+2)
-        return false;
-
-    auto p2 = std::mismatch(std::begin(ia), std::end(ia), std::begin(ic), std::end(ic));
-    if (p2.first != ia+2 || p2.second != ic+2)
-        return false;
-
-    auto p3 = std::mismatch(std::begin(ib), std::end(ib), std::begin(ic));
-    if (p3.first != ib+2 || p3.second != ic+2)
-        return false;
-
-    auto p4 = std::mismatch(std::begin(ib), std::end(ib), std::begin(ic), std::end(ic));
-    if (p4.first != ib+2 || p4.second != ic+2)
-        return false;
-
-    auto p5 = std::mismatch(II(std::begin(ib)), II(std::end(ib)), II(std::begin(ic)));
-    if (p5.first != II(ib+2) || p5.second != II(ic+2))
-        return false;
-    auto p6 = std::mismatch(BI(std::begin(ib)), BI(std::end(ib)), BI(std::begin(ic)), BI(std::end(ic)));
-    if (p6.first != BI(ib+2) || p6.second != BI(ic+2))
-        return false;
-
-    return true;
-    }
+#include "type_algorithms.h"
+
+template <class Iter, class Container1, class Container2>
+TEST_CONSTEXPR_CXX20 void check(Container1 lhs, Container2 rhs, size_t offset) {
+  if (lhs.size() == rhs.size()) {
+    assert(std::mismatch(Iter(lhs.data()), Iter(lhs.data() + lhs.size()), Iter(rhs.data())) ==
+           std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset)));
+
+    assert(std::mismatch(Iter(lhs.data()),
+                         Iter(lhs.data() + lhs.size()),
+                         Iter(rhs.data()),
+                         std::equal_to<typename Container1::value_type>()) ==
+           std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset)));
+  }
+
+#if TEST_STD_VER >= 14
+  assert(
+      std::mismatch(Iter(lhs.data()), Iter(lhs.data() + lhs.size()), Iter(rhs.data()), Iter(rhs.data() + rhs.size())) ==
+      std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset)));
+
+  assert(std::mismatch(Iter(lhs.data()),
+                       Iter(lhs.data() + lhs.size()),
+                       Iter(rhs.data()),
+                       Iter(rhs.data() + rhs.size()),
+                       std::equal_to<typename Container1::value_type>()) ==
+         std::make_pair(Iter(lhs.data() + offset), Iter(rhs.data() + offset)));
 #endif
+}
 
-int main(int, char**)
-{
-    int ia[] = {0, 1, 2, 2, 0, 1, 2, 3};
-    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
-    int ib[] = {0, 1, 2, 3, 0, 1, 2, 3};
-    const unsigned sb = sizeof(ib)/sizeof(ib[0]); ((void)sb); // unused in C++11
-
-    typedef cpp17_input_iterator<const int*> II;
-    typedef random_access_iterator<const int*>  RAI;
-
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib))
-            == (std::pair<II, II>(II(ia+3), II(ib+3))));
-
-    assert(std::mismatch(RAI(ia), RAI(ia + sa), RAI(ib))
-            == (std::pair<RAI, RAI>(RAI(ia+3), RAI(ib+3))));
-
-#if TEST_STD_VER > 11 // We have the four iteration version
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib), II(ib+sb))
-            == (std::pair<II, II>(II(ia+3), II(ib+3))));
+struct NonTrivial {
+  int i_;
+
+  TEST_CONSTEXPR_CXX20 NonTrivial(int i) : i_(i) {}
+  TEST_CONSTEXPR_CXX20 NonTrivial(NonTrivial&& other) : i_(other.i_) { other.i_ = 0; }
+
+  TEST_CONSTEXPR_CXX20 friend bool operator==(const NonTrivial& lhs, const NonTrivial& rhs) { return lhs.i_ == rhs.i_; }
+};
+
+struct ModTwoComp {
+  TEST_CONSTEXPR_CXX20 bool operator()(int lhs, int rhs) { return lhs % 2 == rhs % 2; }
+};
+
+template <class Iter>
+TEST_CONSTEXPR_CXX20 bool test() {
+  { // empty ranges
+    std::array<int, 0> lhs = {};
+    std::array<int, 0> rhs = {};
+    check<Iter>(lhs, rhs, 0);
+  }
+
+  { // same range without mismatch
+    std::array<int, 8> lhs = {0, 1, 2, 3, 0, 1, 2, 3};
+    std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3};
+    check<Iter>(lhs, rhs, 8);
+  }
+
+  { // same range with mismatch
+    std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3};
+    std::array<int, 8> rhs = {0, 1, 2, 3, 0, 1, 2, 3};
+    check<Iter>(lhs, rhs, 3);
+  }
+
+  { // second range is smaller
+    std::array<int, 8> lhs = {0, 1, 2, 2, 0, 1, 2, 3};
+    std::array<int, 2> rhs = {0, 1};
+    check<Iter>(lhs, rhs, 2);
+  }
+
+  { // first range is smaller
+    std::array<int, 2> lhs = {0, 1};
+    std::array<int, 8> rhs = {0, 1, 2, 2, 0, 1, 2, 3};
+    check<Iter>(lhs, rhs, 2);
+  }
+
+  { // use a custom comparator
+    std::array<int, 4> lhs = {0, 2, 3, 4};
+    std::array<int, 4> rhs = {0, 0, 4, 4};
+    assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), ModTwoComp()) ==
+           std::make_pair(lhs.data() + 2, rhs.data() + 2));
+#if TEST_STD_VER >= 14
+    assert(std::mismatch(lhs.data(), lhs.data() + lhs.size(), rhs.data(), rhs.data() + rhs.size(), ModTwoComp()) ==
+           std::make_pair(lhs.data() + 2, rhs.data() + 2));
+#endif
+  }
 
-    assert(std::mismatch(RAI(ia), RAI(ia + sa), RAI(ib), RAI(ib+sb))
-            == (std::pair<RAI, RAI>(RAI(ia+3), RAI(ib+3))));
+  return true;
+}
 
+struct Test {
+  template <class Iter>
+  TEST_CONSTEXPR_CXX20 void operator()() {
+    test<Iter>();
+  }
+};
+
+TEST_CONSTEXPR_CXX20 bool test() {
+  types::for_each(types::cpp17_input_iterator_list<int*>(), Test());
+
+  { // use a non-integer type to also test the general case - all elements match
+    std::array<NonTrivial, 8> lhs = {1, 2, 3, 4, 5, 6, 7, 8};
+    std::array<NonTrivial, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8};
+    check<NonTrivial*>(std::move(lhs), std::move(rhs), 8);
+  }
+
+  { // use a non-integer type to also test the general case - not all elements match
+    std::array<NonTrivial, 8> lhs = {1, 2, 3, 4, 7, 6, 7, 8};
+    std::array<NonTrivial, 8> rhs = {1, 2, 3, 4, 5, 6, 7, 8};
+    check<NonTrivial*>(std::move(lhs), std::move(rhs), 4);
+  }
+
+  return true;
+}
 
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib), II(ib+2))
-            == (std::pair<II, II>(II(ia+2), II(ib+2))));
+int main(int, char**) {
+  test();
+#if TEST_STD_VER >= 20
+  static_assert(test());
 #endif
 
-#if TEST_STD_VER > 17
-    static_assert(test_constexpr());
-#endif
+  { // check with a lot of elements to test the vectorization optimization
+    {
+      std::vector<char> lhs(256);
+      std::vector<char> rhs(256);
+      for (size_t i = 0; i != lhs.size(); ++i) {
+        lhs[i] = 1;
+        check<char*>(lhs, rhs, i);
+        lhs[i] = 0;
+        rhs[i] = 1;
+        check<char*>(lhs, rhs, i);
+        rhs[i] = 0;
+      }
+    }
+
+    {
+      std::vector<int> lhs(256);
+      std::vector<int> rhs(256);
+      for (size_t i = 0; i != lhs.size(); ++i) {
+        lhs[i] = 1;
+        check<int*>(lhs, rhs, i);
+        lhs[i] = 0;
+        rhs[i] = 1;
+        check<int*>(lhs, rhs, i);
+        rhs[i] = 0;
+      }
+    }
+  }
 
   return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch_pred.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch_pred.pass.cpp
deleted file mode 100644
index bda4ec7..0000000
--- a/libcxx/test/std/algorithms/alg.nonmodifying/mismatch/mismatch_pred.pass.cpp
+++ /dev/null
@@ -1,119 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-// <algorithm>
-
-// template<InputIterator Iter1, InputIterator Iter2,
-//          Predicate<auto, Iter1::value_type, Iter2::value_type> Pred>
-//   requires CopyConstructible<Pred>
-//   constexpr pair<Iter1, Iter2>   // constexpr after c++17
-//   mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Pred pred);
-//
-// template<InputIterator Iter1, InputIterator Iter2, Predicate Pred>
-//   constexpr pair<Iter1, Iter2>   // constexpr after c++17
-//   mismatch(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Pred pred); // C++14
-
-#include <algorithm>
-#include <functional>
-#include <cassert>
-
-#include "test_macros.h"
-#include "test_iterators.h"
-#include "counting_predicates.h"
-
-#if TEST_STD_VER > 17
-TEST_CONSTEXPR bool eq(int a, int b) { return a == b; }
-
-TEST_CONSTEXPR bool test_constexpr() {
-    int ia[] = {1, 3, 6, 7};
-    int ib[] = {1, 3};
-    int ic[] = {1, 3, 5, 7};
-    typedef cpp17_input_iterator<int*>         II;
-    typedef bidirectional_iterator<int*> BI;
-
-    auto p1 = std::mismatch(std::begin(ia), std::end(ia), std::begin(ic), eq);
-    if (p1.first != ia+2 || p1.second != ic+2)
-        return false;
-
-    auto p2 = std::mismatch(std::begin(ia), std::end(ia), std::begin(ic), std::end(ic), eq);
-    if (p2.first != ia+2 || p2.second != ic+2)
-        return false;
-
-    auto p3 = std::mismatch(std::begin(ib), std::end(ib), std::begin(ic), eq);
-    if (p3.first != ib+2 || p3.second != ic+2)
-        return false;
-
-    auto p4 = std::mismatch(std::begin(ib), std::end(ib), std::begin(ic), std::end(ic), eq);
-    if (p4.first != ib+2 || p4.second != ic+2)
-        return false;
-
-    auto p5 = std::mismatch(II(std::begin(ib)), II(std::end(ib)), II(std::begin(ic)), eq);
-    if (p5.first != II(ib+2) || p5.second != II(ic+2))
-        return false;
-    auto p6 = std::mismatch(BI(std::begin(ib)), BI(std::end(ib)), BI(std::begin(ic)), BI(std::end(ic)), eq);
-    if (p6.first != BI(ib+2) || p6.second != BI(ic+2))
-        return false;
-
-    return true;
-    }
-#endif
-
-
-#if TEST_STD_VER > 11
-#define HAS_FOUR_ITERATOR_VERSION
-#endif
-
-int main(int, char**)
-{
-    int ia[] = {0, 1, 2, 2, 0, 1, 2, 3};
-    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
-    int ib[] = {0, 1, 2, 3, 0, 1, 2, 3};
-    const unsigned sb = sizeof(ib)/sizeof(ib[0]); ((void)sb); // unused in C++11
-
-    typedef cpp17_input_iterator<const int*> II;
-    typedef random_access_iterator<const int*>  RAI;
-    typedef std::equal_to<int> EQ;
-
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib), EQ())
-            == (std::pair<II, II>(II(ia+3), II(ib+3))));
-    assert(std::mismatch(RAI(ia), RAI(ia + sa), RAI(ib), EQ())
-            == (std::pair<RAI, RAI>(RAI(ia+3), RAI(ib+3))));
-
-    binary_counting_predicate<EQ, int> bcp((EQ()));
-    assert(std::mismatch(RAI(ia), RAI(ia + sa), RAI(ib), std::ref(bcp))
-            == (std::pair<RAI, RAI>(RAI(ia+3), RAI(ib+3))));
-    assert(bcp.count() > 0 && bcp.count() < sa);
-    bcp.reset();
-
-#if TEST_STD_VER >= 14
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib), II(ib + sb), EQ())
-            == (std::pair<II, II>(II(ia+3), II(ib+3))));
-    assert(std::mismatch(RAI(ia), RAI(ia + sa), RAI(ib), RAI(ib + sb), EQ())
-            == (std::pair<RAI, RAI>(RAI(ia+3), RAI(ib+3))));
-
-    assert(std::mismatch(II(ia), II(ia + sa), II(ib), II(ib + sb), std::ref(bcp))
-            == (std::pair<II, II>(II(ia+3), II(ib+3))));
-    assert(bcp.count() > 0 && bcp.count() < std::min(sa, sb));
-#endif
-
-    assert(std::mismatch(ia, ia + sa, ib, EQ()) ==
-           (std::pair<int*,int*>(ia+3,ib+3)));
-
-#if TEST_STD_VER >= 14
-    assert(std::mismatch(ia, ia + sa, ib, ib + sb, EQ()) ==
-           (std::pair<int*,int*>(ia+3,ib+3)));
-    assert(std::mismatch(ia, ia + sa, ib, ib + 2, EQ()) ==
-           (std::pair<int*,int*>(ia+2,ib+2)));
-#endif
-
-#if TEST_STD_VER > 17
-    static_assert(test_constexpr());
-#endif
-
-  return 0;
-}