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#include <algorithm>
10#include <cstdint>
11#include <map>
12#include <random>
13#include <vector>
14
15#include "CartesianBenchmarks.h"
16#include "benchmark/benchmark.h"
17#include "test_macros.h"
18
19// When VALIDATE is defined the benchmark will run to validate the benchmarks.
20// The time taken by several operations depend on whether or not an element
21// exists. To avoid errors in the benchmark these operations have a validation
22// mode to test the benchmark. Since they are not meant to be benchmarked the
23// number of sizes tested is limited to 1.
24// #define VALIDATE
25
26namespace {
27
28enum class Mode { Hit, Miss };
29
30struct AllModes : EnumValuesAsTuple<AllModes, Mode, 2> {
31 static constexpr const char* Names[] = {"ExistingElement", "NewElement"};
32};
33
34// The positions of the hints to pick:
35// - Begin picks the first item. The item cannot be put before this element.
36// - Thrid picks the third item. This is just an element with a valid entry
37// before and after it.
38// - Correct contains the correct hint.
39// - End contains a hint to the end of the map.
40enum class Hint { Begin, Third, Correct, End };
41struct AllHints : EnumValuesAsTuple<AllHints, Hint, 4> {
42 static constexpr const char* Names[] = {"Begin", "Third", "Correct", "End"};
43};
44
45enum class Order { Sorted, Random };
46struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 2> {
47 static constexpr const char* Names[] = {"Sorted", "Random"};
48};
49
50struct TestSets {
51 std::vector<uint64_t> Keys;
52 std::vector<std::map<uint64_t, int64_t> > Maps;
53 std::vector<std::vector<typename std::map<uint64_t, int64_t>::const_iterator> > Hints;
54};
55
56enum class Shuffle { None, Keys, Hints };
57
58TestSets makeTestingSets(size_t MapSize, Mode mode, Shuffle shuffle, size_t max_maps) {
59 /*
60 * The shuffle does not retain the random number generator to use the same
61 * set of random numbers for every iteration.
62 */
63 TestSets R;
64
65 int MapCount = std::min(max_maps, 1000000 / MapSize);
66
67 for (uint64_t I = 0; I < MapSize; ++I) {
68 R.Keys.push_back(mode == Mode::Hit ? 2 * I + 2 : 2 * I + 1);
69 }
70 if (shuffle == Shuffle::Keys)
71 std::shuffle(R.Keys.begin(), R.Keys.end(), std::mt19937());
72
73 for (int M = 0; M < MapCount; ++M) {
74 auto& map = R.Maps.emplace_back();
75 auto& hints = R.Hints.emplace_back();
76 for (uint64_t I = 0; I < MapSize; ++I) {
77 hints.push_back(map.insert(std::make_pair(2 * I + 2, 0)).first);
78 }
79 if (shuffle == Shuffle::Hints)
80 std::shuffle(hints.begin(), hints.end(), std::mt19937());
81 }
82
83 return R;
84}
85
86struct Base {
87 size_t MapSize;
88 Base(size_t T) : MapSize(T) {}
89
90 std::string baseName() const { return "_MapSize=" + std::to_string(val: MapSize); }
91};
92
93//*******************************************************************|
94// Member functions |
95//*******************************************************************|
96
97struct ConstructorDefault {
98 void run(benchmark::State& State) const {
99 for (auto _ : State) {
100 benchmark::DoNotOptimize(std::map<uint64_t, int64_t>());
101 }
102 }
103
104 std::string name() const { return "BM_ConstructorDefault"; }
105};
106
107struct ConstructorIterator : Base {
108 using Base::Base;
109
110 void run(benchmark::State& State) const {
111 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1);
112 auto& Map = Data.Maps.front();
113 while (State.KeepRunningBatch(n: MapSize)) {
114#ifndef VALIDATE
115 benchmark::DoNotOptimize(std::map<uint64_t, int64_t>(Map.begin(), Map.end()));
116#else
117 std::map<uint64_t, int64_t> M{Map.begin(), Map.end()};
118 if (M != Map)
119 State.SkipWithError("Map copy not identical");
120#endif
121 }
122 }
123
124 std::string name() const { return "BM_ConstructorIterator" + baseName(); }
125};
126
127struct ConstructorCopy : Base {
128 using Base::Base;
129
130 void run(benchmark::State& State) const {
131 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1);
132 auto& Map = Data.Maps.front();
133 while (State.KeepRunningBatch(n: MapSize)) {
134#ifndef VALIDATE
135 std::map<uint64_t, int64_t> M(Map);
136 benchmark::DoNotOptimize(M);
137#else
138 std::map<uint64_t, int64_t> M(Map);
139 if (M != Map)
140 State.SkipWithError("Map copy not identical");
141#endif
142 }
143 }
144
145 std::string name() const { return "BM_ConstructorCopy" + baseName(); }
146};
147
148struct ConstructorMove : Base {
149 using Base::Base;
150
151 void run(benchmark::State& State) const {
152 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
153 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
154 for (auto& Map : Data.Maps) {
155 std::map<uint64_t, int64_t> M(std::move(Map));
156 benchmark::DoNotOptimize(M);
157 }
158 State.PauseTiming();
159 Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
160 State.ResumeTiming();
161 }
162 }
163
164 std::string name() const { return "BM_ConstructorMove" + baseName(); }
165};
166
167//*******************************************************************|
168// Capacity |
169//*******************************************************************|
170
171struct Empty : Base {
172 using Base::Base;
173
174 void run(benchmark::State& State) const {
175 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1);
176 auto& Map = Data.Maps.front();
177 for (auto _ : State) {
178#ifndef VALIDATE
179 benchmark::DoNotOptimize(Map.empty());
180#else
181 if (Map.empty())
182 State.SkipWithError("Map contains an invalid number of elements.");
183#endif
184 }
185 }
186
187 std::string name() const { return "BM_Empty" + baseName(); }
188};
189
190struct Size : Base {
191 using Base::Base;
192
193 void run(benchmark::State& State) const {
194 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1);
195 auto& Map = Data.Maps.front();
196 for (auto _ : State) {
197#ifndef VALIDATE
198 benchmark::DoNotOptimize(Map.size());
199#else
200 if (Map.size() != MapSize)
201 State.SkipWithError("Map contains an invalid number of elements.");
202#endif
203 }
204 }
205
206 std::string name() const { return "BM_Size" + baseName(); }
207};
208
209//*******************************************************************|
210// Modifiers |
211//*******************************************************************|
212
213struct Clear : Base {
214 using Base::Base;
215
216 void run(benchmark::State& State) const {
217 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
218 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
219 for (auto& Map : Data.Maps) {
220 Map.clear();
221 benchmark::DoNotOptimize(Map);
222 }
223 State.PauseTiming();
224 Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
225 State.ResumeTiming();
226 }
227 }
228
229 std::string name() const { return "BM_Clear" + baseName(); }
230};
231
232template <class Mode, class Order>
233struct Insert : Base {
234 using Base::Base;
235
236 void run(benchmark::State& State) const {
237 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
238 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
239 for (auto& Map : Data.Maps) {
240 for (auto K : Data.Keys) {
241#ifndef VALIDATE
242 benchmark::DoNotOptimize(Map.insert(std::make_pair(K, 1)));
243#else
244 bool Inserted = Map.insert(std::make_pair(K, 1)).second;
245 if (Mode() == ::Mode::Hit) {
246 if (Inserted)
247 State.SkipWithError("Inserted a duplicate element");
248 } else {
249 if (!Inserted)
250 State.SkipWithError("Failed to insert e new element");
251 }
252#endif
253 }
254 }
255
256 State.PauseTiming();
257 Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
258 State.ResumeTiming();
259 }
260 }
261
262 std::string name() const { return "BM_Insert" + baseName() + Mode::name() + Order::name(); }
263};
264
265template <class Mode, class Hint>
266struct InsertHint : Base {
267 using Base::Base;
268
269 template < ::Hint hint>
270 typename std::enable_if<hint == ::Hint::Correct>::type run(benchmark::State& State) const {
271 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
272 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
273 for (size_t I = 0; I < Data.Maps.size(); ++I) {
274 auto& Map = Data.Maps[I];
275 auto H = Data.Hints[I].begin();
276 for (auto K : Data.Keys) {
277#ifndef VALIDATE
278 benchmark::DoNotOptimize(Map.insert(*H, std::make_pair(K, 1)));
279#else
280 auto Inserted = Map.insert(*H, std::make_pair(K, 1));
281 if (Mode() == ::Mode::Hit) {
282 if (Inserted != *H)
283 State.SkipWithError("Inserted a duplicate element");
284 } else {
285 if (++Inserted != *H)
286 State.SkipWithError("Failed to insert a new element");
287 }
288#endif
289 ++H;
290 }
291 }
292
293 State.PauseTiming();
294 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
295 State.ResumeTiming();
296 }
297 }
298
299 template < ::Hint hint>
300 typename std::enable_if<hint != ::Hint::Correct>::type run(benchmark::State& State) const {
301 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
302 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
303 for (size_t I = 0; I < Data.Maps.size(); ++I) {
304 auto& Map = Data.Maps[I];
305 auto Third = *(Data.Hints[I].begin() + 2);
306 for (auto K : Data.Keys) {
307 auto Itor = hint == ::Hint::Begin ? Map.begin() : hint == ::Hint::Third ? Third : Map.end();
308#ifndef VALIDATE
309 benchmark::DoNotOptimize(Map.insert(Itor, std::make_pair(K, 1)));
310#else
311 size_t Size = Map.size();
312 Map.insert(Itor, std::make_pair(K, 1));
313 if (Mode() == ::Mode::Hit) {
314 if (Size != Map.size())
315 State.SkipWithError("Inserted a duplicate element");
316 } else {
317 if (Size + 1 != Map.size())
318 State.SkipWithError("Failed to insert a new element");
319 }
320#endif
321 }
322 }
323
324 State.PauseTiming();
325 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
326 State.ResumeTiming();
327 }
328 }
329
330 void run(benchmark::State& State) const {
331 static constexpr auto h = Hint();
332 run<h>(State);
333 }
334
335 std::string name() const { return "BM_InsertHint" + baseName() + Mode::name() + Hint::name(); }
336};
337
338template <class Mode, class Order>
339struct InsertAssign : Base {
340 using Base::Base;
341
342 void run(benchmark::State& State) const {
343 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
344 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
345 for (auto& Map : Data.Maps) {
346 for (auto K : Data.Keys) {
347#ifndef VALIDATE
348 benchmark::DoNotOptimize(Map.insert_or_assign(K, 1));
349#else
350 bool Inserted = Map.insert_or_assign(K, 1).second;
351 if (Mode() == ::Mode::Hit) {
352 if (Inserted)
353 State.SkipWithError("Inserted a duplicate element");
354 } else {
355 if (!Inserted)
356 State.SkipWithError("Failed to insert e new element");
357 }
358#endif
359 }
360 }
361
362 State.PauseTiming();
363 Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
364 State.ResumeTiming();
365 }
366 }
367
368 std::string name() const { return "BM_InsertAssign" + baseName() + Mode::name() + Order::name(); }
369};
370
371template <class Mode, class Hint>
372struct InsertAssignHint : Base {
373 using Base::Base;
374
375 template < ::Hint hint>
376 typename std::enable_if<hint == ::Hint::Correct>::type run(benchmark::State& State) const {
377 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
378 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
379 for (size_t I = 0; I < Data.Maps.size(); ++I) {
380 auto& Map = Data.Maps[I];
381 auto H = Data.Hints[I].begin();
382 for (auto K : Data.Keys) {
383#ifndef VALIDATE
384 benchmark::DoNotOptimize(Map.insert_or_assign(*H, K, 1));
385#else
386 auto Inserted = Map.insert_or_assign(*H, K, 1);
387 if (Mode() == ::Mode::Hit) {
388 if (Inserted != *H)
389 State.SkipWithError("Inserted a duplicate element");
390 } else {
391 if (++Inserted != *H)
392 State.SkipWithError("Failed to insert a new element");
393 }
394#endif
395 ++H;
396 }
397 }
398
399 State.PauseTiming();
400 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
401 State.ResumeTiming();
402 }
403 }
404
405 template < ::Hint hint>
406 typename std::enable_if<hint != ::Hint::Correct>::type run(benchmark::State& State) const {
407 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
408 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
409 for (size_t I = 0; I < Data.Maps.size(); ++I) {
410 auto& Map = Data.Maps[I];
411 auto Third = *(Data.Hints[I].begin() + 2);
412 for (auto K : Data.Keys) {
413 auto Itor = hint == ::Hint::Begin ? Map.begin() : hint == ::Hint::Third ? Third : Map.end();
414#ifndef VALIDATE
415 benchmark::DoNotOptimize(Map.insert_or_assign(Itor, K, 1));
416#else
417 size_t Size = Map.size();
418 Map.insert_or_assign(Itor, K, 1);
419 if (Mode() == ::Mode::Hit) {
420 if (Size != Map.size())
421 State.SkipWithError("Inserted a duplicate element");
422 } else {
423 if (Size + 1 != Map.size())
424 State.SkipWithError("Failed to insert a new element");
425 }
426#endif
427 }
428 }
429
430 State.PauseTiming();
431 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
432 State.ResumeTiming();
433 }
434 }
435
436 void run(benchmark::State& State) const {
437 static constexpr auto h = Hint();
438 run<h>(State);
439 }
440
441 std::string name() const { return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name(); }
442};
443
444template <class Mode, class Order>
445struct Emplace : Base {
446 using Base::Base;
447
448 void run(benchmark::State& State) const {
449 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
450 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
451 for (auto& Map : Data.Maps) {
452 for (auto K : Data.Keys) {
453#ifndef VALIDATE
454 benchmark::DoNotOptimize(Map.emplace(K, 1));
455#else
456 bool Inserted = Map.emplace(K, 1).second;
457 if (Mode() == ::Mode::Hit) {
458 if (Inserted)
459 State.SkipWithError("Emplaced a duplicate element");
460 } else {
461 if (!Inserted)
462 State.SkipWithError("Failed to emplace a new element");
463 }
464#endif
465 }
466 }
467
468 State.PauseTiming();
469 Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
470 State.ResumeTiming();
471 }
472 }
473
474 std::string name() const { return "BM_Emplace" + baseName() + Mode::name() + Order::name(); }
475};
476
477template <class Mode, class Hint>
478struct EmplaceHint : Base {
479 using Base::Base;
480
481 template < ::Hint hint>
482 typename std::enable_if<hint == ::Hint::Correct>::type run(benchmark::State& State) const {
483 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
484 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
485 for (size_t I = 0; I < Data.Maps.size(); ++I) {
486 auto& Map = Data.Maps[I];
487 auto H = Data.Hints[I].begin();
488 for (auto K : Data.Keys) {
489#ifndef VALIDATE
490 benchmark::DoNotOptimize(Map.emplace_hint(*H, K, 1));
491#else
492 auto Inserted = Map.emplace_hint(*H, K, 1);
493 if (Mode() == ::Mode::Hit) {
494 if (Inserted != *H)
495 State.SkipWithError("Emplaced a duplicate element");
496 } else {
497 if (++Inserted != *H)
498 State.SkipWithError("Failed to emplace a new element");
499 }
500#endif
501 ++H;
502 }
503 }
504
505 State.PauseTiming();
506 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
507 State.ResumeTiming();
508 }
509 }
510
511 template < ::Hint hint>
512 typename std::enable_if<hint != ::Hint::Correct>::type run(benchmark::State& State) const {
513 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
514 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
515 for (size_t I = 0; I < Data.Maps.size(); ++I) {
516 auto& Map = Data.Maps[I];
517 auto Third = *(Data.Hints[I].begin() + 2);
518 for (auto K : Data.Keys) {
519 auto Itor = hint == ::Hint::Begin ? Map.begin() : hint == ::Hint::Third ? Third : Map.end();
520#ifndef VALIDATE
521 benchmark::DoNotOptimize(Map.emplace_hint(Itor, K, 1));
522#else
523 size_t Size = Map.size();
524 Map.emplace_hint(Itor, K, 1);
525 if (Mode() == ::Mode::Hit) {
526 if (Size != Map.size())
527 State.SkipWithError("Emplaced a duplicate element");
528 } else {
529 if (Size + 1 != Map.size())
530 State.SkipWithError("Failed to emplace a new element");
531 }
532#endif
533 }
534 }
535
536 State.PauseTiming();
537 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
538 State.ResumeTiming();
539 }
540 }
541
542 void run(benchmark::State& State) const {
543 static constexpr auto h = Hint();
544 run<h>(State);
545 }
546
547 std::string name() const { return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name(); }
548};
549
550template <class Mode, class Order>
551struct TryEmplace : Base {
552 using Base::Base;
553
554 void run(benchmark::State& State) const {
555 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
556 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
557 for (auto& Map : Data.Maps) {
558 for (auto K : Data.Keys) {
559#ifndef VALIDATE
560 benchmark::DoNotOptimize(Map.try_emplace(K, 1));
561#else
562 bool Inserted = Map.try_emplace(K, 1).second;
563 if (Mode() == ::Mode::Hit) {
564 if (Inserted)
565 State.SkipWithError("Emplaced a duplicate element");
566 } else {
567 if (!Inserted)
568 State.SkipWithError("Failed to emplace a new element");
569 }
570#endif
571 }
572 }
573
574 State.PauseTiming();
575 Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
576 State.ResumeTiming();
577 }
578 }
579
580 std::string name() const { return "BM_TryEmplace" + baseName() + Mode::name() + Order::name(); }
581};
582
583template <class Mode, class Hint>
584struct TryEmplaceHint : Base {
585 using Base::Base;
586
587 template < ::Hint hint>
588 typename std::enable_if<hint == ::Hint::Correct>::type run(benchmark::State& State) const {
589 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
590 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
591 for (size_t I = 0; I < Data.Maps.size(); ++I) {
592 auto& Map = Data.Maps[I];
593 auto H = Data.Hints[I].begin();
594 for (auto K : Data.Keys) {
595#ifndef VALIDATE
596 benchmark::DoNotOptimize(Map.try_emplace(*H, K, 1));
597#else
598 auto Inserted = Map.try_emplace(*H, K, 1);
599 if (Mode() == ::Mode::Hit) {
600 if (Inserted != *H)
601 State.SkipWithError("Emplaced a duplicate element");
602 } else {
603 if (++Inserted != *H)
604 State.SkipWithError("Failed to emplace a new element");
605 }
606#endif
607 ++H;
608 }
609 }
610
611 State.PauseTiming();
612 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
613 State.ResumeTiming();
614 }
615 }
616
617 template < ::Hint hint>
618 typename std::enable_if<hint != ::Hint::Correct>::type run(benchmark::State& State) const {
619 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
620 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
621 for (size_t I = 0; I < Data.Maps.size(); ++I) {
622 auto& Map = Data.Maps[I];
623 auto Third = *(Data.Hints[I].begin() + 2);
624 for (auto K : Data.Keys) {
625 auto Itor = hint == ::Hint::Begin ? Map.begin() : hint == ::Hint::Third ? Third : Map.end();
626#ifndef VALIDATE
627 benchmark::DoNotOptimize(Map.try_emplace(Itor, K, 1));
628#else
629 size_t Size = Map.size();
630 Map.try_emplace(Itor, K, 1);
631 if (Mode() == ::Mode::Hit) {
632 if (Size != Map.size())
633 State.SkipWithError("Emplaced a duplicate element");
634 } else {
635 if (Size + 1 != Map.size())
636 State.SkipWithError("Failed to emplace a new element");
637 }
638#endif
639 }
640 }
641
642 State.PauseTiming();
643 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
644 State.ResumeTiming();
645 }
646 }
647
648 void run(benchmark::State& State) const {
649 static constexpr auto h = Hint();
650 run<h>(State);
651 }
652
653 std::string name() const { return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name(); }
654};
655
656template <class Mode, class Order>
657struct Erase : Base {
658 using Base::Base;
659
660 void run(benchmark::State& State) const {
661 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
662 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
663 for (auto& Map : Data.Maps) {
664 for (auto K : Data.Keys) {
665#ifndef VALIDATE
666 benchmark::DoNotOptimize(Map.erase(K));
667#else
668 size_t I = Map.erase(K);
669 if (Mode() == ::Mode::Hit) {
670 if (I == 0)
671 State.SkipWithError("Did not find the existing element");
672 } else {
673 if (I == 1)
674 State.SkipWithError("Did find the non-existing element");
675 }
676#endif
677 }
678 }
679
680 State.PauseTiming();
681 Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
682 State.ResumeTiming();
683 }
684 }
685
686 std::string name() const { return "BM_Erase" + baseName() + Mode::name() + Order::name(); }
687};
688
689template <class Order>
690struct EraseIterator : Base {
691 using Base::Base;
692
693 void run(benchmark::State& State) const {
694 auto Data =
695 makeTestingSets(MapSize, Mode::Hit, Order::value == ::Order::Random ? Shuffle::Hints : Shuffle::None, 1000);
696 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
697 for (size_t I = 0; I < Data.Maps.size(); ++I) {
698 auto& Map = Data.Maps[I];
699 for (auto H : Data.Hints[I]) {
700 benchmark::DoNotOptimize(Map.erase(H));
701 }
702#ifdef VALIDATE
703 if (!Map.empty())
704 State.SkipWithError("Did not erase the entire map");
705#endif
706 }
707
708 State.PauseTiming();
709 Data =
710 makeTestingSets(MapSize, Mode::Hit, Order::value == ::Order::Random ? Shuffle::Hints : Shuffle::None, 1000);
711 State.ResumeTiming();
712 }
713 }
714
715 std::string name() const { return "BM_EraseIterator" + baseName() + Order::name(); }
716};
717
718struct EraseRange : Base {
719 using Base::Base;
720
721 void run(benchmark::State& State) const {
722 auto Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
723 while (State.KeepRunningBatch(n: MapSize * Data.Maps.size())) {
724 for (auto& Map : Data.Maps) {
725#ifndef VALIDATE
726 benchmark::DoNotOptimize(Map.erase(Map.begin(), Map.end()));
727#else
728 Map.erase(Map.begin(), Map.end());
729 if (!Map.empty())
730 State.SkipWithError("Did not erase the entire map");
731#endif
732 }
733
734 State.PauseTiming();
735 Data = makeTestingSets(MapSize, mode: Mode::Hit, shuffle: Shuffle::None, max_maps: 1000);
736 State.ResumeTiming();
737 }
738 }
739
740 std::string name() const { return "BM_EraseRange" + baseName(); }
741};
742
743//*******************************************************************|
744// Lookup |
745//*******************************************************************|
746
747template <class Mode, class Order>
748struct Count : Base {
749 using Base::Base;
750
751 void run(benchmark::State& State) const {
752 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
753 auto& Map = Data.Maps.front();
754 while (State.KeepRunningBatch(n: MapSize)) {
755 for (auto K : Data.Keys) {
756#ifndef VALIDATE
757 benchmark::DoNotOptimize(Map.count(K));
758#else
759 size_t I = Map.count(K);
760 if (Mode() == ::Mode::Hit) {
761 if (I == 0)
762 State.SkipWithError("Did not find the existing element");
763 } else {
764 if (I == 1)
765 State.SkipWithError("Did find the non-existing element");
766 }
767#endif
768 }
769 }
770 }
771
772 std::string name() const { return "BM_Count" + baseName() + Mode::name() + Order::name(); }
773};
774
775template <class Mode, class Order>
776struct Find : Base {
777 using Base::Base;
778
779 void run(benchmark::State& State) const {
780 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
781 auto& Map = Data.Maps.front();
782 while (State.KeepRunningBatch(n: MapSize)) {
783 for (auto K : Data.Keys) {
784#ifndef VALIDATE
785 benchmark::DoNotOptimize(Map.find(K));
786#else
787 auto Itor = Map.find(K);
788 if (Mode() == ::Mode::Hit) {
789 if (Itor == Map.end())
790 State.SkipWithError("Did not find the existing element");
791 } else {
792 if (Itor != Map.end())
793 State.SkipWithError("Did find the non-existing element");
794 }
795#endif
796 }
797 }
798 }
799
800 std::string name() const { return "BM_Find" + baseName() + Mode::name() + Order::name(); }
801};
802
803template <class Mode, class Order>
804struct EqualRange : Base {
805 using Base::Base;
806
807 void run(benchmark::State& State) const {
808 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
809 auto& Map = Data.Maps.front();
810 while (State.KeepRunningBatch(n: MapSize)) {
811 for (auto K : Data.Keys) {
812#ifndef VALIDATE
813 benchmark::DoNotOptimize(Map.equal_range(K));
814#else
815 auto Range = Map.equal_range(K);
816 if (Mode() == ::Mode::Hit) {
817 // Adjust validation for the last element.
818 auto Key = K;
819 if (Range.second == Map.end() && K == 2 * MapSize) {
820 --Range.second;
821 Key -= 2;
822 }
823 if (Range.first == Map.end() || Range.first->first != K || Range.second == Map.end() ||
824 Range.second->first - 2 != Key)
825 State.SkipWithError("Did not find the existing element");
826 } else {
827 if (Range.first == Map.end() || Range.first->first - 1 != K || Range.second == Map.end() ||
828 Range.second->first - 1 != K)
829 State.SkipWithError("Did find the non-existing element");
830 }
831#endif
832 }
833 }
834 }
835
836 std::string name() const { return "BM_EqualRange" + baseName() + Mode::name() + Order::name(); }
837};
838
839template <class Mode, class Order>
840struct LowerBound : Base {
841 using Base::Base;
842
843 void run(benchmark::State& State) const {
844 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
845 auto& Map = Data.Maps.front();
846 while (State.KeepRunningBatch(n: MapSize)) {
847 for (auto K : Data.Keys) {
848#ifndef VALIDATE
849 benchmark::DoNotOptimize(Map.lower_bound(K));
850#else
851 auto Itor = Map.lower_bound(K);
852 if (Mode() == ::Mode::Hit) {
853 if (Itor == Map.end() || Itor->first != K)
854 State.SkipWithError("Did not find the existing element");
855 } else {
856 if (Itor == Map.end() || Itor->first - 1 != K)
857 State.SkipWithError("Did find the non-existing element");
858 }
859#endif
860 }
861 }
862 }
863
864 std::string name() const { return "BM_LowerBound" + baseName() + Mode::name() + Order::name(); }
865};
866
867template <class Mode, class Order>
868struct UpperBound : Base {
869 using Base::Base;
870
871 void run(benchmark::State& State) const {
872 auto Data = makeTestingSets(MapSize, Mode(), Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
873 auto& Map = Data.Maps.front();
874 while (State.KeepRunningBatch(n: MapSize)) {
875 for (auto K : Data.Keys) {
876#ifndef VALIDATE
877 benchmark::DoNotOptimize(Map.upper_bound(K));
878#else
879 std::map<uint64_t, int64_t>::iterator Itor = Map.upper_bound(K);
880 if (Mode() == ::Mode::Hit) {
881 // Adjust validation for the last element.
882 auto Key = K;
883 if (Itor == Map.end() && K == 2 * MapSize) {
884 --Itor;
885 Key -= 2;
886 }
887 if (Itor == Map.end() || Itor->first - 2 != Key)
888 State.SkipWithError("Did not find the existing element");
889 } else {
890 if (Itor == Map.end() || Itor->first - 1 != K)
891 State.SkipWithError("Did find the non-existing element");
892 }
893#endif
894 }
895 }
896 }
897
898 std::string name() const { return "BM_UpperBound" + baseName() + Mode::name() + Order::name(); }
899};
900
901} // namespace
902
903int main(int argc, char** argv) {
904 benchmark::Initialize(argc: &argc, argv);
905 if (benchmark::ReportUnrecognizedArguments(argc, argv))
906 return 1;
907
908#ifdef VALIDATE
909 const std::vector<size_t> MapSize{10};
910#else
911 const std::vector<size_t> MapSize{10, 100, 1000, 10000, 100000, 1000000};
912#endif
913
914 // Member functions
915 makeCartesianProductBenchmark<ConstructorDefault>();
916 makeCartesianProductBenchmark<ConstructorIterator>(A: MapSize);
917 makeCartesianProductBenchmark<ConstructorCopy>(A: MapSize);
918 makeCartesianProductBenchmark<ConstructorMove>(A: MapSize);
919
920 // Capacity
921 makeCartesianProductBenchmark<Empty>(A: MapSize);
922 makeCartesianProductBenchmark<Size>(A: MapSize);
923
924 // Modifiers
925 makeCartesianProductBenchmark<Clear>(A: MapSize);
926 makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(A: MapSize);
927 makeCartesianProductBenchmark<InsertHint, AllModes, AllHints>(A: MapSize);
928 makeCartesianProductBenchmark<InsertAssign, AllModes, AllOrders>(A: MapSize);
929 makeCartesianProductBenchmark<InsertAssignHint, AllModes, AllHints>(A: MapSize);
930
931 makeCartesianProductBenchmark<Emplace, AllModes, AllOrders>(A: MapSize);
932 makeCartesianProductBenchmark<EmplaceHint, AllModes, AllHints>(A: MapSize);
933 makeCartesianProductBenchmark<TryEmplace, AllModes, AllOrders>(A: MapSize);
934 makeCartesianProductBenchmark<TryEmplaceHint, AllModes, AllHints>(A: MapSize);
935 makeCartesianProductBenchmark<Erase, AllModes, AllOrders>(A: MapSize);
936 makeCartesianProductBenchmark<EraseIterator, AllOrders>(A: MapSize);
937 makeCartesianProductBenchmark<EraseRange>(A: MapSize);
938
939 // Lookup
940 makeCartesianProductBenchmark<Count, AllModes, AllOrders>(A: MapSize);
941 makeCartesianProductBenchmark<Find, AllModes, AllOrders>(A: MapSize);
942 makeCartesianProductBenchmark<EqualRange, AllModes, AllOrders>(A: MapSize);
943 makeCartesianProductBenchmark<LowerBound, AllModes, AllOrders>(A: MapSize);
944 makeCartesianProductBenchmark<UpperBound, AllModes, AllOrders>(A: MapSize);
945
946 benchmark::RunSpecifiedBenchmarks();
947}
948

source code of libcxx/benchmarks/map.bench.cpp