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_find = [](auto first, auto last, auto const& value) { return std::find(first, last, value); };
23 auto std_find_if = [](auto first, auto last, auto const& value) {
24 return std::find_if(first, last, [&](auto element) {
25 benchmark::DoNotOptimize(element);
26 return element == value;
27 });
28 };
29 auto std_find_if_not = [](auto first, auto last, auto const& value) {
30 return std::find_if_not(first, last, [&](auto element) {
31 benchmark::DoNotOptimize(element);
32 return element != value;
33 });
34 };
35
36 auto ranges_find = [](auto first, auto last, auto const& value) { return std::ranges::find(first, last, value); };
37 auto ranges_find_if = [](auto first, auto last, auto const& value) {
38 return std::ranges::find_if(first, last, [&](auto element) {
39 benchmark::DoNotOptimize(element);
40 return element == value;
41 });
42 };
43 auto ranges_find_if_not = [](auto first, auto last, auto const& value) {
44 return std::ranges::find_if_not(first, last, [&](auto element) {
45 benchmark::DoNotOptimize(element);
46 return element != value;
47 });
48 };
49
50 auto register_benchmarks = [&](auto bm, std::string comment) {
51 // find
52 bm.template operator()<std::vector<char>>("std::find(vector<char>) (" + comment + ")", std_find);
53 bm.template operator()<std::vector<int>>("std::find(vector<int>) (" + comment + ")", std_find);
54 bm.template operator()<std::deque<int>>("std::find(deque<int>) (" + comment + ")", std_find);
55 bm.template operator()<std::list<int>>("std::find(list<int>) (" + comment + ")", std_find);
56
57 bm.template operator()<std::vector<char>>("rng::find(vector<char>) (" + comment + ")", ranges_find);
58 bm.template operator()<std::vector<int>>("rng::find(vector<int>) (" + comment + ")", ranges_find);
59 bm.template operator()<std::deque<int>>("rng::find(deque<int>) (" + comment + ")", ranges_find);
60 bm.template operator()<std::list<int>>("rng::find(list<int>) (" + comment + ")", ranges_find);
61
62 // find_if
63 bm.template operator()<std::vector<char>>("std::find_if(vector<char>) (" + comment + ")", std_find_if);
64 bm.template operator()<std::vector<int>>("std::find_if(vector<int>) (" + comment + ")", std_find_if);
65 bm.template operator()<std::deque<int>>("std::find_if(deque<int>) (" + comment + ")", std_find_if);
66 bm.template operator()<std::list<int>>("std::find_if(list<int>) (" + comment + ")", std_find_if);
67
68 bm.template operator()<std::vector<char>>("rng::find_if(vector<char>) (" + comment + ")", ranges_find_if);
69 bm.template operator()<std::vector<int>>("rng::find_if(vector<int>) (" + comment + ")", ranges_find_if);
70 bm.template operator()<std::deque<int>>("rng::find_if(deque<int>) (" + comment + ")", ranges_find_if);
71 bm.template operator()<std::list<int>>("rng::find_if(list<int>) (" + comment + ")", ranges_find_if);
72
73 // find_if_not
74 bm.template operator()<std::vector<char>>("std::find_if_not(vector<char>) (" + comment + ")", std_find_if_not);
75 bm.template operator()<std::vector<int>>("std::find_if_not(vector<int>) (" + comment + ")", std_find_if_not);
76 bm.template operator()<std::deque<int>>("std::find_if_not(deque<int>) (" + comment + ")", std_find_if_not);
77 bm.template operator()<std::list<int>>("std::find_if_not(list<int>) (" + comment + ")", std_find_if_not);
78
79 bm.template operator()<std::vector<char>>("rng::find_if_not(vector<char>) (" + comment + ")", ranges_find_if_not);
80 bm.template operator()<std::vector<int>>("rng::find_if_not(vector<int>) (" + comment + ")", ranges_find_if_not);
81 bm.template operator()<std::deque<int>>("rng::find_if_not(deque<int>) (" + comment + ")", ranges_find_if_not);
82 bm.template operator()<std::list<int>>("rng::find_if_not(list<int>) (" + comment + ")", ranges_find_if_not);
83 };
84
85 // Benchmark {std,ranges}::{find,find_if,find_if_not}(normal container) where we
86 // bail out after 25% of elements
87 {
88 auto bm = []<class Container>(std::string name, auto find) {
89 benchmark::RegisterBenchmark(
90 name,
91 [find](auto& st) {
92 std::size_t const size = st.range(0);
93 using ValueType = typename Container::value_type;
94 ValueType x = Generate<ValueType>::random();
95 ValueType y = random_different_from({x});
96 Container c(size, x);
97
98 // put the element we're searching for at 25% of the sequence
99 *std::next(c.begin(), size / 4) = y;
100
101 for ([[maybe_unused]] auto _ : st) {
102 benchmark::DoNotOptimize(c);
103 benchmark::DoNotOptimize(y);
104 auto result = find(c.begin(), c.end(), y);
105 benchmark::DoNotOptimize(result);
106 }
107 })
108 ->Arg(8)
109 ->Arg(1024)
110 ->Arg(8192)
111 ->Arg(1 << 15);
112 };
113 register_benchmarks(bm, "bail 25%");
114 }
115
116 // Benchmark {std,ranges}::{find,find_if,find_if_not}(normal container) where we process the whole sequence
117 {
118 auto bm = []<class Container>(std::string name, auto find) {
119 benchmark::RegisterBenchmark(
120 name,
121 [find](auto& st) {
122 std::size_t const size = st.range(0);
123 using ValueType = typename Container::value_type;
124 ValueType x = Generate<ValueType>::random();
125 ValueType y = random_different_from({x});
126 Container c(size, x);
127
128 for ([[maybe_unused]] auto _ : st) {
129 benchmark::DoNotOptimize(c);
130 benchmark::DoNotOptimize(y);
131 auto result = find(c.begin(), c.end(), y);
132 benchmark::DoNotOptimize(result);
133 }
134 })
135 ->Arg(8)
136 ->Arg(50) // non power-of-two
137 ->Arg(1024)
138 ->Arg(8192)
139 ->Arg(1 << 15);
140 };
141 register_benchmarks(bm, "process all");
142 }
143
144 // Benchmark {std,ranges}::{find,find_if,find_if_not}(vector<bool>) where we process the whole sequence
145 {
146 auto bm = [](std::string name, auto find) {
147 benchmark::RegisterBenchmark(
148 name,
149 [find](auto& st) {
150 std::size_t const size = st.range(0);
151 std::vector<bool> c(size, true);
152 bool y = false;
153
154 for ([[maybe_unused]] auto _ : st) {
155 benchmark::DoNotOptimize(c);
156 benchmark::DoNotOptimize(y);
157 auto result = find(c.begin(), c.end(), y);
158 benchmark::DoNotOptimize(result);
159 }
160 })
161 ->Arg(8)
162 ->Arg(50) // non power-of-two
163 ->Arg(1024)
164 ->Arg(8192)
165 ->Arg(1 << 20);
166 };
167 bm("std::find(vector<bool>) (process all)", std_find);
168 bm("rng::find(vector<bool>) (process all)", ranges_find);
169
170 bm("std::find_if(vector<bool>) (process all)", std_find_if);
171 bm("rng::find_if(vector<bool>) (process all)", ranges_find_if);
172
173 bm("std::find_if_not(vector<bool>) (process all)", std_find_if_not);
174 bm("rng::find_if_not(vector<bool>) (process all)", ranges_find_if_not);
175 }
176
177 benchmark::Initialize(&argc, argv);
178 benchmark::RunSpecifiedBenchmarks();
179 benchmark::Shutdown();
180 return 0;
181}
182

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