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 <memory>
12 #include <random>
13 #include <set>
14 #include <string>
15 #include <vector>
16
17 #include "CartesianBenchmarks.h"
18 #include "benchmark/benchmark.h"
19 #include "test_macros.h"
20
21 namespace {
22
23 enum class HitType { Hit, Miss };
24
25 struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> {
26 static constexpr const char* Names[] = {"Hit", "Miss"};
27 };
28
29 enum class AccessPattern { Ordered, Random };
30
31 struct AllAccessPattern
32 : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
33 static constexpr const char* Names[] = {"Ordered", "Random"};
34 };
35
sortKeysBy(std::vector<uint64_t> & Keys,AccessPattern AP)36 void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
37 if (AP == AccessPattern::Random) {
38 std::random_device R;
39 std::mt19937 M(R());
40 std::shuffle(std::begin(Keys), std::end(Keys), M);
41 }
42 }
43
44 struct TestSets {
45 std::vector<std::set<uint64_t> > Sets;
46 std::vector<uint64_t> Keys;
47 };
48
makeTestingSets(size_t TableSize,size_t NumTables,HitType Hit,AccessPattern Access)49 TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit,
50 AccessPattern Access) {
51 TestSets R;
52 R.Sets.resize(1);
53
54 for (uint64_t I = 0; I < TableSize; ++I) {
55 R.Sets[0].insert(2 * I);
56 R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
57 }
58 R.Sets.resize(NumTables, R.Sets[0]);
59 sortKeysBy(R.Keys, Access);
60
61 return R;
62 }
63
64 struct Base {
65 size_t TableSize;
66 size_t NumTables;
Base__anond5c0e82f0111::Base67 Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
68
skip__anond5c0e82f0111::Base69 bool skip() const {
70 size_t Total = TableSize * NumTables;
71 return Total < 100 || Total > 1000000;
72 }
73
baseName__anond5c0e82f0111::Base74 std::string baseName() const {
75 return "_TableSize" + std::to_string(TableSize) + "_NumTables" +
76 std::to_string(NumTables);
77 }
78 };
79
80 template <class Access>
81 struct Create : Base {
82 using Base::Base;
83
run__anond5c0e82f0111::Create84 void run(benchmark::State& State) const {
85 std::vector<uint64_t> Keys(TableSize);
86 std::iota(Keys.begin(), Keys.end(), uint64_t{0});
87 sortKeysBy(Keys, Access());
88
89 while (State.KeepRunningBatch(TableSize * NumTables)) {
90 std::vector<std::set<uint64_t>> Sets(NumTables);
91 for (auto K : Keys) {
92 for (auto& Set : Sets) {
93 benchmark::DoNotOptimize(Set.insert(K));
94 }
95 }
96 }
97 }
98
name__anond5c0e82f0111::Create99 std::string name() const {
100 return "BM_Create" + Access::name() + baseName();
101 }
102 };
103
104 template <class Hit, class Access>
105 struct Find : Base {
106 using Base::Base;
107
run__anond5c0e82f0111::Find108 void run(benchmark::State& State) const {
109 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
110
111 while (State.KeepRunningBatch(TableSize * NumTables)) {
112 for (auto K : Data.Keys) {
113 for (auto& Set : Data.Sets) {
114 benchmark::DoNotOptimize(Set.find(K));
115 }
116 }
117 }
118 }
119
name__anond5c0e82f0111::Find120 std::string name() const {
121 return "BM_Find" + Hit::name() + Access::name() + baseName();
122 }
123 };
124
125 template <class Hit, class Access>
126 struct FindNeEnd : Base {
127 using Base::Base;
128
run__anond5c0e82f0111::FindNeEnd129 void run(benchmark::State& State) const {
130 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
131
132 while (State.KeepRunningBatch(TableSize * NumTables)) {
133 for (auto K : Data.Keys) {
134 for (auto& Set : Data.Sets) {
135 benchmark::DoNotOptimize(Set.find(K) != Set.end());
136 }
137 }
138 }
139 }
140
name__anond5c0e82f0111::FindNeEnd141 std::string name() const {
142 return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName();
143 }
144 };
145
146 template <class Access>
147 struct InsertHit : Base {
148 using Base::Base;
149
run__anond5c0e82f0111::InsertHit150 void run(benchmark::State& State) const {
151 auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
152
153 while (State.KeepRunningBatch(TableSize * NumTables)) {
154 for (auto K : Data.Keys) {
155 for (auto& Set : Data.Sets) {
156 benchmark::DoNotOptimize(Set.insert(K));
157 }
158 }
159 }
160 }
161
name__anond5c0e82f0111::InsertHit162 std::string name() const {
163 return "BM_InsertHit" + Access::name() + baseName();
164 }
165 };
166
167 template <class Access>
168 struct InsertMissAndErase : Base {
169 using Base::Base;
170
run__anond5c0e82f0111::InsertMissAndErase171 void run(benchmark::State& State) const {
172 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
173
174 while (State.KeepRunningBatch(TableSize * NumTables)) {
175 for (auto K : Data.Keys) {
176 for (auto& Set : Data.Sets) {
177 benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
178 }
179 }
180 }
181 }
182
name__anond5c0e82f0111::InsertMissAndErase183 std::string name() const {
184 return "BM_InsertMissAndErase" + Access::name() + baseName();
185 }
186 };
187
188 struct IterateRangeFor : Base {
189 using Base::Base;
190
run__anond5c0e82f0111::IterateRangeFor191 void run(benchmark::State& State) const {
192 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
193 AccessPattern::Ordered);
194
195 while (State.KeepRunningBatch(TableSize * NumTables)) {
196 for (auto& Set : Data.Sets) {
197 for (auto& V : Set) {
198 benchmark::DoNotOptimize(V);
199 }
200 }
201 }
202 }
203
name__anond5c0e82f0111::IterateRangeFor204 std::string name() const { return "BM_IterateRangeFor" + baseName(); }
205 };
206
207 struct IterateBeginEnd : Base {
208 using Base::Base;
209
run__anond5c0e82f0111::IterateBeginEnd210 void run(benchmark::State& State) const {
211 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
212 AccessPattern::Ordered);
213
214 while (State.KeepRunningBatch(TableSize * NumTables)) {
215 for (auto& Set : Data.Sets) {
216 for (auto it = Set.begin(); it != Set.end(); ++it) {
217 benchmark::DoNotOptimize(*it);
218 }
219 }
220 }
221 }
222
name__anond5c0e82f0111::IterateBeginEnd223 std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
224 };
225
226 } // namespace
227
main(int argc,char ** argv)228 int main(int argc, char** argv) {
229 benchmark::Initialize(&argc, argv);
230 if (benchmark::ReportUnrecognizedArguments(argc, argv))
231 return 1;
232
233 const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
234 const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
235
236 makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
237 makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(
238 TableSize, NumTables);
239 makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(
240 TableSize, NumTables);
241 makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(
242 TableSize, NumTables);
243 makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(
244 TableSize, NumTables);
245 makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
246 makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
247 benchmark::RunSpecifiedBenchmarks();
248 }
249