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 <cassert>
13#include <cstddef>
14#include <deque>
15#include <forward_list>
16#include <list>
17#include <string>
18#include <vector>
19
20#include <benchmark/benchmark.h>
21#include "../../GenerateInput.h"
22
23int main(int argc, char** argv) {
24 auto std_find_end = [](auto first1, auto last1, auto first2, auto last2) {
25 return std::find_end(first1, last1, first2, last2);
26 };
27 auto std_find_end_pred = [](auto first1, auto last1, auto first2, auto last2) {
28 return std::find_end(first1, last1, first2, last2, [](auto x, auto y) {
29 benchmark::DoNotOptimize(x);
30 benchmark::DoNotOptimize(y);
31 return x == y;
32 });
33 };
34 auto ranges_find_end_pred = [](auto first1, auto last1, auto first2, auto last2) {
35 return std::ranges::find_end(first1, last1, first2, last2, [](auto x, auto y) {
36 benchmark::DoNotOptimize(x);
37 benchmark::DoNotOptimize(y);
38 return x == y;
39 });
40 };
41
42 auto register_benchmarks = [&](auto bm, std::string comment) {
43 // {std,ranges}::find_end(it1, it1, it2, it2)
44 bm.template operator()<std::vector<int>>("std::find_end(vector<int>) (" + comment + ")", std_find_end);
45 bm.template operator()<std::deque<int>>("std::find_end(deque<int>) (" + comment + ")", std_find_end);
46 bm.template operator()<std::list<int>>("std::find_end(list<int>) (" + comment + ")", std_find_end);
47 bm.template operator()<std::forward_list<int>>("std::find_end(forward_list<int>) (" + comment + ")", std_find_end);
48 bm.template operator()<std::vector<int>>("rng::find_end(vector<int>) (" + comment + ")", std::ranges::find_end);
49 bm.template operator()<std::deque<int>>("rng::find_end(deque<int>) (" + comment + ")", std::ranges::find_end);
50 bm.template operator()<std::list<int>>("rng::find_end(list<int>) (" + comment + ")", std::ranges::find_end);
51 bm.template operator()<std::forward_list<int>>(
52 "rng::find_end(forward_list<int>) (" + comment + ")", std::ranges::find_end);
53
54 // {std,ranges}::find_end(it1, it1, it2, it2, pred)
55 bm.template operator()<std::vector<int>>("std::find_end(vector<int>, pred) (" + comment + ")", std_find_end_pred);
56 bm.template operator()<std::deque<int>>("std::find_end(deque<int>, pred) (" + comment + ")", std_find_end_pred);
57 bm.template operator()<std::list<int>>("std::find_end(list<int>, pred) (" + comment + ")", std_find_end_pred);
58 bm.template operator()<std::forward_list<int>>(
59 "std::find_end(forward_list<int>, pred) (" + comment + ")", std_find_end_pred);
60 bm.template operator()<std::vector<int>>(
61 "rng::find_end(vector<int>, pred) (" + comment + ")", ranges_find_end_pred);
62 bm.template operator()<std::deque<int>>("rng::find_end(deque<int>, pred) (" + comment + ")", ranges_find_end_pred);
63 bm.template operator()<std::list<int>>("rng::find_end(list<int>, pred) (" + comment + ")", ranges_find_end_pred);
64 bm.template operator()<std::forward_list<int>>(
65 "rng::find_end(forward_list<int>, pred) (" + comment + ")", ranges_find_end_pred);
66 };
67
68 // Benchmark {std,ranges}::find_end where we never find the needle, which is the
69 // worst case.
70 {
71 auto bm = []<class Container>(std::string name, auto find_end) {
72 benchmark::RegisterBenchmark(
73 name,
74 [find_end](auto& st) {
75 std::size_t const size = st.range(0);
76 using ValueType = typename Container::value_type;
77 ValueType x = Generate<ValueType>::random();
78 ValueType y = random_different_from({x});
79 Container haystack(size, x);
80 std::size_t n = size / 10; // needle size is 10% of the haystack, but we'll never find it
81 assert(n > 0);
82 Container needle(n, y);
83
84 for ([[maybe_unused]] auto _ : st) {
85 benchmark::DoNotOptimize(haystack);
86 benchmark::DoNotOptimize(needle);
87 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());
88 benchmark::DoNotOptimize(result);
89 }
90 })
91 ->Arg(1000) // non power-of-two
92 ->Arg(1024)
93 ->Arg(8192)
94 ->Arg(1 << 20);
95 };
96 register_benchmarks(bm, "process all");
97 }
98
99 // Benchmark {std,ranges}::find_end where we intersperse "near matches" inside the haystack.
100 {
101 auto bm = []<class Container>(std::string name, auto find_end) {
102 benchmark::RegisterBenchmark(
103 name,
104 [find_end](auto& st) {
105 std::size_t const size = st.range(0);
106 using ValueType = typename Container::value_type;
107 ValueType x = Generate<ValueType>::random();
108 ValueType y = random_different_from({x});
109 Container haystack(size, x);
110 std::size_t n = size / 10; // needle size is 10% of the haystack
111 assert(n > 0);
112 Container needle(n, y);
113
114 // intersperse near-matches inside the haystack
115 {
116 auto first = haystack.begin();
117 for (int i = 0; i != 10; ++i) {
118 first = std::copy_n(needle.begin(), n - 1, first);
119 ++first; // this causes the subsequence not to match because it has length n-1
120 }
121 }
122
123 for ([[maybe_unused]] auto _ : st) {
124 benchmark::DoNotOptimize(haystack);
125 benchmark::DoNotOptimize(needle);
126 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());
127 benchmark::DoNotOptimize(result);
128 }
129 })
130 ->Arg(1000) // non power-of-two
131 ->Arg(1024)
132 ->Arg(8192);
133 };
134 register_benchmarks(bm, "near matches");
135 }
136
137 // Special case: the two ranges are the same length (and they are equal, which is the worst case).
138 {
139 auto bm = []<class Container>(std::string name, auto find_end) {
140 benchmark::RegisterBenchmark(
141 name,
142 [find_end](auto& st) {
143 std::size_t const size = st.range(0);
144 using ValueType = typename Container::value_type;
145 ValueType x = Generate<ValueType>::random();
146 Container haystack(size, x);
147 Container needle(size, x);
148
149 for ([[maybe_unused]] auto _ : st) {
150 benchmark::DoNotOptimize(haystack);
151 benchmark::DoNotOptimize(needle);
152 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());
153 benchmark::DoNotOptimize(result);
154 }
155 })
156 ->Arg(1000) // non power-of-two
157 ->Arg(1024)
158 ->Arg(8192);
159 };
160 register_benchmarks(bm, "same length");
161 }
162
163 // Special case: the needle contains a single element (which we never find, i.e. the worst case).
164 {
165 auto bm = []<class Container>(std::string name, auto find_end) {
166 benchmark::RegisterBenchmark(
167 name,
168 [find_end](auto& st) {
169 std::size_t const size = st.range(0);
170 using ValueType = typename Container::value_type;
171 ValueType x = Generate<ValueType>::random();
172 ValueType y = random_different_from({x});
173 Container haystack(size, x);
174 Container needle(1, y);
175
176 for ([[maybe_unused]] auto _ : st) {
177 benchmark::DoNotOptimize(haystack);
178 benchmark::DoNotOptimize(needle);
179 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());
180 benchmark::DoNotOptimize(result);
181 }
182 })
183 ->Arg(1000) // non power-of-two
184 ->Arg(1024)
185 ->Arg(8192);
186 };
187 register_benchmarks(bm, "single element");
188 }
189
190 // Special case: we have a match close to the end of the haystack (ideal case if we start searching from the end).
191 {
192 auto bm = []<class Container>(std::string name, auto find_end) {
193 benchmark::RegisterBenchmark(
194 name,
195 [find_end](auto& st) {
196 std::size_t const size = st.range(0);
197 using ValueType = typename Container::value_type;
198 ValueType x = Generate<ValueType>::random();
199 ValueType y = random_different_from({x});
200 Container haystack(size, x);
201 std::size_t n = size / 10; // needle size is 10% of the haystack
202 assert(n > 0);
203 Container needle(n, y);
204
205 // put the needle at 90% of the haystack
206 std::ranges::copy(needle, std::next(haystack.begin(), (9 * size) / 10));
207
208 for ([[maybe_unused]] auto _ : st) {
209 benchmark::DoNotOptimize(haystack);
210 benchmark::DoNotOptimize(needle);
211 auto result = find_end(haystack.begin(), haystack.end(), needle.begin(), needle.end());
212 benchmark::DoNotOptimize(result);
213 }
214 })
215 ->Arg(1000) // non power-of-two
216 ->Arg(1024)
217 ->Arg(8192);
218 };
219 register_benchmarks(bm, "match near end");
220 }
221
222 benchmark::Initialize(&argc, argv);
223 benchmark::RunSpecifiedBenchmarks();
224 benchmark::Shutdown();
225 return 0;
226}
227

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