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 TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H
11#define TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H
12
13#include <algorithm>
14#include <cassert>
15#include <cstddef>
16#include <iterator>
17#include <ranges> // for std::from_range
18#include <string>
19#include <type_traits>
20#include <vector>
21
22#include "benchmark/benchmark.h"
23#include "test_iterators.h"
24#include "../../GenerateInput.h"
25
26namespace support {
27
28template <class Container>
29void DoNotOptimizeData(Container& c) {
30 if constexpr (requires { c.data(); }) {
31 benchmark::DoNotOptimize(c.data());
32 } else {
33 benchmark::DoNotOptimize(&c);
34 }
35}
36
37template <class Container>
38void sequence_container_benchmarks(std::string container) {
39 using ValueType = typename Container::value_type;
40
41 using Generator = ValueType (*)();
42 Generator cheap = [] { return Generate<ValueType>::cheap(); };
43 Generator expensive = [] { return Generate<ValueType>::expensive(); };
44 auto tostr = [&](Generator gen) -> std::string {
45 return gen == cheap ? " (cheap elements)" : " (expensive elements)";
46 };
47 std::vector<Generator> generators;
48 generators.push_back(cheap);
49 if constexpr (!std::is_integral_v<ValueType>) {
50 generators.push_back(expensive);
51 }
52
53 // Some of these benchmarks are structured to perform the operation being benchmarked
54 // a small number of times at each iteration, in order to offset the cost of
55 // PauseTiming() and ResumeTiming().
56 static constexpr std::size_t BatchSize = 32;
57
58 auto bench = [&](std::string operation, auto f) {
59 benchmark::RegisterBenchmark(container + "::" + operation, f)->Arg(32)->Arg(1024)->Arg(8192);
60 };
61
62 /////////////////////////
63 // Constructors
64 /////////////////////////
65 if constexpr (std::is_constructible_v<Container, std::size_t>) {
66 // not all containers provide this constructor
67 bench("ctor(size)", [](auto& st) {
68 auto const size = st.range(0);
69
70 for ([[maybe_unused]] auto _ : st) {
71 Container c(size); // we assume the destructor doesn't dominate the benchmark
72 DoNotOptimizeData(c);
73 }
74 });
75 }
76
77 for (auto gen : generators)
78 bench("ctor(size, value_type)" + tostr(gen), [gen](auto& st) {
79 auto const size = st.range(0);
80 ValueType value = gen();
81 benchmark::DoNotOptimize(value);
82
83 for ([[maybe_unused]] auto _ : st) {
84 Container c(size, value); // we assume the destructor doesn't dominate the benchmark
85 DoNotOptimizeData(c);
86 }
87 });
88
89 for (auto gen : generators)
90 bench("ctor(Iterator, Iterator)" + tostr(gen), [gen](auto& st) {
91 auto const size = st.range(0);
92 std::vector<ValueType> in;
93 std::generate_n(std::back_inserter(in), size, gen);
94 const auto begin = in.begin();
95 const auto end = in.end();
96 benchmark::DoNotOptimize(in);
97
98 for ([[maybe_unused]] auto _ : st) {
99 Container c(begin, end); // we assume the destructor doesn't dominate the benchmark
100 DoNotOptimizeData(c);
101 }
102 });
103
104#if defined(__cpp_lib_containers_ranges) && __cpp_lib_containers_ranges >= 202202L
105 for (auto gen : generators)
106 bench("ctor(Range)" + tostr(gen), [gen](auto& st) {
107 auto const size = st.range(0);
108 std::vector<ValueType> in;
109 std::generate_n(std::back_inserter(in), size, gen);
110 benchmark::DoNotOptimize(in);
111
112 for ([[maybe_unused]] auto _ : st) {
113 Container c(std::from_range, in); // we assume the destructor doesn't dominate the benchmark
114 DoNotOptimizeData(c);
115 }
116 });
117#endif
118
119 for (auto gen : generators)
120 bench("ctor(const&)" + tostr(gen), [gen](auto& st) {
121 auto const size = st.range(0);
122 Container in;
123 std::generate_n(std::back_inserter(in), size, gen);
124 DoNotOptimizeData(in);
125
126 for ([[maybe_unused]] auto _ : st) {
127 Container c(in); // we assume the destructor doesn't dominate the benchmark
128 DoNotOptimizeData(c);
129 DoNotOptimizeData(in);
130 }
131 });
132
133 /////////////////////////
134 // Assignment
135 /////////////////////////
136 for (auto gen : generators)
137 bench("operator=(const&)" + tostr(gen), [gen](auto& st) {
138 auto const size = st.range(0);
139 Container in1, in2;
140 std::generate_n(std::back_inserter(in1), size, gen);
141 std::generate_n(std::back_inserter(in2), size, gen);
142 DoNotOptimizeData(in1);
143 DoNotOptimizeData(in2);
144
145 // Assign from one of two containers in succession to avoid
146 // hitting a self-assignment corner-case
147 Container c(in1);
148 bool toggle = false;
149 for ([[maybe_unused]] auto _ : st) {
150 c = toggle ? in1 : in2;
151 toggle = !toggle;
152 DoNotOptimizeData(c);
153 DoNotOptimizeData(in1);
154 DoNotOptimizeData(in2);
155 }
156 });
157
158 // Benchmark Container::assign(input-iter, input-iter) when the container already contains
159 // the same number of elements that we're assigning. The intent is to check whether the
160 // implementation basically creates a new container from scratch or manages to reuse the
161 // pre-existing storage.
162 for (auto gen : generators)
163 bench("assign(input-iter, input-iter) (full container)" + tostr(gen), [gen](auto& st) {
164 auto const size = st.range(0);
165 std::vector<ValueType> in1, in2;
166 std::generate_n(std::back_inserter(in1), size, gen);
167 std::generate_n(std::back_inserter(in2), size, gen);
168 DoNotOptimizeData(in1);
169 DoNotOptimizeData(in2);
170
171 Container c(in1.begin(), in1.end());
172 bool toggle = false;
173 for ([[maybe_unused]] auto _ : st) {
174 std::vector<ValueType>& in = toggle ? in1 : in2;
175 auto first = in.data();
176 auto last = in.data() + in.size();
177 c.assign(cpp17_input_iterator(first), cpp17_input_iterator(last));
178 toggle = !toggle;
179 DoNotOptimizeData(c);
180 }
181 });
182
183 /////////////////////////
184 // Insertion
185 /////////////////////////
186 for (auto gen : generators)
187 bench("insert(begin)" + tostr(gen), [gen](auto& st) {
188 auto const size = st.range(0);
189 std::vector<ValueType> in;
190 std::generate_n(std::back_inserter(in), size, gen);
191 DoNotOptimizeData(in);
192
193 Container c(in.begin(), in.end());
194 DoNotOptimizeData(c);
195
196 ValueType value = gen();
197 benchmark::DoNotOptimize(value);
198
199 for ([[maybe_unused]] auto _ : st) {
200 c.insert(c.begin(), value);
201 DoNotOptimizeData(c);
202
203 c.erase(std::prev(c.end())); // avoid growing indefinitely
204 }
205 });
206
207 if constexpr (std::random_access_iterator<typename Container::iterator>) {
208 for (auto gen : generators)
209 bench("insert(middle)" + tostr(gen), [gen](auto& st) {
210 auto const size = st.range(0);
211 std::vector<ValueType> in;
212 std::generate_n(std::back_inserter(in), size, gen);
213 DoNotOptimizeData(in);
214
215 Container c(in.begin(), in.end());
216 DoNotOptimizeData(c);
217
218 ValueType value = gen();
219 benchmark::DoNotOptimize(value);
220
221 for ([[maybe_unused]] auto _ : st) {
222 auto mid = c.begin() + (size / 2); // requires random-access iterators in order to make sense
223 c.insert(mid, value);
224 DoNotOptimizeData(c);
225
226 c.erase(c.end() - 1); // avoid growing indefinitely
227 }
228 });
229 }
230
231 if constexpr (requires(Container c) { c.reserve(0); }) {
232 // Insert at the start of a vector in a scenario where the vector already
233 // has enough capacity to hold all the elements we are inserting.
234 for (auto gen : generators)
235 bench("insert(begin, input-iter, input-iter) (no realloc)" + tostr(gen), [gen](auto& st) {
236 auto const size = st.range(0);
237 std::vector<ValueType> in;
238 std::generate_n(std::back_inserter(in), size, gen);
239 DoNotOptimizeData(in);
240 auto first = in.data();
241 auto last = in.data() + in.size();
242
243 const int small = 100; // arbitrary
244 Container c;
245 c.reserve(size + small); // ensure no reallocation
246 std::generate_n(std::back_inserter(c), small, gen);
247
248 for ([[maybe_unused]] auto _ : st) {
249 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));
250 DoNotOptimizeData(c);
251
252 st.PauseTiming();
253 c.erase(c.begin() + small, c.end()); // avoid growing indefinitely
254 st.ResumeTiming();
255 }
256 });
257
258 // Insert at the start of a vector in a scenario where the vector already
259 // has almost enough capacity to hold all the elements we are inserting,
260 // but does need to reallocate.
261 for (auto gen : generators)
262 bench("insert(begin, input-iter, input-iter) (half filled)" + tostr(gen), [gen](auto& st) {
263 auto const size = st.range(0);
264 std::vector<ValueType> in;
265 std::generate_n(std::back_inserter(in), size, gen);
266 DoNotOptimizeData(in);
267 auto first = in.data();
268 auto last = in.data() + in.size();
269
270 const int overflow = size / 10; // 10% of elements won't fit in the vector when we insert
271 Container c;
272 for ([[maybe_unused]] auto _ : st) {
273 st.PauseTiming();
274 c = Container();
275 c.reserve(size);
276 std::generate_n(std::back_inserter(c), overflow, gen);
277 st.ResumeTiming();
278
279 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));
280 DoNotOptimizeData(c);
281 }
282 });
283
284 // Insert at the start of a vector in a scenario where the vector can fit a few
285 // more elements, but needs to reallocate almost immediately to fit the remaining
286 // elements.
287 for (auto gen : generators)
288 bench("insert(begin, input-iter, input-iter) (near full)" + tostr(gen), [gen](auto& st) {
289 auto const size = st.range(0);
290 std::vector<ValueType> in;
291 std::generate_n(std::back_inserter(in), size, gen);
292 DoNotOptimizeData(in);
293 auto first = in.data();
294 auto last = in.data() + in.size();
295
296 auto const overflow = 9 * (size / 10); // 90% of elements won't fit in the vector when we insert
297 Container c;
298 for ([[maybe_unused]] auto _ : st) {
299 st.PauseTiming();
300 c = Container();
301 c.reserve(size);
302 std::generate_n(std::back_inserter(c), overflow, gen);
303 st.ResumeTiming();
304
305 c.insert(c.begin(), cpp17_input_iterator(first), cpp17_input_iterator(last));
306 DoNotOptimizeData(c);
307 }
308 });
309 }
310
311 /////////////////////////
312 // Variations of push_back
313 /////////////////////////
314 static constexpr bool has_push_back = requires(Container c, ValueType v) { c.push_back(v); };
315 static constexpr bool has_capacity = requires(Container c) { c.capacity(); };
316 static constexpr bool has_reserve = requires(Container c) { c.reserve(0); };
317 if constexpr (has_push_back) {
318 if constexpr (has_capacity) {
319 // For containers where we can observe capacity(), push_back a single element
320 // without reserving to ensure the container needs to grow
321 for (auto gen : generators)
322 bench("push_back() (growing)" + tostr(gen), [gen](auto& st) {
323 auto const size = st.range(0);
324 std::vector<ValueType> in;
325 std::generate_n(std::back_inserter(in), size, gen);
326 DoNotOptimizeData(in);
327
328 auto at_capacity = [](Container c) {
329 while (c.size() < c.capacity())
330 c.push_back(c.back());
331 return c;
332 };
333
334 std::vector<Container> c(BatchSize, at_capacity(Container(in.begin(), in.end())));
335 std::vector<Container> const original = c;
336
337 while (st.KeepRunningBatch(BatchSize)) {
338 for (std::size_t i = 0; i != BatchSize; ++i) {
339 c[i].push_back(in[i]);
340 DoNotOptimizeData(c[i]);
341 }
342
343 st.PauseTiming();
344 for (std::size_t i = 0; i != BatchSize; ++i) {
345 c[i] = at_capacity(Container(in.begin(), in.end()));
346 assert(c[i].size() == c[i].capacity());
347 }
348 st.ResumeTiming();
349 }
350 });
351 }
352
353 // For containers where we can reserve, push_back a single element after reserving to
354 // ensure the container doesn't grow
355 if constexpr (has_reserve) {
356 for (auto gen : generators)
357 bench("push_back() (with reserve)" + tostr(gen), [gen](auto& st) {
358 auto const size = st.range(0);
359 std::vector<ValueType> in;
360 std::generate_n(std::back_inserter(in), size, gen);
361 DoNotOptimizeData(in);
362
363 Container c(in.begin(), in.end());
364 // Ensure the container has enough capacity
365 c.reserve(c.size() + BatchSize);
366 DoNotOptimizeData(c);
367
368 while (st.KeepRunningBatch(BatchSize)) {
369 for (std::size_t i = 0; i != BatchSize; ++i) {
370 c.push_back(in[i]);
371 }
372 DoNotOptimizeData(c);
373
374 st.PauseTiming();
375 c.erase(c.end() - BatchSize, c.end());
376 st.ResumeTiming();
377 }
378 });
379 }
380
381 // push_back many elements: this is amortized constant for std::vector but not all containers
382 for (auto gen : generators)
383 bench("push_back() (many elements)" + tostr(gen), [gen](auto& st) {
384 auto const size = st.range(0);
385 std::vector<ValueType> in;
386 std::generate_n(std::back_inserter(in), size, gen);
387 DoNotOptimizeData(in);
388
389 Container c;
390 DoNotOptimizeData(c);
391 while (st.KeepRunningBatch(size)) {
392 for (int i = 0; i != size; ++i) {
393 c.push_back(in[i]);
394 }
395 DoNotOptimizeData(c);
396
397 st.PauseTiming();
398 c.clear();
399 st.ResumeTiming();
400 }
401 });
402 }
403
404 /////////////////////////
405 // Erasure
406 /////////////////////////
407 for (auto gen : generators)
408 bench("erase(begin)" + tostr(gen), [gen](auto& st) {
409 auto const size = st.range(0);
410 std::vector<ValueType> in;
411 std::generate_n(std::back_inserter(in), size, gen);
412 DoNotOptimizeData(in);
413
414 Container c(in.begin(), in.end());
415 DoNotOptimizeData(c);
416
417 ValueType value = gen();
418 benchmark::DoNotOptimize(value);
419
420 for ([[maybe_unused]] auto _ : st) {
421 c.erase(c.begin());
422 DoNotOptimizeData(c);
423
424 c.insert(c.end(), value); // re-insert an element at the end to avoid needing a new container
425 }
426 });
427
428 if constexpr (std::random_access_iterator<typename Container::iterator>) {
429 for (auto gen : generators)
430 bench("erase(middle)" + tostr(gen), [gen](auto& st) {
431 auto const size = st.range(0);
432 std::vector<ValueType> in;
433 std::generate_n(std::back_inserter(in), size, gen);
434 DoNotOptimizeData(in);
435
436 Container c(in.begin(), in.end());
437 DoNotOptimizeData(c);
438
439 ValueType value = gen();
440 benchmark::DoNotOptimize(value);
441
442 for ([[maybe_unused]] auto _ : st) {
443 auto mid = c.begin() + (size / 2);
444 c.erase(mid);
445 DoNotOptimizeData(c);
446
447 c.insert(c.end(), value); // re-insert an element at the end to avoid needing a new container
448 }
449 });
450 }
451}
452
453} // namespace support
454
455#endif // TEST_BENCHMARKS_CONTAINERS_SEQUENCE_SEQUENCE_CONTAINER_BENCHMARKS_H
456

source code of libcxx/test/benchmarks/containers/sequence/sequence_container_benchmarks.h