1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef BENCHMARK_CONTAINER_BENCHMARKS_H
11 #define BENCHMARK_CONTAINER_BENCHMARKS_H
12
13 #include <cassert>
14
15 #include "Utilities.h"
16 #include "benchmark/benchmark.h"
17
18 namespace ContainerBenchmarks {
19
20 template <class Container>
BM_ConstructSize(benchmark::State & st,Container)21 void BM_ConstructSize(benchmark::State& st, Container) {
22 auto size = st.range(0);
23 for (auto _ : st) {
24 Container c(size);
25 DoNotOptimizeData(c);
26 }
27 }
28
29 template <class Container>
BM_ConstructSizeValue(benchmark::State & st,Container,typename Container::value_type const & val)30 void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
31 const auto size = st.range(0);
32 for (auto _ : st) {
33 Container c(size, val);
34 DoNotOptimizeData(c);
35 }
36 }
37
38 template <class Container, class GenInputs>
BM_ConstructIterIter(benchmark::State & st,Container,GenInputs gen)39 void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
40 auto in = gen(st.range(0));
41 const auto begin = in.begin();
42 const auto end = in.end();
43 benchmark::DoNotOptimize(&in);
44 while (st.KeepRunning()) {
45 Container c(begin, end);
46 DoNotOptimizeData(c);
47 }
48 }
49
50 template <class Container, class GenInputs>
BM_InsertValue(benchmark::State & st,Container c,GenInputs gen)51 void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
52 auto in = gen(st.range(0));
53 const auto end = in.end();
54 while (st.KeepRunning()) {
55 c.clear();
56 for (auto it = in.begin(); it != end; ++it) {
57 benchmark::DoNotOptimize(&(*c.insert(*it).first));
58 }
59 benchmark::ClobberMemory();
60 }
61 }
62
63 template <class Container, class GenInputs>
BM_InsertValueRehash(benchmark::State & st,Container c,GenInputs gen)64 void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
65 auto in = gen(st.range(0));
66 const auto end = in.end();
67 while (st.KeepRunning()) {
68 c.clear();
69 c.rehash(16);
70 for (auto it = in.begin(); it != end; ++it) {
71 benchmark::DoNotOptimize(&(*c.insert(*it).first));
72 }
73 benchmark::ClobberMemory();
74 }
75 }
76
77
78 template <class Container, class GenInputs>
BM_InsertDuplicate(benchmark::State & st,Container c,GenInputs gen)79 void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
80 auto in = gen(st.range(0));
81 const auto end = in.end();
82 c.insert(in.begin(), in.end());
83 benchmark::DoNotOptimize(&c);
84 benchmark::DoNotOptimize(&in);
85 while (st.KeepRunning()) {
86 for (auto it = in.begin(); it != end; ++it) {
87 benchmark::DoNotOptimize(&(*c.insert(*it).first));
88 }
89 benchmark::ClobberMemory();
90 }
91 }
92
93
94 template <class Container, class GenInputs>
BM_EmplaceDuplicate(benchmark::State & st,Container c,GenInputs gen)95 void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
96 auto in = gen(st.range(0));
97 const auto end = in.end();
98 c.insert(in.begin(), in.end());
99 benchmark::DoNotOptimize(&c);
100 benchmark::DoNotOptimize(&in);
101 while (st.KeepRunning()) {
102 for (auto it = in.begin(); it != end; ++it) {
103 benchmark::DoNotOptimize(&(*c.emplace(*it).first));
104 }
105 benchmark::ClobberMemory();
106 }
107 }
108
109 template <class Container, class GenInputs>
BM_Find(benchmark::State & st,Container c,GenInputs gen)110 static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
111 auto in = gen(st.range(0));
112 c.insert(in.begin(), in.end());
113 benchmark::DoNotOptimize(&(*c.begin()));
114 const auto end = in.data() + in.size();
115 while (st.KeepRunning()) {
116 for (auto it = in.data(); it != end; ++it) {
117 benchmark::DoNotOptimize(&(*c.find(*it)));
118 }
119 benchmark::ClobberMemory();
120 }
121 }
122
123 template <class Container, class GenInputs>
BM_FindRehash(benchmark::State & st,Container c,GenInputs gen)124 static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
125 c.rehash(8);
126 auto in = gen(st.range(0));
127 c.insert(in.begin(), in.end());
128 benchmark::DoNotOptimize(&(*c.begin()));
129 const auto end = in.data() + in.size();
130 while (st.KeepRunning()) {
131 for (auto it = in.data(); it != end; ++it) {
132 benchmark::DoNotOptimize(&(*c.find(*it)));
133 }
134 benchmark::ClobberMemory();
135 }
136 }
137
138 template <class Container, class GenInputs>
BM_Rehash(benchmark::State & st,Container c,GenInputs gen)139 static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
140 auto in = gen(st.range(0));
141 c.max_load_factor(3.0);
142 c.insert(in.begin(), in.end());
143 benchmark::DoNotOptimize(c);
144 const auto bucket_count = c.bucket_count();
145 while (st.KeepRunning()) {
146 c.rehash(bucket_count + 1);
147 c.rehash(bucket_count);
148 benchmark::ClobberMemory();
149 }
150 }
151
152 } // end namespace ContainerBenchmarks
153
154 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H
155