1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include <algorithm>
11 #include <cstdint>
12 #include <memory>
13 #include <random>
14 #include <set>
15 #include <string>
16 #include <vector>
17
18 #include "CartesianBenchmarks.hpp"
19 #include "benchmark/benchmark.h"
20 #include "test_macros.h"
21
22 namespace {
23
24 enum class HitType { Hit, Miss };
25
26 struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> {
27 static constexpr const char* Names[] = {"Hit", "Miss"};
28 };
29
30 enum class AccessPattern { Ordered, Random };
31
32 struct AllAccessPattern
33 : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
34 static constexpr const char* Names[] = {"Ordered", "Random"};
35 };
36
sortKeysBy(std::vector<uint64_t> & Keys,AccessPattern AP)37 void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
38 if (AP == AccessPattern::Random) {
39 std::random_device R;
40 std::mt19937 M(R());
41 std::shuffle(std::begin(Keys), std::end(Keys), M);
42 }
43 }
44
45 struct TestSets {
46 std::vector<std::set<uint64_t> > Sets;
47 std::vector<uint64_t> Keys;
48 };
49
makeTestingSets(size_t TableSize,size_t NumTables,HitType Hit,AccessPattern Access)50 TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit,
51 AccessPattern Access) {
52 TestSets R;
53 R.Sets.resize(1);
54
55 for (uint64_t I = 0; I < TableSize; ++I) {
56 R.Sets[0].insert(2 * I);
57 R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
58 }
59 R.Sets.resize(NumTables, R.Sets[0]);
60 sortKeysBy(R.Keys, Access);
61
62 return R;
63 }
64
65 struct Base {
66 size_t TableSize;
67 size_t NumTables;
Base__anon8cbba7860111::Base68 Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
69
skip__anon8cbba7860111::Base70 bool skip() const {
71 size_t Total = TableSize * NumTables;
72 return Total < 100 || Total > 1000000;
73 }
74
baseName__anon8cbba7860111::Base75 std::string baseName() const {
76 return "_TableSize" + std::to_string(TableSize) + "_NumTables" +
77 std::to_string(NumTables);
78 }
79 };
80
81 template <class Access>
82 struct Create : Base {
83 using Base::Base;
84
run__anon8cbba7860111::Create85 void run(benchmark::State& State) const {
86 std::vector<uint64_t> Keys(TableSize);
87 std::iota(Keys.begin(), Keys.end(), uint64_t{0});
88 sortKeysBy(Keys, Access());
89
90 while (State.KeepRunningBatch(TableSize * NumTables)) {
91 std::vector<std::set<uint64_t>> Sets(NumTables);
92 for (auto K : Keys) {
93 for (auto& Set : Sets) {
94 benchmark::DoNotOptimize(Set.insert(K));
95 }
96 }
97 }
98 }
99
name__anon8cbba7860111::Create100 std::string name() const {
101 return "BM_Create" + Access::name() + baseName();
102 }
103 };
104
105 template <class Hit, class Access>
106 struct Find : Base {
107 using Base::Base;
108
run__anon8cbba7860111::Find109 void run(benchmark::State& State) const {
110 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
111
112 while (State.KeepRunningBatch(TableSize * NumTables)) {
113 for (auto K : Data.Keys) {
114 for (auto& Set : Data.Sets) {
115 benchmark::DoNotOptimize(Set.find(K));
116 }
117 }
118 }
119 }
120
name__anon8cbba7860111::Find121 std::string name() const {
122 return "BM_Find" + Hit::name() + Access::name() + baseName();
123 }
124 };
125
126 template <class Hit, class Access>
127 struct FindNeEnd : Base {
128 using Base::Base;
129
run__anon8cbba7860111::FindNeEnd130 void run(benchmark::State& State) const {
131 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
132
133 while (State.KeepRunningBatch(TableSize * NumTables)) {
134 for (auto K : Data.Keys) {
135 for (auto& Set : Data.Sets) {
136 benchmark::DoNotOptimize(Set.find(K) != Set.end());
137 }
138 }
139 }
140 }
141
name__anon8cbba7860111::FindNeEnd142 std::string name() const {
143 return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName();
144 }
145 };
146
147 template <class Access>
148 struct InsertHit : Base {
149 using Base::Base;
150
run__anon8cbba7860111::InsertHit151 void run(benchmark::State& State) const {
152 auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
153
154 while (State.KeepRunningBatch(TableSize * NumTables)) {
155 for (auto K : Data.Keys) {
156 for (auto& Set : Data.Sets) {
157 benchmark::DoNotOptimize(Set.insert(K));
158 }
159 }
160 }
161 }
162
name__anon8cbba7860111::InsertHit163 std::string name() const {
164 return "BM_InsertHit" + Access::name() + baseName();
165 }
166 };
167
168 template <class Access>
169 struct InsertMissAndErase : Base {
170 using Base::Base;
171
run__anon8cbba7860111::InsertMissAndErase172 void run(benchmark::State& State) const {
173 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
174
175 while (State.KeepRunningBatch(TableSize * NumTables)) {
176 for (auto K : Data.Keys) {
177 for (auto& Set : Data.Sets) {
178 benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
179 }
180 }
181 }
182 }
183
name__anon8cbba7860111::InsertMissAndErase184 std::string name() const {
185 return "BM_InsertMissAndErase" + Access::name() + baseName();
186 }
187 };
188
189 struct IterateRangeFor : Base {
190 using Base::Base;
191
run__anon8cbba7860111::IterateRangeFor192 void run(benchmark::State& State) const {
193 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
194 AccessPattern::Ordered);
195
196 while (State.KeepRunningBatch(TableSize * NumTables)) {
197 for (auto& Set : Data.Sets) {
198 for (auto& V : Set) {
199 benchmark::DoNotOptimize(V);
200 }
201 }
202 }
203 }
204
name__anon8cbba7860111::IterateRangeFor205 std::string name() const { return "BM_IterateRangeFor" + baseName(); }
206 };
207
208 struct IterateBeginEnd : Base {
209 using Base::Base;
210
run__anon8cbba7860111::IterateBeginEnd211 void run(benchmark::State& State) const {
212 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
213 AccessPattern::Ordered);
214
215 while (State.KeepRunningBatch(TableSize * NumTables)) {
216 for (auto& Set : Data.Sets) {
217 for (auto it = Set.begin(); it != Set.end(); ++it) {
218 benchmark::DoNotOptimize(*it);
219 }
220 }
221 }
222 }
223
name__anon8cbba7860111::IterateBeginEnd224 std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
225 };
226
227 } // namespace
228
main(int argc,char ** argv)229 int main(int argc, char** argv) {
230 benchmark::Initialize(&argc, argv);
231 if (benchmark::ReportUnrecognizedArguments(argc, argv))
232 return 1;
233
234 const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
235 const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
236
237 makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
238 makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(
239 TableSize, NumTables);
240 makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(
241 TableSize, NumTables);
242 makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(
243 TableSize, NumTables);
244 makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(
245 TableSize, NumTables);
246 makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
247 makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
248 benchmark::RunSpecifiedBenchmarks();
249 }
250