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 
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;
91   Base(size_t T) : MapSize(T) {}
92 
93   std::string baseName() const { return "_MapSize=" + std::to_string(MapSize); }
94 };
95 
96 //*******************************************************************|
97 //                       Member functions                            |
98 //*******************************************************************|
99 
100 struct ConstructorDefault {
101   void run(benchmark::State& State) const {
102     for (auto _ : State) {
103       benchmark::DoNotOptimize(std::map<uint64_t, int64_t>());
104     }
105   }
106 
107   std::string name() const { return "BM_ConstructorDefault"; }
108 };
109 
110 struct ConstructorIterator : Base {
111   using Base::Base;
112 
113   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 
128   std::string name() const { return "BM_ConstructorIterator" + baseName(); }
129 };
130 
131 struct ConstructorCopy : Base {
132   using Base::Base;
133 
134   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 
149   std::string name() const { return "BM_ConstructorCopy" + baseName(); }
150 };
151 
152 struct ConstructorMove : Base {
153   using Base::Base;
154 
155   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 
168   std::string name() const { return "BM_ConstructorMove" + baseName(); }
169 };
170 
171 //*******************************************************************|
172 //                           Capacity                                |
173 //*******************************************************************|
174 
175 struct Empty : Base {
176   using Base::Base;
177 
178   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 
191   std::string name() const { return "BM_Empty" + baseName(); }
192 };
193 
194 struct Size : Base {
195   using Base::Base;
196 
197   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 
210   std::string name() const { return "BM_Size" + baseName(); }
211 };
212 
213 //*******************************************************************|
214 //                           Modifiers                               |
215 //*******************************************************************|
216 
217 struct Clear : Base {
218   using Base::Base;
219 
220   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 
233   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 
240   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 
271   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
282   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
313   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 
345   void run(benchmark::State& State) const {
346     static constexpr auto h = Hint();
347     run<h>(State);
348   }
349 
350   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 
359   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 
390   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
401   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
432   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 
464   void run(benchmark::State& State) const {
465     static constexpr auto h = Hint();
466     run<h>(State);
467   }
468 
469   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 
478   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 
510   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
521   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
552   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 
584   void run(benchmark::State& State) const {
585     static constexpr auto h = Hint();
586     run<h>(State);
587   }
588 
589   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 
598   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 
630   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
641   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
672   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 
704   void run(benchmark::State& State) const {
705     static constexpr auto h = Hint();
706     run<h>(State);
707   }
708 
709   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 
718   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 
749   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 
758   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 
783   std::string name() const {
784     return "BM_EraseIterator" + baseName() + Order::name();
785   }
786 };
787 
788 struct EraseRange : Base {
789   using Base::Base;
790 
791   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 
810   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 
821   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 
844   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 
853   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 
876   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 
885   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 
916   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 
925   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 
948   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 
957   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 
986   std::string name() const {
987     return "BM_UpperBound" + baseName() + Mode::name() + Order::name();
988   }
989 };
990 
991 } // namespace
992 
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