1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef BENCHMARK_CONTAINER_BENCHMARKS_H
11 #define BENCHMARK_CONTAINER_BENCHMARKS_H
12
13 #include <cassert>
14
15 #include "Utilities.h"
16 #include "benchmark/benchmark.h"
17
18 namespace ContainerBenchmarks {
19
20 template <class Container>
BM_ConstructSize(benchmark::State & st,Container)21 void BM_ConstructSize(benchmark::State& st, Container) {
22 auto size = st.range(0);
23 for (auto _ : st) {
24 Container c(size);
25 DoNotOptimizeData(c);
26 }
27 }
28
29 template <class Container>
BM_CopyConstruct(benchmark::State & st,Container)30 void BM_CopyConstruct(benchmark::State& st, Container) {
31 auto size = st.range(0);
32 Container c(size);
33 for (auto _ : st) {
34 auto v = c;
35 DoNotOptimizeData(v);
36 }
37 }
38
39 template <class Container>
BM_Assignment(benchmark::State & st,Container)40 void BM_Assignment(benchmark::State& st, Container) {
41 auto size = st.range(0);
42 Container c1;
43 Container c2(size);
44 for (auto _ : st) {
45 c1 = c2;
46 DoNotOptimizeData(c1);
47 DoNotOptimizeData(c2);
48 }
49 }
50
51 template <class Container>
BM_ConstructSizeValue(benchmark::State & st,Container,typename Container::value_type const & val)52 void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
53 const auto size = st.range(0);
54 for (auto _ : st) {
55 Container c(size, val);
56 DoNotOptimizeData(c);
57 }
58 }
59
60 template <class Container, class GenInputs>
BM_ConstructIterIter(benchmark::State & st,Container,GenInputs gen)61 void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
62 auto in = gen(st.range(0));
63 const auto begin = in.begin();
64 const auto end = in.end();
65 benchmark::DoNotOptimize(&in);
66 while (st.KeepRunning()) {
67 Container c(begin, end);
68 DoNotOptimizeData(c);
69 }
70 }
71
72 template <class Container, class GenInputs>
BM_ConstructFromRange(benchmark::State & st,Container,GenInputs gen)73 void BM_ConstructFromRange(benchmark::State& st, Container, GenInputs gen) {
74 auto in = gen(st.range(0));
75 benchmark::DoNotOptimize(&in);
76 while (st.KeepRunning()) {
77 Container c(std::from_range, in);
78 DoNotOptimizeData(c);
79 }
80 }
81
82 template <class Container>
BM_Pushback_no_grow(benchmark::State & state,Container c)83 void BM_Pushback_no_grow(benchmark::State& state, Container c) {
84 int count = state.range(0);
85 c.reserve(count);
86 while (state.KeepRunningBatch(count)) {
87 c.clear();
88 for (int i = 0; i != count; ++i) {
89 c.push_back(i);
90 }
91 benchmark::DoNotOptimize(c.data());
92 }
93 }
94
95 template <class Container, class GenInputs>
BM_InsertValue(benchmark::State & st,Container c,GenInputs gen)96 void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
97 auto in = gen(st.range(0));
98 const auto end = in.end();
99 while (st.KeepRunning()) {
100 c.clear();
101 for (auto it = in.begin(); it != end; ++it) {
102 benchmark::DoNotOptimize(&(*c.insert(*it).first));
103 }
104 benchmark::ClobberMemory();
105 }
106 }
107
108 template <class Container, class GenInputs>
BM_InsertValueRehash(benchmark::State & st,Container c,GenInputs gen)109 void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
110 auto in = gen(st.range(0));
111 const auto end = in.end();
112 while (st.KeepRunning()) {
113 c.clear();
114 c.rehash(16);
115 for (auto it = in.begin(); it != end; ++it) {
116 benchmark::DoNotOptimize(&(*c.insert(*it).first));
117 }
118 benchmark::ClobberMemory();
119 }
120 }
121
122 template <class Container, class GenInputs>
BM_InsertDuplicate(benchmark::State & st,Container c,GenInputs gen)123 void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
124 auto in = gen(st.range(0));
125 const auto end = in.end();
126 c.insert(in.begin(), in.end());
127 benchmark::DoNotOptimize(&c);
128 benchmark::DoNotOptimize(&in);
129 while (st.KeepRunning()) {
130 for (auto it = in.begin(); it != end; ++it) {
131 benchmark::DoNotOptimize(&(*c.insert(*it).first));
132 }
133 benchmark::ClobberMemory();
134 }
135 }
136
137 template <class Container, class GenInputs>
BM_EmplaceDuplicate(benchmark::State & st,Container c,GenInputs gen)138 void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
139 auto in = gen(st.range(0));
140 const auto end = in.end();
141 c.insert(in.begin(), in.end());
142 benchmark::DoNotOptimize(&c);
143 benchmark::DoNotOptimize(&in);
144 while (st.KeepRunning()) {
145 for (auto it = in.begin(); it != end; ++it) {
146 benchmark::DoNotOptimize(&(*c.emplace(*it).first));
147 }
148 benchmark::ClobberMemory();
149 }
150 }
151
152 template <class Container, class GenInputs>
BM_Find(benchmark::State & st,Container c,GenInputs gen)153 static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
154 auto in = gen(st.range(0));
155 c.insert(in.begin(), in.end());
156 benchmark::DoNotOptimize(&(*c.begin()));
157 const auto end = in.data() + in.size();
158 while (st.KeepRunning()) {
159 for (auto it = in.data(); it != end; ++it) {
160 benchmark::DoNotOptimize(&(*c.find(*it)));
161 }
162 benchmark::ClobberMemory();
163 }
164 }
165
166 template <class Container, class GenInputs>
BM_FindRehash(benchmark::State & st,Container c,GenInputs gen)167 static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
168 c.rehash(8);
169 auto in = gen(st.range(0));
170 c.insert(in.begin(), in.end());
171 benchmark::DoNotOptimize(&(*c.begin()));
172 const auto end = in.data() + in.size();
173 while (st.KeepRunning()) {
174 for (auto it = in.data(); it != end; ++it) {
175 benchmark::DoNotOptimize(&(*c.find(*it)));
176 }
177 benchmark::ClobberMemory();
178 }
179 }
180
181 template <class Container, class GenInputs>
BM_Rehash(benchmark::State & st,Container c,GenInputs gen)182 static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
183 auto in = gen(st.range(0));
184 c.max_load_factor(3.0);
185 c.insert(in.begin(), in.end());
186 benchmark::DoNotOptimize(c);
187 const auto bucket_count = c.bucket_count();
188 while (st.KeepRunning()) {
189 c.rehash(bucket_count + 1);
190 c.rehash(bucket_count);
191 benchmark::ClobberMemory();
192 }
193 }
194
195 template <class Container, class GenInputs>
BM_Compare_same_container(benchmark::State & st,Container,GenInputs gen)196 static void BM_Compare_same_container(benchmark::State& st, Container, GenInputs gen) {
197 auto in = gen(st.range(0));
198 Container c1(in.begin(), in.end());
199 Container c2 = c1;
200
201 benchmark::DoNotOptimize(&(*c1.begin()));
202 benchmark::DoNotOptimize(&(*c2.begin()));
203 while (st.KeepRunning()) {
204 bool res = c1 == c2;
205 benchmark::DoNotOptimize(&res);
206 benchmark::ClobberMemory();
207 }
208 }
209
210 template <class Container, class GenInputs>
BM_Compare_different_containers(benchmark::State & st,Container,GenInputs gen)211 static void BM_Compare_different_containers(benchmark::State& st, Container, GenInputs gen) {
212 auto in1 = gen(st.range(0));
213 auto in2 = gen(st.range(0));
214 Container c1(in1.begin(), in1.end());
215 Container c2(in2.begin(), in2.end());
216
217 benchmark::DoNotOptimize(&(*c1.begin()));
218 benchmark::DoNotOptimize(&(*c2.begin()));
219 while (st.KeepRunning()) {
220 bool res = c1 == c2;
221 benchmark::DoNotOptimize(&res);
222 benchmark::ClobberMemory();
223 }
224 }
225
226 } // end namespace ContainerBenchmarks
227
228 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H
229