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<std::vector<typename std::map<uint64_t, int64_t>::const_iterator> > Hints;
54 };
55
56 enum class Shuffle { None, Keys, Hints };
57
makeTestingSets(size_t MapSize,Mode mode,Shuffle shuffle,size_t max_maps)58 TestSets 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
86 struct Base {
87 size_t MapSize;
Base__anon83464c5a0111::Base88 Base(size_t T) : MapSize(T) {}
89
baseName__anon83464c5a0111::Base90 std::string baseName() const { return "_MapSize=" + std::to_string(MapSize); }
91 };
92
93 //*******************************************************************|
94 // Member functions |
95 //*******************************************************************|
96
97 struct ConstructorDefault {
run__anon83464c5a0111::ConstructorDefault98 void run(benchmark::State& State) const {
99 for (auto _ : State) {
100 benchmark::DoNotOptimize(std::map<uint64_t, int64_t>());
101 }
102 }
103
name__anon83464c5a0111::ConstructorDefault104 std::string name() const { return "BM_ConstructorDefault"; }
105 };
106
107 struct ConstructorIterator : Base {
108 using Base::Base;
109
run__anon83464c5a0111::ConstructorIterator110 void run(benchmark::State& State) const {
111 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
112 auto& Map = Data.Maps.front();
113 while (State.KeepRunningBatch(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
name__anon83464c5a0111::ConstructorIterator124 std::string name() const { return "BM_ConstructorIterator" + baseName(); }
125 };
126
127 struct ConstructorCopy : Base {
128 using Base::Base;
129
run__anon83464c5a0111::ConstructorCopy130 void run(benchmark::State& State) const {
131 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
132 auto& Map = Data.Maps.front();
133 while (State.KeepRunningBatch(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
name__anon83464c5a0111::ConstructorCopy145 std::string name() const { return "BM_ConstructorCopy" + baseName(); }
146 };
147
148 struct ConstructorMove : Base {
149 using Base::Base;
150
run__anon83464c5a0111::ConstructorMove151 void run(benchmark::State& State) const {
152 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
153 while (State.KeepRunningBatch(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::Hit, Shuffle::None, 1000);
160 State.ResumeTiming();
161 }
162 }
163
name__anon83464c5a0111::ConstructorMove164 std::string name() const { return "BM_ConstructorMove" + baseName(); }
165 };
166
167 //*******************************************************************|
168 // Capacity |
169 //*******************************************************************|
170
171 struct Empty : Base {
172 using Base::Base;
173
run__anon83464c5a0111::Empty174 void run(benchmark::State& State) const {
175 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 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
name__anon83464c5a0111::Empty187 std::string name() const { return "BM_Empty" + baseName(); }
188 };
189
190 struct Size : Base {
191 using Base::Base;
192
run__anon83464c5a0111::Size193 void run(benchmark::State& State) const {
194 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 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
name__anon83464c5a0111::Size206 std::string name() const { return "BM_Size" + baseName(); }
207 };
208
209 //*******************************************************************|
210 // Modifiers |
211 //*******************************************************************|
212
213 struct Clear : Base {
214 using Base::Base;
215
run__anon83464c5a0111::Clear216 void run(benchmark::State& State) const {
217 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
218 while (State.KeepRunningBatch(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::Hit, Shuffle::None, 1000);
225 State.ResumeTiming();
226 }
227 }
228
name__anon83464c5a0111::Clear229 std::string name() const { return "BM_Clear" + baseName(); }
230 };
231
232 template <class Mode, class Order>
233 struct Insert : Base {
234 using Base::Base;
235
run__anon83464c5a0111::Insert236 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(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
name__anon83464c5a0111::Insert262 std::string name() const { return "BM_Insert" + baseName() + Mode::name() + Order::name(); }
263 };
264
265 template <class Mode, class Hint>
266 struct InsertHint : Base {
267 using Base::Base;
268
269 template < ::Hint hint>
run__anon83464c5a0111::InsertHint270 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(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>
run__anon83464c5a0111::InsertHint300 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(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
run__anon83464c5a0111::InsertHint330 void run(benchmark::State& State) const {
331 static constexpr auto h = Hint();
332 run<h>(State);
333 }
334
name__anon83464c5a0111::InsertHint335 std::string name() const { return "BM_InsertHint" + baseName() + Mode::name() + Hint::name(); }
336 };
337
338 template <class Mode, class Order>
339 struct InsertAssign : Base {
340 using Base::Base;
341
run__anon83464c5a0111::InsertAssign342 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(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
name__anon83464c5a0111::InsertAssign368 std::string name() const { return "BM_InsertAssign" + baseName() + Mode::name() + Order::name(); }
369 };
370
371 template <class Mode, class Hint>
372 struct InsertAssignHint : Base {
373 using Base::Base;
374
375 template < ::Hint hint>
run__anon83464c5a0111::InsertAssignHint376 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(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>
run__anon83464c5a0111::InsertAssignHint406 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(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
run__anon83464c5a0111::InsertAssignHint436 void run(benchmark::State& State) const {
437 static constexpr auto h = Hint();
438 run<h>(State);
439 }
440
name__anon83464c5a0111::InsertAssignHint441 std::string name() const { return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name(); }
442 };
443
444 template <class Mode, class Order>
445 struct Emplace : Base {
446 using Base::Base;
447
run__anon83464c5a0111::Emplace448 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(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
name__anon83464c5a0111::Emplace474 std::string name() const { return "BM_Emplace" + baseName() + Mode::name() + Order::name(); }
475 };
476
477 template <class Mode, class Hint>
478 struct EmplaceHint : Base {
479 using Base::Base;
480
481 template < ::Hint hint>
run__anon83464c5a0111::EmplaceHint482 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(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>
run__anon83464c5a0111::EmplaceHint512 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(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
run__anon83464c5a0111::EmplaceHint542 void run(benchmark::State& State) const {
543 static constexpr auto h = Hint();
544 run<h>(State);
545 }
546
name__anon83464c5a0111::EmplaceHint547 std::string name() const { return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name(); }
548 };
549
550 template <class Mode, class Order>
551 struct TryEmplace : Base {
552 using Base::Base;
553
run__anon83464c5a0111::TryEmplace554 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(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
name__anon83464c5a0111::TryEmplace580 std::string name() const { return "BM_TryEmplace" + baseName() + Mode::name() + Order::name(); }
581 };
582
583 template <class Mode, class Hint>
584 struct TryEmplaceHint : Base {
585 using Base::Base;
586
587 template < ::Hint hint>
run__anon83464c5a0111::TryEmplaceHint588 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(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>
run__anon83464c5a0111::TryEmplaceHint618 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(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
run__anon83464c5a0111::TryEmplaceHint648 void run(benchmark::State& State) const {
649 static constexpr auto h = Hint();
650 run<h>(State);
651 }
652
name__anon83464c5a0111::TryEmplaceHint653 std::string name() const { return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name(); }
654 };
655
656 template <class Mode, class Order>
657 struct Erase : Base {
658 using Base::Base;
659
run__anon83464c5a0111::Erase660 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(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
name__anon83464c5a0111::Erase686 std::string name() const { return "BM_Erase" + baseName() + Mode::name() + Order::name(); }
687 };
688
689 template <class Order>
690 struct EraseIterator : Base {
691 using Base::Base;
692
run__anon83464c5a0111::EraseIterator693 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(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
name__anon83464c5a0111::EraseIterator715 std::string name() const { return "BM_EraseIterator" + baseName() + Order::name(); }
716 };
717
718 struct EraseRange : Base {
719 using Base::Base;
720
run__anon83464c5a0111::EraseRange721 void run(benchmark::State& State) const {
722 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
723 while (State.KeepRunningBatch(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::Hit, Shuffle::None, 1000);
736 State.ResumeTiming();
737 }
738 }
739
name__anon83464c5a0111::EraseRange740 std::string name() const { return "BM_EraseRange" + baseName(); }
741 };
742
743 //*******************************************************************|
744 // Lookup |
745 //*******************************************************************|
746
747 template <class Mode, class Order>
748 struct Count : Base {
749 using Base::Base;
750
run__anon83464c5a0111::Count751 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(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
name__anon83464c5a0111::Count772 std::string name() const { return "BM_Count" + baseName() + Mode::name() + Order::name(); }
773 };
774
775 template <class Mode, class Order>
776 struct Find : Base {
777 using Base::Base;
778
run__anon83464c5a0111::Find779 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(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
name__anon83464c5a0111::Find800 std::string name() const { return "BM_Find" + baseName() + Mode::name() + Order::name(); }
801 };
802
803 template <class Mode, class Order>
804 struct EqualRange : Base {
805 using Base::Base;
806
run__anon83464c5a0111::EqualRange807 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(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
name__anon83464c5a0111::EqualRange836 std::string name() const { return "BM_EqualRange" + baseName() + Mode::name() + Order::name(); }
837 };
838
839 template <class Mode, class Order>
840 struct LowerBound : Base {
841 using Base::Base;
842
run__anon83464c5a0111::LowerBound843 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(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
name__anon83464c5a0111::LowerBound864 std::string name() const { return "BM_LowerBound" + baseName() + Mode::name() + Order::name(); }
865 };
866
867 template <class Mode, class Order>
868 struct UpperBound : Base {
869 using Base::Base;
870
run__anon83464c5a0111::UpperBound871 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(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
name__anon83464c5a0111::UpperBound898 std::string name() const { return "BM_UpperBound" + baseName() + Mode::name() + Order::name(); }
899 };
900
901 } // namespace
902
main(int argc,char ** argv)903 int main(int argc, char** argv) {
904 benchmark::Initialize(&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>(MapSize);
917 makeCartesianProductBenchmark<ConstructorCopy>(MapSize);
918 makeCartesianProductBenchmark<ConstructorMove>(MapSize);
919
920 // Capacity
921 makeCartesianProductBenchmark<Empty>(MapSize);
922 makeCartesianProductBenchmark<Size>(MapSize);
923
924 // Modifiers
925 makeCartesianProductBenchmark<Clear>(MapSize);
926 makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(MapSize);
927 makeCartesianProductBenchmark<InsertHint, AllModes, AllHints>(MapSize);
928 makeCartesianProductBenchmark<InsertAssign, AllModes, AllOrders>(MapSize);
929 makeCartesianProductBenchmark<InsertAssignHint, AllModes, AllHints>(MapSize);
930
931 makeCartesianProductBenchmark<Emplace, AllModes, AllOrders>(MapSize);
932 makeCartesianProductBenchmark<EmplaceHint, AllModes, AllHints>(MapSize);
933 makeCartesianProductBenchmark<TryEmplace, AllModes, AllOrders>(MapSize);
934 makeCartesianProductBenchmark<TryEmplaceHint, AllModes, AllHints>(MapSize);
935 makeCartesianProductBenchmark<Erase, AllModes, AllOrders>(MapSize);
936 makeCartesianProductBenchmark<EraseIterator, AllOrders>(MapSize);
937 makeCartesianProductBenchmark<EraseRange>(MapSize);
938
939 // Lookup
940 makeCartesianProductBenchmark<Count, AllModes, AllOrders>(MapSize);
941 makeCartesianProductBenchmark<Find, AllModes, AllOrders>(MapSize);
942 makeCartesianProductBenchmark<EqualRange, AllModes, AllOrders>(MapSize);
943 makeCartesianProductBenchmark<LowerBound, AllModes, AllOrders>(MapSize);
944 makeCartesianProductBenchmark<UpperBound, AllModes, AllOrders>(MapSize);
945
946 benchmark::RunSpecifiedBenchmarks();
947 }
948