1
2 #include <algorithm>
3 #include <cstdint>
4 #include <map>
5 #include <random>
6 #include <string>
7 #include <utility>
8 #include <vector>
9
10 #include "CartesianBenchmarks.h"
11 #include "GenerateInput.h"
12 #include "benchmark/benchmark.h"
13 #include "test_macros.h"
14
15 namespace {
16
17 enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
18 struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
19 static constexpr const char* Names[] = {
20 "uint32", "uint64", "pair<uint32, uint32>",
21 "tuple<uint32, uint64, uint32>", "string"};
22 };
23
24 template <class V>
25 using Value = std::conditional_t<
26 V() == ValueType::Uint32, uint32_t,
27 std::conditional_t<
28 V() == ValueType::Uint64, uint64_t,
29 std::conditional_t<
30 V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
31 std::conditional_t<V() == ValueType::Tuple,
32 std::tuple<uint32_t, uint64_t, uint32_t>,
33 std::string> > > >;
34
35 enum class Order {
36 Random,
37 Ascending,
38 Descending,
39 SingleElement,
40 PipeOrgan,
41 Heap
42 };
43 struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
44 static constexpr const char* Names[] = {"Random", "Ascending",
45 "Descending", "SingleElement",
46 "PipeOrgan", "Heap"};
47 };
48
49 template <typename T>
fillValues(std::vector<T> & V,size_t N,Order O)50 void fillValues(std::vector<T>& V, size_t N, Order O) {
51 if (O == Order::SingleElement) {
52 V.resize(N, 0);
53 } else {
54 while (V.size() < N)
55 V.push_back(V.size());
56 }
57 }
58
59 template <typename T>
fillValues(std::vector<std::pair<T,T>> & V,size_t N,Order O)60 void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
61 if (O == Order::SingleElement) {
62 V.resize(N, std::make_pair(0, 0));
63 } else {
64 while (V.size() < N)
65 // Half of array will have the same first element.
66 if (V.size() % 2) {
67 V.push_back(std::make_pair(V.size(), V.size()));
68 } else {
69 V.push_back(std::make_pair(0, V.size()));
70 }
71 }
72 }
73
74 template <typename T1, typename T2, typename T3>
fillValues(std::vector<std::tuple<T1,T2,T3>> & V,size_t N,Order O)75 void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
76 if (O == Order::SingleElement) {
77 V.resize(N, std::make_tuple(0, 0, 0));
78 } else {
79 while (V.size() < N)
80 // One third of array will have the same first element.
81 // One third of array will have the same first element and the same second element.
82 switch (V.size() % 3) {
83 case 0:
84 V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
85 break;
86 case 1:
87 V.push_back(std::make_tuple(0, V.size(), V.size()));
88 break;
89 case 2:
90 V.push_back(std::make_tuple(0, 0, V.size()));
91 break;
92 }
93 }
94 }
95
fillValues(std::vector<std::string> & V,size_t N,Order O)96 void fillValues(std::vector<std::string>& V, size_t N, Order O) {
97 if (O == Order::SingleElement) {
98 V.resize(N, getRandomString(64));
99 } else {
100 while (V.size() < N)
101 V.push_back(getRandomString(64));
102 }
103 }
104
105 template <class T>
sortValues(T & V,Order O)106 void sortValues(T& V, Order O) {
107 assert(std::is_sorted(V.begin(), V.end()));
108 switch (O) {
109 case Order::Random: {
110 std::random_device R;
111 std::mt19937 M(R());
112 std::shuffle(V.begin(), V.end(), M);
113 break;
114 }
115 case Order::Ascending:
116 std::sort(V.begin(), V.end());
117 break;
118 case Order::Descending:
119 std::sort(V.begin(), V.end(), std::greater<>());
120 break;
121 case Order::SingleElement:
122 // Nothing to do
123 break;
124 case Order::PipeOrgan:
125 std::sort(V.begin(), V.end());
126 std::reverse(V.begin() + V.size() / 2, V.end());
127 break;
128 case Order::Heap:
129 std::make_heap(V.begin(), V.end());
130 break;
131 }
132 }
133
134 constexpr size_t TestSetElements =
135 #if !TEST_HAS_FEATURE(memory_sanitizer)
136 1 << 18;
137 #else
138 1 << 14;
139 #endif
140
141 template <class ValueType>
makeOrderedValues(size_t N,Order O)142 std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
143 Order O) {
144 std::vector<std::vector<Value<ValueType> > > Ret;
145 const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
146 Ret.resize(NumCopies);
147 for (auto& V : Ret) {
148 fillValues(V, N, O);
149 sortValues(V, O);
150 }
151 return Ret;
152 }
153
154 template <class T, class U>
resetCopies(benchmark::State & state,T & Copies,U & Orig)155 TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
156 U& Orig) {
157 state.PauseTiming();
158 for (auto& Copy : Copies)
159 Copy = Orig;
160 state.ResumeTiming();
161 }
162
163 enum class BatchSize {
164 CountElements,
165 CountBatch,
166 };
167
168 template <class ValueType, class F>
runOpOnCopies(benchmark::State & state,size_t Quantity,Order O,BatchSize Count,F Body)169 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
170 BatchSize Count, F Body) {
171 auto Copies = makeOrderedValues<ValueType>(Quantity, O);
172 auto Orig = Copies;
173
174 const size_t Batch = Count == BatchSize::CountElements
175 ? Copies.size() * Quantity
176 : Copies.size();
177 while (state.KeepRunningBatch(Batch)) {
178 for (auto& Copy : Copies) {
179 Body(Copy);
180 benchmark::DoNotOptimize(Copy);
181 }
182 state.PauseTiming();
183 Copies = Orig;
184 state.ResumeTiming();
185 }
186 }
187
188 template <class ValueType, class Order>
189 struct Sort {
190 size_t Quantity;
191
run__anonc233ceb90111::Sort192 void run(benchmark::State& state) const {
193 runOpOnCopies<ValueType>(
194 state, Quantity, Order(), BatchSize::CountElements,
195 [](auto& Copy) { std::sort(Copy.begin(), Copy.end()); });
196 }
197
skip__anonc233ceb90111::Sort198 bool skip() const { return Order() == ::Order::Heap; }
199
name__anonc233ceb90111::Sort200 std::string name() const {
201 return "BM_Sort" + ValueType::name() + Order::name() + "_" +
202 std::to_string(Quantity);
203 };
204 };
205
206 template <class ValueType, class Order>
207 struct StableSort {
208 size_t Quantity;
209
run__anonc233ceb90111::StableSort210 void run(benchmark::State& state) const {
211 runOpOnCopies<ValueType>(
212 state, Quantity, Order(), BatchSize::CountElements,
213 [](auto& Copy) { std::stable_sort(Copy.begin(), Copy.end()); });
214 }
215
skip__anonc233ceb90111::StableSort216 bool skip() const { return Order() == ::Order::Heap; }
217
name__anonc233ceb90111::StableSort218 std::string name() const {
219 return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
220 std::to_string(Quantity);
221 };
222 };
223
224 template <class ValueType, class Order>
225 struct MakeHeap {
226 size_t Quantity;
227
run__anonc233ceb90111::MakeHeap228 void run(benchmark::State& state) const {
229 runOpOnCopies<ValueType>(
230 state, Quantity, Order(), BatchSize::CountElements,
231 [](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); });
232 }
233
name__anonc233ceb90111::MakeHeap234 std::string name() const {
235 return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
236 std::to_string(Quantity);
237 };
238 };
239
240 template <class ValueType>
241 struct SortHeap {
242 size_t Quantity;
243
run__anonc233ceb90111::SortHeap244 void run(benchmark::State& state) const {
245 runOpOnCopies<ValueType>(
246 state, Quantity, Order::Heap, BatchSize::CountElements,
247 [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
248 }
249
name__anonc233ceb90111::SortHeap250 std::string name() const {
251 return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
252 };
253 };
254
255 template <class ValueType, class Order>
256 struct MakeThenSortHeap {
257 size_t Quantity;
258
run__anonc233ceb90111::MakeThenSortHeap259 void run(benchmark::State& state) const {
260 runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
261 [](auto& Copy) {
262 std::make_heap(Copy.begin(), Copy.end());
263 std::sort_heap(Copy.begin(), Copy.end());
264 });
265 }
266
name__anonc233ceb90111::MakeThenSortHeap267 std::string name() const {
268 return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
269 std::to_string(Quantity);
270 };
271 };
272
273 template <class ValueType, class Order>
274 struct PushHeap {
275 size_t Quantity;
276
run__anonc233ceb90111::PushHeap277 void run(benchmark::State& state) const {
278 runOpOnCopies<ValueType>(
279 state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
280 for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
281 std::push_heap(Copy.begin(), I + 1);
282 }
283 });
284 }
285
skip__anonc233ceb90111::PushHeap286 bool skip() const { return Order() == ::Order::Heap; }
287
name__anonc233ceb90111::PushHeap288 std::string name() const {
289 return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
290 std::to_string(Quantity);
291 };
292 };
293
294 template <class ValueType>
295 struct PopHeap {
296 size_t Quantity;
297
run__anonc233ceb90111::PopHeap298 void run(benchmark::State& state) const {
299 runOpOnCopies<ValueType>(
300 state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
301 for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
302 std::pop_heap(B, I);
303 }
304 });
305 }
306
name__anonc233ceb90111::PopHeap307 std::string name() const {
308 return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
309 };
310 };
311
312 } // namespace
313
main(int argc,char ** argv)314 int main(int argc, char** argv) {
315 benchmark::Initialize(&argc, argv);
316 if (benchmark::ReportUnrecognizedArguments(argc, argv))
317 return 1;
318
319 const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6,
320 1 << 8, 1 << 10, 1 << 14,
321 // Running each benchmark in parallel consumes too much memory with MSAN
322 // and can lead to the test process being killed.
323 #if !TEST_HAS_FEATURE(memory_sanitizer)
324 1 << 18
325 #endif
326 };
327 makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
328 makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
329 Quantities);
330 makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
331 makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
332 makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
333 Quantities);
334 makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
335 makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
336 benchmark::RunSpecifiedBenchmarks();
337 }