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#ifndef TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H
10#define TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H
11
12#include <algorithm>
13#include <iterator>
14#include <random>
15#include <string>
16#include <ranges>
17#include <type_traits>
18#include <utility>
19#include <vector>
20
21#include "benchmark/benchmark.h"
22#include "../../GenerateInput.h"
23#include "test_macros.h"
24
25namespace support {
26
27template <class Container>
28struct adapt_operations {
29 // using ValueType = ...;
30 // using KeyType = ...;
31 // static ValueType value_from_key(KeyType const& k);
32 // static KeyType key_from_value(ValueType const& value);
33
34 // using InsertionResult = ...;
35 // static Container::iterator get_iterator(InsertionResult const&);
36};
37
38template <class Container>
39void associative_container_benchmarks(std::string container) {
40 using Key = typename Container::key_type;
41 using Value = typename Container::value_type;
42
43 auto generate_unique_keys = [=](std::size_t n) {
44 std::set<Key> keys;
45 while (keys.size() < n) {
46 Key k = Generate<Key>::random();
47 keys.insert(k);
48 }
49 return std::vector<Key>(keys.begin(), keys.end());
50 };
51
52 auto make_value_types = [](std::vector<Key> const& keys) {
53 std::vector<Value> kv;
54 for (Key const& k : keys)
55 kv.push_back(adapt_operations<Container>::value_from_key(k));
56 return kv;
57 };
58
59 auto get_key = [](Value const& v) { return adapt_operations<Container>::key_from_value(v); };
60
61 auto bench = [&](std::string operation, auto f) {
62 benchmark::RegisterBenchmark(container + "::" + operation, f)->Arg(0)->Arg(32)->Arg(1024)->Arg(8192);
63 };
64
65 static constexpr bool is_multi_key_container =
66 !std::is_same_v<typename adapt_operations<Container>::InsertionResult,
67 std::pair<typename Container::iterator, bool>>;
68
69 static constexpr bool is_ordered_container = requires(Container c, Key k) { c.lower_bound(k); };
70
71 static constexpr bool is_map_like = requires { typename Container::mapped_type; };
72
73 // These benchmarks are structured to perform the operation being benchmarked
74 // a small number of times at each iteration, in order to offset the cost of
75 // PauseTiming() and ResumeTiming().
76 static constexpr std::size_t BatchSize = 32;
77
78 struct alignas(Container) ScratchSpace {
79 char storage[sizeof(Container)];
80 };
81
82 /////////////////////////
83 // Constructors
84 /////////////////////////
85 bench("ctor(const&)", [=](auto& st) {
86 const std::size_t size = st.range(0);
87 std::vector<Value> in = make_value_types(generate_unique_keys(size));
88 Container src(in.begin(), in.end());
89 ScratchSpace c[BatchSize];
90
91 while (st.KeepRunningBatch(BatchSize)) {
92 for (std::size_t i = 0; i != BatchSize; ++i) {
93 new (c + i) Container(src);
94 benchmark::DoNotOptimize(c + i);
95 benchmark::ClobberMemory();
96 }
97
98 st.PauseTiming();
99 for (std::size_t i = 0; i != BatchSize; ++i) {
100 reinterpret_cast<Container*>(c + i)->~Container();
101 }
102 st.ResumeTiming();
103 }
104 });
105
106 bench("ctor(iterator, iterator) (unsorted sequence)", [=](auto& st) {
107 const std::size_t size = st.range(0);
108 std::mt19937 randomness;
109 std::vector<Key> keys = generate_unique_keys(size);
110 std::shuffle(keys.begin(), keys.end(), randomness);
111 std::vector<Value> in = make_value_types(keys);
112 ScratchSpace c[BatchSize];
113
114 while (st.KeepRunningBatch(BatchSize)) {
115 for (std::size_t i = 0; i != BatchSize; ++i) {
116 new (c + i) Container(in.begin(), in.end());
117 benchmark::DoNotOptimize(c + i);
118 benchmark::ClobberMemory();
119 }
120
121 st.PauseTiming();
122 for (std::size_t i = 0; i != BatchSize; ++i) {
123 reinterpret_cast<Container*>(c + i)->~Container();
124 }
125 st.ResumeTiming();
126 }
127 });
128
129 bench("ctor(iterator, iterator) (sorted sequence)", [=](auto& st) {
130 const std::size_t size = st.range(0);
131 std::vector<Key> keys = generate_unique_keys(size);
132 std::sort(keys.begin(), keys.end());
133 std::vector<Value> in = make_value_types(keys);
134 ScratchSpace c[BatchSize];
135
136 while (st.KeepRunningBatch(BatchSize)) {
137 for (std::size_t i = 0; i != BatchSize; ++i) {
138 new (c + i) Container(in.begin(), in.end());
139 benchmark::DoNotOptimize(c + i);
140 benchmark::ClobberMemory();
141 }
142
143 st.PauseTiming();
144 for (std::size_t i = 0; i != BatchSize; ++i) {
145 reinterpret_cast<Container*>(c + i)->~Container();
146 }
147 st.ResumeTiming();
148 }
149 });
150
151 /////////////////////////
152 // Assignment
153 /////////////////////////
154 bench("operator=(const&)", [=](auto& st) {
155 const std::size_t size = st.range(0);
156 std::vector<Value> in = make_value_types(generate_unique_keys(size));
157 Container src(in.begin(), in.end());
158 Container c[BatchSize];
159
160 while (st.KeepRunningBatch(BatchSize)) {
161 for (std::size_t i = 0; i != BatchSize; ++i) {
162 c[i] = src;
163 benchmark::DoNotOptimize(c[i]);
164 benchmark::ClobberMemory();
165 }
166
167 st.PauseTiming();
168 for (std::size_t i = 0; i != BatchSize; ++i) {
169 c[i].clear();
170 }
171 st.ResumeTiming();
172 }
173 });
174
175 /////////////////////////
176 // Insertion
177 /////////////////////////
178 bench("insert(value) (already present)", [=](auto& st) {
179 const std::size_t size = st.range(0) ? st.range(0) : 1;
180 std::vector<Value> in = make_value_types(generate_unique_keys(size));
181 Value to_insert = in[in.size() / 2]; // pick any existing value
182 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));
183 typename Container::iterator inserted[BatchSize];
184
185 while (st.KeepRunningBatch(BatchSize)) {
186 for (std::size_t i = 0; i != BatchSize; ++i) {
187 inserted[i] = adapt_operations<Container>::get_iterator(c[i].insert(to_insert));
188 benchmark::DoNotOptimize(inserted[i]);
189 benchmark::DoNotOptimize(c[i]);
190 benchmark::ClobberMemory();
191 }
192
193 if constexpr (is_multi_key_container) {
194 st.PauseTiming();
195 for (std::size_t i = 0; i != BatchSize; ++i) {
196 c[i].erase(inserted[i]);
197 }
198 st.ResumeTiming();
199 }
200 }
201 });
202
203 bench("insert(value) (new value)", [=](auto& st) {
204 const std::size_t size = st.range(0);
205 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));
206 Value to_insert = in.back();
207 in.pop_back();
208 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));
209
210 while (st.KeepRunningBatch(BatchSize)) {
211 for (std::size_t i = 0; i != BatchSize; ++i) {
212 auto result = c[i].insert(to_insert);
213 benchmark::DoNotOptimize(result);
214 benchmark::DoNotOptimize(c[i]);
215 benchmark::ClobberMemory();
216 }
217
218 st.PauseTiming();
219 for (std::size_t i = 0; i != BatchSize; ++i) {
220 c[i].erase(get_key(to_insert));
221 }
222 st.ResumeTiming();
223 }
224 });
225
226 // The insert(hint, ...) methods are only relevant for ordered containers, and we lack
227 // a good way to compute a hint for unordered ones.
228 if constexpr (is_ordered_container) {
229 bench("insert(hint, value) (good hint)", [=](auto& st) {
230 const std::size_t size = st.range(0);
231 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));
232 Value to_insert = in.back();
233 in.pop_back();
234
235 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));
236 typename Container::iterator hints[BatchSize];
237 for (std::size_t i = 0; i != BatchSize; ++i) {
238 hints[i] = c[i].lower_bound(get_key(to_insert));
239 }
240
241 while (st.KeepRunningBatch(BatchSize)) {
242 for (std::size_t i = 0; i != BatchSize; ++i) {
243 auto result = c[i].insert(hints[i], to_insert);
244 benchmark::DoNotOptimize(result);
245 benchmark::DoNotOptimize(c[i]);
246 benchmark::ClobberMemory();
247 }
248
249 st.PauseTiming();
250 for (std::size_t i = 0; i != BatchSize; ++i) {
251 c[i].erase(get_key(to_insert));
252 hints[i] = c[i].lower_bound(get_key(to_insert)); // refresh hints in case of invalidation
253 }
254 st.ResumeTiming();
255 }
256 });
257
258 bench("insert(hint, value) (bad hint)", [=](auto& st) {
259 const std::size_t size = st.range(0);
260 std::vector<Value> in = make_value_types(generate_unique_keys(size + 1));
261 Value to_insert = in.back();
262 in.pop_back();
263 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));
264
265 while (st.KeepRunningBatch(BatchSize)) {
266 for (std::size_t i = 0; i != BatchSize; ++i) {
267 auto result = c[i].insert(c[i].begin(), to_insert);
268 benchmark::DoNotOptimize(result);
269 benchmark::DoNotOptimize(c[i]);
270 benchmark::ClobberMemory();
271 }
272
273 st.PauseTiming();
274 for (std::size_t i = 0; i != BatchSize; ++i) {
275 c[i].erase(get_key(to_insert));
276 }
277 st.ResumeTiming();
278 }
279 });
280 }
281
282 bench("insert(iterator, iterator) (all new keys)", [=](auto& st) {
283 const std::size_t size = st.range(0);
284 std::vector<Value> in = make_value_types(generate_unique_keys(size + (size / 10)));
285
286 // Populate a container with a small number of elements, that's what containers will start with.
287 std::vector<Value> small;
288 for (std::size_t i = 0; i != (size / 10); ++i) {
289 small.push_back(in.back());
290 in.pop_back();
291 }
292 Container c(small.begin(), small.end());
293
294 for ([[maybe_unused]] auto _ : st) {
295 c.insert(in.begin(), in.end());
296 benchmark::DoNotOptimize(c);
297 benchmark::ClobberMemory();
298
299 st.PauseTiming();
300 c = Container(small.begin(), small.end());
301 st.ResumeTiming();
302 }
303 });
304
305 bench("insert(iterator, iterator) (half new keys)", [=](auto& st) {
306 const std::size_t size = st.range(0);
307 std::vector<Value> in = make_value_types(generate_unique_keys(size));
308
309 // Populate a container that already contains half the elements we'll try inserting,
310 // that's what our container will start with.
311 std::vector<Value> small;
312 for (std::size_t i = 0; i != size / 2; ++i) {
313 small.push_back(in.at(i * 2));
314 }
315 Container c(small.begin(), small.end());
316
317 for ([[maybe_unused]] auto _ : st) {
318 c.insert(in.begin(), in.end());
319 benchmark::DoNotOptimize(c);
320 benchmark::ClobberMemory();
321
322 st.PauseTiming();
323 c = Container(small.begin(), small.end());
324 st.ResumeTiming();
325 }
326 });
327
328 if constexpr (is_map_like) {
329 bench("insert(iterator, iterator) (product_iterator from same type)", [=](auto& st) {
330 const std::size_t size = st.range(0);
331 std::vector<Value> in = make_value_types(generate_unique_keys(size + (size / 10)));
332 Container source(in.begin(), in.end());
333
334 Container c;
335
336 for ([[maybe_unused]] auto _ : st) {
337 c.insert(source.begin(), source.end());
338 benchmark::DoNotOptimize(c);
339 benchmark::ClobberMemory();
340
341 st.PauseTiming();
342 c = Container();
343 st.ResumeTiming();
344 }
345 });
346
347#if TEST_STD_VER >= 23
348 bench("insert(iterator, iterator) (product_iterator from zip_view)", [=](auto& st) {
349 const std::size_t size = st.range(0);
350 std::vector<Key> keys = generate_unique_keys(size + (size / 10));
351 std::sort(keys.begin(), keys.end());
352 std::vector<typename Container::mapped_type> mapped(keys.size());
353
354 auto source = std::views::zip(keys, mapped);
355
356 Container c;
357
358 for ([[maybe_unused]] auto _ : st) {
359 c.insert(source.begin(), source.end());
360 benchmark::DoNotOptimize(c);
361 benchmark::ClobberMemory();
362
363 st.PauseTiming();
364 c = Container();
365 st.ResumeTiming();
366 }
367 });
368#endif
369 }
370 /////////////////////////
371 // Erasure
372 /////////////////////////
373 bench("erase(key) (existent)", [=](auto& st) {
374 const std::size_t size = st.range(0) ? st.range(0) : 1; // avoid empty container
375 std::vector<Value> in = make_value_types(generate_unique_keys(size));
376 Value element = in[in.size() / 2]; // pick any element
377 std::vector<Container> c(BatchSize, Container(in.begin(), in.end()));
378
379 while (st.KeepRunningBatch(BatchSize)) {
380 for (std::size_t i = 0; i != BatchSize; ++i) {
381 auto result = c[i].erase(get_key(element));
382 benchmark::DoNotOptimize(result);
383 benchmark::DoNotOptimize(c[i]);
384 benchmark::ClobberMemory();
385 }
386
387 st.PauseTiming();
388 for (std::size_t i = 0; i != BatchSize; ++i) {
389 c[i].insert(element);
390 }
391 st.ResumeTiming();
392 }
393 });
394
395 bench("erase(key) (non-existent)", [=](auto& st) {
396 const std::size_t size = st.range(0);
397 std::vector<Value> in = make_value_types(generate_unique_keys(size + BatchSize));
398 std::vector<Key> keys;
399 for (std::size_t i = 0; i != BatchSize; ++i) {
400 keys.push_back(get_key(in.back()));
401 in.pop_back();
402 }
403 Container c(in.begin(), in.end());
404
405 while (st.KeepRunningBatch(BatchSize)) {
406 for (std::size_t i = 0; i != BatchSize; ++i) {
407 auto result = c.erase(keys[i]);
408 benchmark::DoNotOptimize(result);
409 benchmark::DoNotOptimize(c);
410 benchmark::ClobberMemory();
411 }
412
413 // no cleanup required because we erased a non-existent element
414 }
415 });
416
417 bench("erase(iterator)", [=](auto& st) {
418 const std::size_t size = st.range(0) ? st.range(0) : 1; // avoid empty container
419 std::vector<Value> in = make_value_types(generate_unique_keys(size));
420 Value element = in[in.size() / 2]; // pick any element
421
422 std::vector<Container> c;
423 std::vector<typename Container::iterator> iterators;
424 for (std::size_t i = 0; i != BatchSize; ++i) {
425 c.push_back(Container(in.begin(), in.end()));
426 iterators.push_back(c[i].find(get_key(element)));
427 }
428
429 while (st.KeepRunningBatch(BatchSize)) {
430 for (std::size_t i = 0; i != BatchSize; ++i) {
431 auto result = c[i].erase(iterators[i]);
432 benchmark::DoNotOptimize(result);
433 benchmark::DoNotOptimize(c[i]);
434 benchmark::ClobberMemory();
435 }
436
437 st.PauseTiming();
438 for (std::size_t i = 0; i != BatchSize; ++i) {
439 iterators[i] = adapt_operations<Container>::get_iterator(c[i].insert(element));
440 }
441 st.ResumeTiming();
442 }
443 });
444
445 bench("erase(iterator, iterator) (erase half the container)", [=](auto& st) {
446 const std::size_t size = st.range(0);
447 std::vector<Value> in = make_value_types(generate_unique_keys(size));
448 Container c(in.begin(), in.end());
449
450 auto first = std::next(c.begin(), c.size() / 4);
451 auto last = std::next(c.begin(), 3 * (c.size() / 4));
452 for ([[maybe_unused]] auto _ : st) {
453 auto result = c.erase(first, last);
454 benchmark::DoNotOptimize(result);
455 benchmark::DoNotOptimize(c);
456 benchmark::ClobberMemory();
457
458 st.PauseTiming();
459 c = Container(in.begin(), in.end());
460 first = std::next(c.begin(), c.size() / 4);
461 last = std::next(c.begin(), 3 * (c.size() / 4));
462 st.ResumeTiming();
463 }
464 });
465
466 bench("clear()", [=](auto& st) {
467 const std::size_t size = st.range(0);
468 std::vector<Value> in = make_value_types(generate_unique_keys(size));
469 Container c(in.begin(), in.end());
470
471 for ([[maybe_unused]] auto _ : st) {
472 c.clear();
473 benchmark::DoNotOptimize(c);
474 benchmark::ClobberMemory();
475
476 st.PauseTiming();
477 c = Container(in.begin(), in.end());
478 st.ResumeTiming();
479 }
480 });
481
482 /////////////////////////
483 // Query
484 /////////////////////////
485 auto with_existent_key = [=](auto func) {
486 return [=](auto& st) {
487 const std::size_t size = st.range(0);
488 std::vector<Value> in = make_value_types(generate_unique_keys(size));
489 // Pick any `BatchSize` number of elements
490 std::vector<Key> keys;
491 for (std::size_t i = 0; i < in.size(); i += (in.size() / BatchSize)) {
492 keys.push_back(get_key(in.at(i)));
493 }
494 Container c(in.begin(), in.end());
495
496 while (st.KeepRunningBatch(BatchSize)) {
497 for (std::size_t i = 0; i != keys.size(); ++i) { // possible empty keys when Arg(0)
498 auto result = func(c, keys[i]);
499 benchmark::DoNotOptimize(c);
500 benchmark::DoNotOptimize(result);
501 benchmark::ClobberMemory();
502 }
503 }
504 };
505 };
506
507 auto with_nonexistent_key = [=](auto func) {
508 return [=](auto& st) {
509 const std::size_t size = st.range(0);
510 std::vector<Value> in = make_value_types(generate_unique_keys(size + BatchSize));
511 std::vector<Key> keys;
512 for (std::size_t i = 0; i != BatchSize; ++i) {
513 keys.push_back(get_key(in.back()));
514 in.pop_back();
515 }
516 Container c(in.begin(), in.end());
517
518 while (st.KeepRunningBatch(BatchSize)) {
519 for (std::size_t i = 0; i != BatchSize; ++i) {
520 auto result = func(c, keys[i]);
521 benchmark::DoNotOptimize(c);
522 benchmark::DoNotOptimize(result);
523 benchmark::ClobberMemory();
524 }
525 }
526 };
527 };
528
529 auto find = [](Container const& c, Key const& key) { return c.find(key); };
530 bench("find(key) (existent)", with_existent_key(find));
531 bench("find(key) (non-existent)", with_nonexistent_key(find));
532
533 auto count = [](Container const& c, Key const& key) { return c.count(key); };
534 bench("count(key) (existent)", with_existent_key(count));
535 bench("count(key) (non-existent)", with_nonexistent_key(count));
536
537 auto contains = [](Container const& c, Key const& key) { return c.contains(key); };
538 bench("contains(key) (existent)", with_existent_key(contains));
539 bench("contains(key) (non-existent)", with_nonexistent_key(contains));
540
541 if constexpr (is_ordered_container) {
542 auto lower_bound = [](Container const& c, Key const& key) { return c.lower_bound(key); };
543 bench("lower_bound(key) (existent)", with_existent_key(lower_bound));
544 bench("lower_bound(key) (non-existent)", with_nonexistent_key(lower_bound));
545
546 auto upper_bound = [](Container const& c, Key const& key) { return c.upper_bound(key); };
547 bench("upper_bound(key) (existent)", with_existent_key(upper_bound));
548 bench("upper_bound(key) (non-existent)", with_nonexistent_key(upper_bound));
549
550 auto equal_range = [](Container const& c, Key const& key) { return c.equal_range(key); };
551 bench("equal_range(key) (existent)", with_existent_key(equal_range));
552 bench("equal_range(key) (non-existent)", with_nonexistent_key(equal_range));
553 }
554}
555
556} // namespace support
557
558#endif // TEST_BENCHMARKS_CONTAINERS_ASSOCIATIVE_CONTAINER_BENCHMARKS_H
559

source code of libcxx/test/benchmarks/containers/associative/associative_container_benchmarks.h