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 : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
32 static constexpr const char* Names[] = {"Ordered", "Random"};
33 };
34
sortKeysBy(std::vector<uint64_t> & Keys,AccessPattern AP)35 void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
36 if (AP == AccessPattern::Random) {
37 std::random_device R;
38 std::mt19937 M(R());
39 std::shuffle(std::begin(Keys), std::end(Keys), M);
40 }
41 }
42
43 struct TestSets {
44 std::vector<std::set<uint64_t> > Sets;
45 std::vector<uint64_t> Keys;
46 };
47
makeTestingSets(size_t TableSize,size_t NumTables,HitType Hit,AccessPattern Access)48 TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit, AccessPattern Access) {
49 TestSets R;
50 R.Sets.resize(1);
51
52 for (uint64_t I = 0; I < TableSize; ++I) {
53 R.Sets[0].insert(2 * I);
54 R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
55 }
56 R.Sets.resize(NumTables, R.Sets[0]);
57 sortKeysBy(R.Keys, Access);
58
59 return R;
60 }
61
62 struct Base {
63 size_t TableSize;
64 size_t NumTables;
Base__anond84fc66a0111::Base65 Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
66
skip__anond84fc66a0111::Base67 bool skip() const {
68 size_t Total = TableSize * NumTables;
69 return Total < 100 || Total > 1000000;
70 }
71
baseName__anond84fc66a0111::Base72 std::string baseName() const {
73 return "_TableSize" + std::to_string(TableSize) + "_NumTables" + std::to_string(NumTables);
74 }
75 };
76
77 template <class Access>
78 struct Create : Base {
79 using Base::Base;
80
run__anond84fc66a0111::Create81 void run(benchmark::State& State) const {
82 std::vector<uint64_t> Keys(TableSize);
83 std::iota(Keys.begin(), Keys.end(), uint64_t{0});
84 sortKeysBy(Keys, Access());
85
86 while (State.KeepRunningBatch(TableSize * NumTables)) {
87 std::vector<std::set<uint64_t>> Sets(NumTables);
88 for (auto K : Keys) {
89 for (auto& Set : Sets) {
90 benchmark::DoNotOptimize(Set.insert(K));
91 }
92 }
93 }
94 }
95
name__anond84fc66a0111::Create96 std::string name() const { return "BM_Create" + Access::name() + baseName(); }
97 };
98
99 template <class Hit, class Access>
100 struct Find : Base {
101 using Base::Base;
102
run__anond84fc66a0111::Find103 void run(benchmark::State& State) const {
104 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
105
106 while (State.KeepRunningBatch(TableSize * NumTables)) {
107 for (auto K : Data.Keys) {
108 for (auto& Set : Data.Sets) {
109 benchmark::DoNotOptimize(Set.find(K));
110 }
111 }
112 }
113 }
114
name__anond84fc66a0111::Find115 std::string name() const { return "BM_Find" + Hit::name() + Access::name() + baseName(); }
116 };
117
118 template <class Hit, class Access>
119 struct FindNeEnd : Base {
120 using Base::Base;
121
run__anond84fc66a0111::FindNeEnd122 void run(benchmark::State& State) const {
123 auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
124
125 while (State.KeepRunningBatch(TableSize * NumTables)) {
126 for (auto K : Data.Keys) {
127 for (auto& Set : Data.Sets) {
128 benchmark::DoNotOptimize(Set.find(K) != Set.end());
129 }
130 }
131 }
132 }
133
name__anond84fc66a0111::FindNeEnd134 std::string name() const { return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName(); }
135 };
136
137 template <class Access>
138 struct InsertHit : Base {
139 using Base::Base;
140
run__anond84fc66a0111::InsertHit141 void run(benchmark::State& State) const {
142 auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
143
144 while (State.KeepRunningBatch(TableSize * NumTables)) {
145 for (auto K : Data.Keys) {
146 for (auto& Set : Data.Sets) {
147 benchmark::DoNotOptimize(Set.insert(K));
148 }
149 }
150 }
151 }
152
name__anond84fc66a0111::InsertHit153 std::string name() const { return "BM_InsertHit" + Access::name() + baseName(); }
154 };
155
156 template <class Access>
157 struct InsertMissAndErase : Base {
158 using Base::Base;
159
run__anond84fc66a0111::InsertMissAndErase160 void run(benchmark::State& State) const {
161 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
162
163 while (State.KeepRunningBatch(TableSize * NumTables)) {
164 for (auto K : Data.Keys) {
165 for (auto& Set : Data.Sets) {
166 benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
167 }
168 }
169 }
170 }
171
name__anond84fc66a0111::InsertMissAndErase172 std::string name() const { return "BM_InsertMissAndErase" + Access::name() + baseName(); }
173 };
174
175 struct IterateRangeFor : Base {
176 using Base::Base;
177
run__anond84fc66a0111::IterateRangeFor178 void run(benchmark::State& State) const {
179 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, AccessPattern::Ordered);
180
181 while (State.KeepRunningBatch(TableSize * NumTables)) {
182 for (auto& Set : Data.Sets) {
183 for (auto& V : Set) {
184 benchmark::DoNotOptimize(V);
185 }
186 }
187 }
188 }
189
name__anond84fc66a0111::IterateRangeFor190 std::string name() const { return "BM_IterateRangeFor" + baseName(); }
191 };
192
193 struct IterateBeginEnd : Base {
194 using Base::Base;
195
run__anond84fc66a0111::IterateBeginEnd196 void run(benchmark::State& State) const {
197 auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, AccessPattern::Ordered);
198
199 while (State.KeepRunningBatch(TableSize * NumTables)) {
200 for (auto& Set : Data.Sets) {
201 for (auto it = Set.begin(); it != Set.end(); ++it) {
202 benchmark::DoNotOptimize(*it);
203 }
204 }
205 }
206 }
207
name__anond84fc66a0111::IterateBeginEnd208 std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
209 };
210
211 } // namespace
212
main(int argc,char ** argv)213 int main(int argc, char** argv) {
214 benchmark::Initialize(&argc, argv);
215 if (benchmark::ReportUnrecognizedArguments(argc, argv))
216 return 1;
217
218 const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
219 const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
220
221 makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
222 makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(TableSize, NumTables);
223 makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(TableSize, NumTables);
224 makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(TableSize, NumTables);
225 makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(TableSize, NumTables);
226 makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
227 makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
228 benchmark::RunSpecifiedBenchmarks();
229 }
230