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
26 namespace {
27
28 enum class Mode { Hit, Miss };
29
30 struct 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.
40 enum class Hint { Begin, Third, Correct, End };
41 struct AllHints : EnumValuesAsTuple<AllHints, Hint, 4> {
42 static constexpr const char* Names[] = {"Begin", "Third", "Correct", "End"};
43 };
44
45 enum class Order { Sorted, Random };
46 struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 2> {
47 static constexpr const char* Names[] = {"Sorted", "Random"};
48 };
49
50 struct TestSets {
51 std::vector<uint64_t> Keys;
52 std::vector<std::map<uint64_t, int64_t> > Maps;
53 std::vector<
54 std::vector<typename std::map<uint64_t, int64_t>::const_iterator> >
55 Hints;
56 };
57
58 enum class Shuffle { None, Keys, Hints };
59
makeTestingSets(size_t MapSize,Mode mode,Shuffle shuffle,size_t max_maps)60 TestSets makeTestingSets(size_t MapSize, Mode mode, Shuffle shuffle,
61 size_t max_maps) {
62 /*
63 * The shuffle does not retain the random number generator to use the same
64 * set of random numbers for every iteration.
65 */
66 TestSets R;
67
68 int MapCount = std::min(max_maps, 1000000 / MapSize);
69
70 for (uint64_t I = 0; I < MapSize; ++I) {
71 R.Keys.push_back(mode == Mode::Hit ? 2 * I + 2 : 2 * I + 1);
72 }
73 if (shuffle == Shuffle::Keys)
74 std::shuffle(R.Keys.begin(), R.Keys.end(), std::mt19937());
75
76 for (int M = 0; M < MapCount; ++M) {
77 auto& map = R.Maps.emplace_back();
78 auto& hints = R.Hints.emplace_back();
79 for (uint64_t I = 0; I < MapSize; ++I) {
80 hints.push_back(map.insert(std::make_pair(2 * I + 2, 0)).first);
81 }
82 if (shuffle == Shuffle::Hints)
83 std::shuffle(hints.begin(), hints.end(), std::mt19937());
84 }
85
86 return R;
87 }
88
89 struct Base {
90 size_t MapSize;
Base__anon482b47ff0111::Base91 Base(size_t T) : MapSize(T) {}
92
baseName__anon482b47ff0111::Base93 std::string baseName() const { return "_MapSize=" + std::to_string(MapSize); }
94 };
95
96 //*******************************************************************|
97 // Member functions |
98 //*******************************************************************|
99
100 struct ConstructorDefault {
run__anon482b47ff0111::ConstructorDefault101 void run(benchmark::State& State) const {
102 for (auto _ : State) {
103 benchmark::DoNotOptimize(std::map<uint64_t, int64_t>());
104 }
105 }
106
name__anon482b47ff0111::ConstructorDefault107 std::string name() const { return "BM_ConstructorDefault"; }
108 };
109
110 struct ConstructorIterator : Base {
111 using Base::Base;
112
run__anon482b47ff0111::ConstructorIterator113 void run(benchmark::State& State) const {
114 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
115 auto& Map = Data.Maps.front();
116 while (State.KeepRunningBatch(MapSize)) {
117 #ifndef VALIDATE
118 benchmark::DoNotOptimize(
119 std::map<uint64_t, int64_t>(Map.begin(), Map.end()));
120 #else
121 std::map<uint64_t, int64_t> M{Map.begin(), Map.end()};
122 if (M != Map)
123 State.SkipWithError("Map copy not identical");
124 #endif
125 }
126 }
127
name__anon482b47ff0111::ConstructorIterator128 std::string name() const { return "BM_ConstructorIterator" + baseName(); }
129 };
130
131 struct ConstructorCopy : Base {
132 using Base::Base;
133
run__anon482b47ff0111::ConstructorCopy134 void run(benchmark::State& State) const {
135 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
136 auto& Map = Data.Maps.front();
137 while (State.KeepRunningBatch(MapSize)) {
138 #ifndef VALIDATE
139 std::map<uint64_t, int64_t> M(Map);
140 benchmark::DoNotOptimize(M);
141 #else
142 std::map<uint64_t, int64_t> M(Map);
143 if (M != Map)
144 State.SkipWithError("Map copy not identical");
145 #endif
146 }
147 }
148
name__anon482b47ff0111::ConstructorCopy149 std::string name() const { return "BM_ConstructorCopy" + baseName(); }
150 };
151
152 struct ConstructorMove : Base {
153 using Base::Base;
154
run__anon482b47ff0111::ConstructorMove155 void run(benchmark::State& State) const {
156 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
157 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
158 for (auto& Map : Data.Maps) {
159 std::map<uint64_t, int64_t> M(std::move(Map));
160 benchmark::DoNotOptimize(M);
161 }
162 State.PauseTiming();
163 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
164 State.ResumeTiming();
165 }
166 }
167
name__anon482b47ff0111::ConstructorMove168 std::string name() const { return "BM_ConstructorMove" + baseName(); }
169 };
170
171 //*******************************************************************|
172 // Capacity |
173 //*******************************************************************|
174
175 struct Empty : Base {
176 using Base::Base;
177
run__anon482b47ff0111::Empty178 void run(benchmark::State& State) const {
179 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
180 auto& Map = Data.Maps.front();
181 for (auto _ : State) {
182 #ifndef VALIDATE
183 benchmark::DoNotOptimize(Map.empty());
184 #else
185 if (Map.empty())
186 State.SkipWithError("Map contains an invalid number of elements.");
187 #endif
188 }
189 }
190
name__anon482b47ff0111::Empty191 std::string name() const { return "BM_Empty" + baseName(); }
192 };
193
194 struct Size : Base {
195 using Base::Base;
196
run__anon482b47ff0111::Size197 void run(benchmark::State& State) const {
198 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
199 auto& Map = Data.Maps.front();
200 for (auto _ : State) {
201 #ifndef VALIDATE
202 benchmark::DoNotOptimize(Map.size());
203 #else
204 if (Map.size() != MapSize)
205 State.SkipWithError("Map contains an invalid number of elements.");
206 #endif
207 }
208 }
209
name__anon482b47ff0111::Size210 std::string name() const { return "BM_Size" + baseName(); }
211 };
212
213 //*******************************************************************|
214 // Modifiers |
215 //*******************************************************************|
216
217 struct Clear : Base {
218 using Base::Base;
219
run__anon482b47ff0111::Clear220 void run(benchmark::State& State) const {
221 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
222 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
223 for (auto& Map : Data.Maps) {
224 Map.clear();
225 benchmark::DoNotOptimize(Map);
226 }
227 State.PauseTiming();
228 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
229 State.ResumeTiming();
230 }
231 }
232
name__anon482b47ff0111::Clear233 std::string name() const { return "BM_Clear" + baseName(); }
234 };
235
236 template <class Mode, class Order>
237 struct Insert : Base {
238 using Base::Base;
239
run__anon482b47ff0111::Insert240 void run(benchmark::State& State) const {
241 auto Data = makeTestingSets(
242 MapSize, Mode(),
243 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
244 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
245 for (auto& Map : Data.Maps) {
246 for (auto K : Data.Keys) {
247 #ifndef VALIDATE
248 benchmark::DoNotOptimize(Map.insert(std::make_pair(K, 1)));
249 #else
250 bool Inserted = Map.insert(std::make_pair(K, 1)).second;
251 if (Mode() == ::Mode::Hit) {
252 if (Inserted)
253 State.SkipWithError("Inserted a duplicate element");
254 } else {
255 if (!Inserted)
256 State.SkipWithError("Failed to insert e new element");
257 }
258 #endif
259 }
260 }
261
262 State.PauseTiming();
263 Data = makeTestingSets(MapSize, Mode(),
264 Order::value == ::Order::Random ? Shuffle::Keys
265 : Shuffle::None,
266 1000);
267 State.ResumeTiming();
268 }
269 }
270
name__anon482b47ff0111::Insert271 std::string name() const {
272 return "BM_Insert" + baseName() + Mode::name() + Order::name();
273 }
274 };
275
276 template <class Mode, class Hint>
277 struct InsertHint : Base {
278 using Base::Base;
279
280 template < ::Hint hint>
281 typename std::enable_if<hint == ::Hint::Correct>::type
run__anon482b47ff0111::InsertHint282 run(benchmark::State& State) const {
283 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
284 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
285 for (size_t I = 0; I < Data.Maps.size(); ++I) {
286 auto& Map = Data.Maps[I];
287 auto H = Data.Hints[I].begin();
288 for (auto K : Data.Keys) {
289 #ifndef VALIDATE
290 benchmark::DoNotOptimize(Map.insert(*H, std::make_pair(K, 1)));
291 #else
292 auto Inserted = Map.insert(*H, std::make_pair(K, 1));
293 if (Mode() == ::Mode::Hit) {
294 if (Inserted != *H)
295 State.SkipWithError("Inserted a duplicate element");
296 } else {
297 if (++Inserted != *H)
298 State.SkipWithError("Failed to insert a new element");
299 }
300 #endif
301 ++H;
302 }
303 }
304
305 State.PauseTiming();
306 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
307 State.ResumeTiming();
308 }
309 }
310
311 template < ::Hint hint>
312 typename std::enable_if<hint != ::Hint::Correct>::type
run__anon482b47ff0111::InsertHint313 run(benchmark::State& State) const {
314 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
315 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
316 for (size_t I = 0; I < Data.Maps.size(); ++I) {
317 auto& Map = Data.Maps[I];
318 auto Third = *(Data.Hints[I].begin() + 2);
319 for (auto K : Data.Keys) {
320 auto Itor = hint == ::Hint::Begin
321 ? Map.begin()
322 : hint == ::Hint::Third ? Third : Map.end();
323 #ifndef VALIDATE
324 benchmark::DoNotOptimize(Map.insert(Itor, std::make_pair(K, 1)));
325 #else
326 size_t Size = Map.size();
327 Map.insert(Itor, std::make_pair(K, 1));
328 if (Mode() == ::Mode::Hit) {
329 if (Size != Map.size())
330 State.SkipWithError("Inserted a duplicate element");
331 } else {
332 if (Size + 1 != Map.size())
333 State.SkipWithError("Failed to insert a new element");
334 }
335 #endif
336 }
337 }
338
339 State.PauseTiming();
340 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
341 State.ResumeTiming();
342 }
343 }
344
run__anon482b47ff0111::InsertHint345 void run(benchmark::State& State) const {
346 static constexpr auto h = Hint();
347 run<h>(State);
348 }
349
name__anon482b47ff0111::InsertHint350 std::string name() const {
351 return "BM_InsertHint" + baseName() + Mode::name() + Hint::name();
352 }
353 };
354
355 template <class Mode, class Order>
356 struct InsertAssign : Base {
357 using Base::Base;
358
run__anon482b47ff0111::InsertAssign359 void run(benchmark::State& State) const {
360 auto Data = makeTestingSets(
361 MapSize, Mode(),
362 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
363 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
364 for (auto& Map : Data.Maps) {
365 for (auto K : Data.Keys) {
366 #ifndef VALIDATE
367 benchmark::DoNotOptimize(Map.insert_or_assign(K, 1));
368 #else
369 bool Inserted = Map.insert_or_assign(K, 1).second;
370 if (Mode() == ::Mode::Hit) {
371 if (Inserted)
372 State.SkipWithError("Inserted a duplicate element");
373 } else {
374 if (!Inserted)
375 State.SkipWithError("Failed to insert e new element");
376 }
377 #endif
378 }
379 }
380
381 State.PauseTiming();
382 Data = makeTestingSets(MapSize, Mode(),
383 Order::value == ::Order::Random ? Shuffle::Keys
384 : Shuffle::None,
385 1000);
386 State.ResumeTiming();
387 }
388 }
389
name__anon482b47ff0111::InsertAssign390 std::string name() const {
391 return "BM_InsertAssign" + baseName() + Mode::name() + Order::name();
392 }
393 };
394
395 template <class Mode, class Hint>
396 struct InsertAssignHint : Base {
397 using Base::Base;
398
399 template < ::Hint hint>
400 typename std::enable_if<hint == ::Hint::Correct>::type
run__anon482b47ff0111::InsertAssignHint401 run(benchmark::State& State) const {
402 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
403 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
404 for (size_t I = 0; I < Data.Maps.size(); ++I) {
405 auto& Map = Data.Maps[I];
406 auto H = Data.Hints[I].begin();
407 for (auto K : Data.Keys) {
408 #ifndef VALIDATE
409 benchmark::DoNotOptimize(Map.insert_or_assign(*H, K, 1));
410 #else
411 auto Inserted = Map.insert_or_assign(*H, K, 1);
412 if (Mode() == ::Mode::Hit) {
413 if (Inserted != *H)
414 State.SkipWithError("Inserted a duplicate element");
415 } else {
416 if (++Inserted != *H)
417 State.SkipWithError("Failed to insert a new element");
418 }
419 #endif
420 ++H;
421 }
422 }
423
424 State.PauseTiming();
425 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
426 State.ResumeTiming();
427 }
428 }
429
430 template < ::Hint hint>
431 typename std::enable_if<hint != ::Hint::Correct>::type
run__anon482b47ff0111::InsertAssignHint432 run(benchmark::State& State) const {
433 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
434 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
435 for (size_t I = 0; I < Data.Maps.size(); ++I) {
436 auto& Map = Data.Maps[I];
437 auto Third = *(Data.Hints[I].begin() + 2);
438 for (auto K : Data.Keys) {
439 auto Itor = hint == ::Hint::Begin
440 ? Map.begin()
441 : hint == ::Hint::Third ? Third : Map.end();
442 #ifndef VALIDATE
443 benchmark::DoNotOptimize(Map.insert_or_assign(Itor, K, 1));
444 #else
445 size_t Size = Map.size();
446 Map.insert_or_assign(Itor, K, 1);
447 if (Mode() == ::Mode::Hit) {
448 if (Size != Map.size())
449 State.SkipWithError("Inserted a duplicate element");
450 } else {
451 if (Size + 1 != Map.size())
452 State.SkipWithError("Failed to insert a new element");
453 }
454 #endif
455 }
456 }
457
458 State.PauseTiming();
459 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
460 State.ResumeTiming();
461 }
462 }
463
run__anon482b47ff0111::InsertAssignHint464 void run(benchmark::State& State) const {
465 static constexpr auto h = Hint();
466 run<h>(State);
467 }
468
name__anon482b47ff0111::InsertAssignHint469 std::string name() const {
470 return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name();
471 }
472 };
473
474 template <class Mode, class Order>
475 struct Emplace : Base {
476 using Base::Base;
477
run__anon482b47ff0111::Emplace478 void run(benchmark::State& State) const {
479
480 auto Data = makeTestingSets(
481 MapSize, Mode(),
482 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
483 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
484 for (auto& Map : Data.Maps) {
485 for (auto K : Data.Keys) {
486 #ifndef VALIDATE
487 benchmark::DoNotOptimize(Map.emplace(K, 1));
488 #else
489 bool Inserted = Map.emplace(K, 1).second;
490 if (Mode() == ::Mode::Hit) {
491 if (Inserted)
492 State.SkipWithError("Emplaced a duplicate element");
493 } else {
494 if (!Inserted)
495 State.SkipWithError("Failed to emplace a new element");
496 }
497 #endif
498 }
499 }
500
501 State.PauseTiming();
502 Data = makeTestingSets(MapSize, Mode(),
503 Order::value == ::Order::Random ? Shuffle::Keys
504 : Shuffle::None,
505 1000);
506 State.ResumeTiming();
507 }
508 }
509
name__anon482b47ff0111::Emplace510 std::string name() const {
511 return "BM_Emplace" + baseName() + Mode::name() + Order::name();
512 }
513 };
514
515 template <class Mode, class Hint>
516 struct EmplaceHint : Base {
517 using Base::Base;
518
519 template < ::Hint hint>
520 typename std::enable_if<hint == ::Hint::Correct>::type
run__anon482b47ff0111::EmplaceHint521 run(benchmark::State& State) const {
522 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
523 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
524 for (size_t I = 0; I < Data.Maps.size(); ++I) {
525 auto& Map = Data.Maps[I];
526 auto H = Data.Hints[I].begin();
527 for (auto K : Data.Keys) {
528 #ifndef VALIDATE
529 benchmark::DoNotOptimize(Map.emplace_hint(*H, K, 1));
530 #else
531 auto Inserted = Map.emplace_hint(*H, K, 1);
532 if (Mode() == ::Mode::Hit) {
533 if (Inserted != *H)
534 State.SkipWithError("Emplaced a duplicate element");
535 } else {
536 if (++Inserted != *H)
537 State.SkipWithError("Failed to emplace a new element");
538 }
539 #endif
540 ++H;
541 }
542 }
543
544 State.PauseTiming();
545 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
546 State.ResumeTiming();
547 }
548 }
549
550 template < ::Hint hint>
551 typename std::enable_if<hint != ::Hint::Correct>::type
run__anon482b47ff0111::EmplaceHint552 run(benchmark::State& State) const {
553 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
554 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
555 for (size_t I = 0; I < Data.Maps.size(); ++I) {
556 auto& Map = Data.Maps[I];
557 auto Third = *(Data.Hints[I].begin() + 2);
558 for (auto K : Data.Keys) {
559 auto Itor = hint == ::Hint::Begin
560 ? Map.begin()
561 : hint == ::Hint::Third ? Third : Map.end();
562 #ifndef VALIDATE
563 benchmark::DoNotOptimize(Map.emplace_hint(Itor, K, 1));
564 #else
565 size_t Size = Map.size();
566 Map.emplace_hint(Itor, K, 1);
567 if (Mode() == ::Mode::Hit) {
568 if (Size != Map.size())
569 State.SkipWithError("Emplaced a duplicate element");
570 } else {
571 if (Size + 1 != Map.size())
572 State.SkipWithError("Failed to emplace a new element");
573 }
574 #endif
575 }
576 }
577
578 State.PauseTiming();
579 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
580 State.ResumeTiming();
581 }
582 }
583
run__anon482b47ff0111::EmplaceHint584 void run(benchmark::State& State) const {
585 static constexpr auto h = Hint();
586 run<h>(State);
587 }
588
name__anon482b47ff0111::EmplaceHint589 std::string name() const {
590 return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name();
591 }
592 };
593
594 template <class Mode, class Order>
595 struct TryEmplace : Base {
596 using Base::Base;
597
run__anon482b47ff0111::TryEmplace598 void run(benchmark::State& State) const {
599
600 auto Data = makeTestingSets(
601 MapSize, Mode(),
602 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
603 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
604 for (auto& Map : Data.Maps) {
605 for (auto K : Data.Keys) {
606 #ifndef VALIDATE
607 benchmark::DoNotOptimize(Map.try_emplace(K, 1));
608 #else
609 bool Inserted = Map.try_emplace(K, 1).second;
610 if (Mode() == ::Mode::Hit) {
611 if (Inserted)
612 State.SkipWithError("Emplaced a duplicate element");
613 } else {
614 if (!Inserted)
615 State.SkipWithError("Failed to emplace a new element");
616 }
617 #endif
618 }
619 }
620
621 State.PauseTiming();
622 Data = makeTestingSets(MapSize, Mode(),
623 Order::value == ::Order::Random ? Shuffle::Keys
624 : Shuffle::None,
625 1000);
626 State.ResumeTiming();
627 }
628 }
629
name__anon482b47ff0111::TryEmplace630 std::string name() const {
631 return "BM_TryEmplace" + baseName() + Mode::name() + Order::name();
632 }
633 };
634
635 template <class Mode, class Hint>
636 struct TryEmplaceHint : Base {
637 using Base::Base;
638
639 template < ::Hint hint>
640 typename std::enable_if<hint == ::Hint::Correct>::type
run__anon482b47ff0111::TryEmplaceHint641 run(benchmark::State& State) const {
642 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
643 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
644 for (size_t I = 0; I < Data.Maps.size(); ++I) {
645 auto& Map = Data.Maps[I];
646 auto H = Data.Hints[I].begin();
647 for (auto K : Data.Keys) {
648 #ifndef VALIDATE
649 benchmark::DoNotOptimize(Map.try_emplace(*H, K, 1));
650 #else
651 auto Inserted = Map.try_emplace(*H, K, 1);
652 if (Mode() == ::Mode::Hit) {
653 if (Inserted != *H)
654 State.SkipWithError("Emplaced a duplicate element");
655 } else {
656 if (++Inserted != *H)
657 State.SkipWithError("Failed to emplace a new element");
658 }
659 #endif
660 ++H;
661 }
662 }
663
664 State.PauseTiming();
665 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
666 State.ResumeTiming();
667 }
668 }
669
670 template < ::Hint hint>
671 typename std::enable_if<hint != ::Hint::Correct>::type
run__anon482b47ff0111::TryEmplaceHint672 run(benchmark::State& State) const {
673 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
674 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
675 for (size_t I = 0; I < Data.Maps.size(); ++I) {
676 auto& Map = Data.Maps[I];
677 auto Third = *(Data.Hints[I].begin() + 2);
678 for (auto K : Data.Keys) {
679 auto Itor = hint == ::Hint::Begin
680 ? Map.begin()
681 : hint == ::Hint::Third ? Third : Map.end();
682 #ifndef VALIDATE
683 benchmark::DoNotOptimize(Map.try_emplace(Itor, K, 1));
684 #else
685 size_t Size = Map.size();
686 Map.try_emplace(Itor, K, 1);
687 if (Mode() == ::Mode::Hit) {
688 if (Size != Map.size())
689 State.SkipWithError("Emplaced a duplicate element");
690 } else {
691 if (Size + 1 != Map.size())
692 State.SkipWithError("Failed to emplace a new element");
693 }
694 #endif
695 }
696 }
697
698 State.PauseTiming();
699 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000);
700 State.ResumeTiming();
701 }
702 }
703
run__anon482b47ff0111::TryEmplaceHint704 void run(benchmark::State& State) const {
705 static constexpr auto h = Hint();
706 run<h>(State);
707 }
708
name__anon482b47ff0111::TryEmplaceHint709 std::string name() const {
710 return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name();
711 }
712 };
713
714 template <class Mode, class Order>
715 struct Erase : Base {
716 using Base::Base;
717
run__anon482b47ff0111::Erase718 void run(benchmark::State& State) const {
719 auto Data = makeTestingSets(
720 MapSize, Mode(),
721 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000);
722 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
723 for (auto& Map : Data.Maps) {
724 for (auto K : Data.Keys) {
725 #ifndef VALIDATE
726 benchmark::DoNotOptimize(Map.erase(K));
727 #else
728 size_t I = Map.erase(K);
729 if (Mode() == ::Mode::Hit) {
730 if (I == 0)
731 State.SkipWithError("Did not find the existing element");
732 } else {
733 if (I == 1)
734 State.SkipWithError("Did find the non-existing element");
735 }
736 #endif
737 }
738 }
739
740 State.PauseTiming();
741 Data = makeTestingSets(MapSize, Mode(),
742 Order::value == ::Order::Random ? Shuffle::Keys
743 : Shuffle::None,
744 1000);
745 State.ResumeTiming();
746 }
747 }
748
name__anon482b47ff0111::Erase749 std::string name() const {
750 return "BM_Erase" + baseName() + Mode::name() + Order::name();
751 }
752 };
753
754 template <class Order>
755 struct EraseIterator : Base {
756 using Base::Base;
757
run__anon482b47ff0111::EraseIterator758 void run(benchmark::State& State) const {
759 auto Data = makeTestingSets(
760 MapSize, Mode::Hit,
761 Order::value == ::Order::Random ? Shuffle::Hints : Shuffle::None, 1000);
762 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
763 for (size_t I = 0; I < Data.Maps.size(); ++I) {
764 auto& Map = Data.Maps[I];
765 for (auto H : Data.Hints[I]) {
766 benchmark::DoNotOptimize(Map.erase(H));
767 }
768 #ifdef VALIDATE
769 if (!Map.empty())
770 State.SkipWithError("Did not erase the entire map");
771 #endif
772 }
773
774 State.PauseTiming();
775 Data = makeTestingSets(MapSize, Mode::Hit,
776 Order::value == ::Order::Random ? Shuffle::Hints
777 : Shuffle::None,
778 1000);
779 State.ResumeTiming();
780 }
781 }
782
name__anon482b47ff0111::EraseIterator783 std::string name() const {
784 return "BM_EraseIterator" + baseName() + Order::name();
785 }
786 };
787
788 struct EraseRange : Base {
789 using Base::Base;
790
run__anon482b47ff0111::EraseRange791 void run(benchmark::State& State) const {
792 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
793 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
794 for (auto& Map : Data.Maps) {
795 #ifndef VALIDATE
796 benchmark::DoNotOptimize(Map.erase(Map.begin(), Map.end()));
797 #else
798 Map.erase(Map.begin(), Map.end());
799 if (!Map.empty())
800 State.SkipWithError("Did not erase the entire map");
801 #endif
802 }
803
804 State.PauseTiming();
805 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
806 State.ResumeTiming();
807 }
808 }
809
name__anon482b47ff0111::EraseRange810 std::string name() const { return "BM_EraseRange" + baseName(); }
811 };
812
813 //*******************************************************************|
814 // Lookup |
815 //*******************************************************************|
816
817 template <class Mode, class Order>
818 struct Count : Base {
819 using Base::Base;
820
run__anon482b47ff0111::Count821 void run(benchmark::State& State) const {
822 auto Data = makeTestingSets(
823 MapSize, Mode(),
824 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
825 auto& Map = Data.Maps.front();
826 while (State.KeepRunningBatch(MapSize)) {
827 for (auto K : Data.Keys) {
828 #ifndef VALIDATE
829 benchmark::DoNotOptimize(Map.count(K));
830 #else
831 size_t I = Map.count(K);
832 if (Mode() == ::Mode::Hit) {
833 if (I == 0)
834 State.SkipWithError("Did not find the existing element");
835 } else {
836 if (I == 1)
837 State.SkipWithError("Did find the non-existing element");
838 }
839 #endif
840 }
841 }
842 }
843
name__anon482b47ff0111::Count844 std::string name() const {
845 return "BM_Count" + baseName() + Mode::name() + Order::name();
846 }
847 };
848
849 template <class Mode, class Order>
850 struct Find : Base {
851 using Base::Base;
852
run__anon482b47ff0111::Find853 void run(benchmark::State& State) const {
854 auto Data = makeTestingSets(
855 MapSize, Mode(),
856 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
857 auto& Map = Data.Maps.front();
858 while (State.KeepRunningBatch(MapSize)) {
859 for (auto K : Data.Keys) {
860 #ifndef VALIDATE
861 benchmark::DoNotOptimize(Map.find(K));
862 #else
863 auto Itor = Map.find(K);
864 if (Mode() == ::Mode::Hit) {
865 if (Itor == Map.end())
866 State.SkipWithError("Did not find the existing element");
867 } else {
868 if (Itor != Map.end())
869 State.SkipWithError("Did find the non-existing element");
870 }
871 #endif
872 }
873 }
874 }
875
name__anon482b47ff0111::Find876 std::string name() const {
877 return "BM_Find" + baseName() + Mode::name() + Order::name();
878 }
879 };
880
881 template <class Mode, class Order>
882 struct EqualRange : Base {
883 using Base::Base;
884
run__anon482b47ff0111::EqualRange885 void run(benchmark::State& State) const {
886 auto Data = makeTestingSets(
887 MapSize, Mode(),
888 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
889 auto& Map = Data.Maps.front();
890 while (State.KeepRunningBatch(MapSize)) {
891 for (auto K : Data.Keys) {
892 #ifndef VALIDATE
893 benchmark::DoNotOptimize(Map.equal_range(K));
894 #else
895 auto Range = Map.equal_range(K);
896 if (Mode() == ::Mode::Hit) {
897 // Adjust validation for the last element.
898 auto Key = K;
899 if (Range.second == Map.end() && K == 2 * MapSize) {
900 --Range.second;
901 Key -= 2;
902 }
903 if (Range.first == Map.end() || Range.first->first != K ||
904 Range.second == Map.end() || Range.second->first - 2 != Key)
905 State.SkipWithError("Did not find the existing element");
906 } else {
907 if (Range.first == Map.end() || Range.first->first - 1 != K ||
908 Range.second == Map.end() || Range.second->first - 1 != K)
909 State.SkipWithError("Did find the non-existing element");
910 }
911 #endif
912 }
913 }
914 }
915
name__anon482b47ff0111::EqualRange916 std::string name() const {
917 return "BM_EqualRange" + baseName() + Mode::name() + Order::name();
918 }
919 };
920
921 template <class Mode, class Order>
922 struct LowerBound : Base {
923 using Base::Base;
924
run__anon482b47ff0111::LowerBound925 void run(benchmark::State& State) const {
926 auto Data = makeTestingSets(
927 MapSize, Mode(),
928 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
929 auto& Map = Data.Maps.front();
930 while (State.KeepRunningBatch(MapSize)) {
931 for (auto K : Data.Keys) {
932 #ifndef VALIDATE
933 benchmark::DoNotOptimize(Map.lower_bound(K));
934 #else
935 auto Itor = Map.lower_bound(K);
936 if (Mode() == ::Mode::Hit) {
937 if (Itor == Map.end() || Itor->first != K)
938 State.SkipWithError("Did not find the existing element");
939 } else {
940 if (Itor == Map.end() || Itor->first - 1 != K)
941 State.SkipWithError("Did find the non-existing element");
942 }
943 #endif
944 }
945 }
946 }
947
name__anon482b47ff0111::LowerBound948 std::string name() const {
949 return "BM_LowerBound" + baseName() + Mode::name() + Order::name();
950 }
951 };
952
953 template <class Mode, class Order>
954 struct UpperBound : Base {
955 using Base::Base;
956
run__anon482b47ff0111::UpperBound957 void run(benchmark::State& State) const {
958 auto Data = makeTestingSets(
959 MapSize, Mode(),
960 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1);
961 auto& Map = Data.Maps.front();
962 while (State.KeepRunningBatch(MapSize)) {
963 for (auto K : Data.Keys) {
964 #ifndef VALIDATE
965 benchmark::DoNotOptimize(Map.upper_bound(K));
966 #else
967 std::map<uint64_t, int64_t>::iterator Itor = Map.upper_bound(K);
968 if (Mode() == ::Mode::Hit) {
969 // Adjust validation for the last element.
970 auto Key = K;
971 if (Itor == Map.end() && K == 2 * MapSize) {
972 --Itor;
973 Key -= 2;
974 }
975 if (Itor == Map.end() || Itor->first - 2 != Key)
976 State.SkipWithError("Did not find the existing element");
977 } else {
978 if (Itor == Map.end() || Itor->first - 1 != K)
979 State.SkipWithError("Did find the non-existing element");
980 }
981 #endif
982 }
983 }
984 }
985
name__anon482b47ff0111::UpperBound986 std::string name() const {
987 return "BM_UpperBound" + baseName() + Mode::name() + Order::name();
988 }
989 };
990
991 } // namespace
992
main(int argc,char ** argv)993 int main(int argc, char** argv) {
994 benchmark::Initialize(&argc, argv);
995 if (benchmark::ReportUnrecognizedArguments(argc, argv))
996 return 1;
997
998 #ifdef VALIDATE
999 const std::vector<size_t> MapSize{10};
1000 #else
1001 const std::vector<size_t> MapSize{10, 100, 1000, 10000, 100000, 1000000};
1002 #endif
1003
1004 // Member functions
1005 makeCartesianProductBenchmark<ConstructorDefault>();
1006 makeCartesianProductBenchmark<ConstructorIterator>(MapSize);
1007 makeCartesianProductBenchmark<ConstructorCopy>(MapSize);
1008 makeCartesianProductBenchmark<ConstructorMove>(MapSize);
1009
1010 // Capacity
1011 makeCartesianProductBenchmark<Empty>(MapSize);
1012 makeCartesianProductBenchmark<Size>(MapSize);
1013
1014 // Modifiers
1015 makeCartesianProductBenchmark<Clear>(MapSize);
1016 makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(MapSize);
1017 makeCartesianProductBenchmark<InsertHint, AllModes, AllHints>(MapSize);
1018 makeCartesianProductBenchmark<InsertAssign, AllModes, AllOrders>(MapSize);
1019 makeCartesianProductBenchmark<InsertAssignHint, AllModes, AllHints>(MapSize);
1020
1021 makeCartesianProductBenchmark<Emplace, AllModes, AllOrders>(MapSize);
1022 makeCartesianProductBenchmark<EmplaceHint, AllModes, AllHints>(MapSize);
1023 makeCartesianProductBenchmark<TryEmplace, AllModes, AllOrders>(MapSize);
1024 makeCartesianProductBenchmark<TryEmplaceHint, AllModes, AllHints>(MapSize);
1025 makeCartesianProductBenchmark<Erase, AllModes, AllOrders>(MapSize);
1026 makeCartesianProductBenchmark<EraseIterator, AllOrders>(MapSize);
1027 makeCartesianProductBenchmark<EraseRange>(MapSize);
1028
1029 // Lookup
1030 makeCartesianProductBenchmark<Count, AllModes, AllOrders>(MapSize);
1031 makeCartesianProductBenchmark<Find, AllModes, AllOrders>(MapSize);
1032 makeCartesianProductBenchmark<EqualRange, AllModes, AllOrders>(MapSize);
1033 makeCartesianProductBenchmark<LowerBound, AllModes, AllOrders>(MapSize);
1034 makeCartesianProductBenchmark<UpperBound, AllModes, AllOrders>(MapSize);
1035
1036 benchmark::RunSpecifiedBenchmarks();
1037 }
1038