1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11#include <algorithm>
12#include <cstddef>
13#include <deque>
14#include <list>
15#include <string>
16#include <vector>
17
18#include <benchmark/benchmark.h>
19#include "../../GenerateInput.h"
20
21int main(int argc, char** argv) {
22 auto std_mismatch_3leg = [](auto first1, auto last1, auto first2, auto) {
23 return std::mismatch(first1, last1, first2);
24 };
25 auto std_mismatch_4leg = [](auto first1, auto last1, auto first2, auto last2) {
26 return std::mismatch(first1, last1, first2, last2);
27 };
28 auto std_mismatch_3leg_pred = [](auto first1, auto last1, auto first2, auto) {
29 return std::mismatch(first1, last1, first2, [](auto x, auto y) {
30 benchmark::DoNotOptimize(x);
31 benchmark::DoNotOptimize(y);
32 return x == y;
33 });
34 };
35 auto std_mismatch_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {
36 return std::mismatch(first1, last1, first2, last2, [](auto x, auto y) {
37 benchmark::DoNotOptimize(x);
38 benchmark::DoNotOptimize(y);
39 return x == y;
40 });
41 };
42 auto ranges_mismatch_4leg_pred = [](auto first1, auto last1, auto first2, auto last2) {
43 return std::ranges::mismatch(first1, last1, first2, last2, [](auto x, auto y) {
44 benchmark::DoNotOptimize(x);
45 benchmark::DoNotOptimize(y);
46 return x == y;
47 });
48 };
49
50 // Benchmark {std,ranges}::mismatch where we find the mismatching element at the very end (worst case).
51 //
52 // TODO: Look into benchmarking aligned and unaligned memory explicitly
53 // (currently things happen to be aligned because they are malloced that way)
54 {
55 auto bm = []<class Container>(std::string name, auto mismatch) {
56 benchmark::RegisterBenchmark(
57 name,
58 [mismatch](auto& st) {
59 std::size_t const size = st.range(0);
60 using ValueType = typename Container::value_type;
61 ValueType x = Generate<ValueType>::random();
62 ValueType y = random_different_from({x});
63 Container c1(size, x);
64 Container c2(size, x);
65 c2.back() = y;
66
67 for ([[maybe_unused]] auto _ : st) {
68 benchmark::DoNotOptimize(c1);
69 benchmark::DoNotOptimize(c2);
70 auto result = mismatch(c1.begin(), c1.end(), c2.begin(), c2.end());
71 benchmark::DoNotOptimize(result);
72 }
73 })
74 ->Arg(8)
75 ->Arg(1000) // non power-of-two
76 ->Arg(1024)
77 ->Arg(8192)
78 ->Arg(1 << 20);
79 };
80
81 // std::mismatch(it, it, it)
82 bm.operator()<std::vector<int>>(name: "std::mismatch(vector<int>) (it, it, it)", mismatch: std_mismatch_3leg);
83 bm.operator()<std::deque<int>>(name: "std::mismatch(deque<int>) (it, it, it)", mismatch: std_mismatch_3leg);
84 bm.operator()<std::list<int>>(name: "std::mismatch(list<int>) (it, it, it)", mismatch: std_mismatch_3leg);
85
86 // std::mismatch(it, it, it, pred)
87 bm.operator()<std::vector<int>>(name: "std::mismatch(vector<int>) (it, it, it, pred)", mismatch: std_mismatch_3leg_pred);
88 bm.operator()<std::deque<int>>(name: "std::mismatch(deque<int>) (it, it, it, pred)", mismatch: std_mismatch_3leg_pred);
89 bm.operator()<std::list<int>>(name: "std::mismatch(list<int>) (it, it, it, pred)", mismatch: std_mismatch_3leg_pred);
90
91 // {std,ranges}::mismatch(it, it, it, it)
92 bm.operator()<std::vector<int>>(name: "std::mismatch(vector<int>) (it, it, it, it)", mismatch: std_mismatch_4leg);
93 bm.operator()<std::deque<int>>(name: "std::mismatch(deque<int>) (it, it, it, it)", mismatch: std_mismatch_4leg);
94 bm.operator()<std::list<int>>(name: "std::mismatch(list<int>) (it, it, it, it)", mismatch: std_mismatch_4leg);
95 bm.operator()<std::vector<int>>("rng::mismatch(vector<int>) (it, it, it, it)", std::ranges::mismatch);
96 bm.operator()<std::deque<int>>("rng::mismatch(deque<int>) (it, it, it, it)", std::ranges::mismatch);
97 bm.operator()<std::list<int>>("rng::mismatch(list<int>) (it, it, it, it)", std::ranges::mismatch);
98
99 // {std,ranges}::mismatch(it, it, it, it, pred)
100 bm.operator()<std::vector<int>>(name: "std::mismatch(vector<int>) (it, it, it, it, pred)", mismatch: std_mismatch_4leg_pred);
101 bm.operator()<std::deque<int>>(name: "std::mismatch(deque<int>) (it, it, it, it, pred)", mismatch: std_mismatch_4leg_pred);
102 bm.operator()<std::list<int>>(name: "std::mismatch(list<int>) (it, it, it, it, pred)", mismatch: std_mismatch_4leg_pred);
103 bm.operator()<std::vector<int>>(name: "rng::mismatch(vector<int>) (it, it, it, it, pred)", mismatch: ranges_mismatch_4leg_pred);
104 bm.operator()<std::deque<int>>(name: "rng::mismatch(deque<int>) (it, it, it, it, pred)", mismatch: ranges_mismatch_4leg_pred);
105 bm.operator()<std::list<int>>(name: "rng::mismatch(list<int>) (it, it, it, it, pred)", mismatch: ranges_mismatch_4leg_pred);
106 }
107
108 benchmark::Initialize(&argc, argv);
109 benchmark::RunSpecifiedBenchmarks();
110 benchmark::Shutdown();
111 return 0;
112}
113

source code of libcxx/test/benchmarks/algorithms/nonmodifying/mismatch.bench.cpp