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.hpp"
11 #include "GenerateInput.hpp"
12 #include "benchmark/benchmark.h"
13 #include "test_macros.h"
14
15 namespace {
16
17 enum class ValueType { Uint32, String };
18 struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
19 static constexpr const char* Names[] = {"uint32", "string"};
20 };
21
22 template <class V>
23 using Value =
24 std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
25
26 enum class Order {
27 Random,
28 Ascending,
29 Descending,
30 SingleElement,
31 PipeOrgan,
32 Heap
33 };
34 struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
35 static constexpr const char* Names[] = {"Random", "Ascending",
36 "Descending", "SingleElement",
37 "PipeOrgan", "Heap"};
38 };
39
fillValues(std::vector<uint32_t> & V,size_t N,Order O)40 void fillValues(std::vector<uint32_t>& V, size_t N, Order O) {
41 if (O == Order::SingleElement) {
42 V.resize(N, 0);
43 } else {
44 while (V.size() < N)
45 V.push_back(V.size());
46 }
47 }
48
fillValues(std::vector<std::string> & V,size_t N,Order O)49 void fillValues(std::vector<std::string>& V, size_t N, Order O) {
50
51 if (O == Order::SingleElement) {
52 V.resize(N, getRandomString(1024));
53 } else {
54 while (V.size() < N)
55 V.push_back(getRandomString(1024));
56 }
57 }
58
59 template <class T>
sortValues(T & V,Order O)60 void sortValues(T& V, Order O) {
61 assert(std::is_sorted(V.begin(), V.end()));
62 switch (O) {
63 case Order::Random: {
64 std::random_device R;
65 std::mt19937 M(R());
66 std::shuffle(V.begin(), V.end(), M);
67 break;
68 }
69 case Order::Ascending:
70 std::sort(V.begin(), V.end());
71 break;
72 case Order::Descending:
73 std::sort(V.begin(), V.end(), std::greater<>());
74 break;
75 case Order::SingleElement:
76 // Nothing to do
77 break;
78 case Order::PipeOrgan:
79 std::sort(V.begin(), V.end());
80 std::reverse(V.begin() + V.size() / 2, V.end());
81 break;
82 case Order::Heap:
83 std::make_heap(V.begin(), V.end());
84 break;
85 }
86 }
87
88 template <class ValueType>
makeOrderedValues(size_t N,Order O)89 std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
90 Order O) {
91 // Let's make sure that all random sequences of the same size are the same.
92 // That way we can compare the different algorithms with the same input.
93 static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
94 Cached;
95
96 auto& Values = Cached[{N, O}];
97 if (Values.empty()) {
98 fillValues(Values, N, O);
99 sortValues(Values, O);
100 };
101 const size_t NumCopies = std::max(size_t{1}, 1000 / N);
102 return { NumCopies, Values };
103 }
104
105 template <class T, class U>
resetCopies(benchmark::State & state,T & Copies,U & Orig)106 TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
107 U& Orig) {
108 state.PauseTiming();
109 for (auto& Copy : Copies)
110 Copy = Orig;
111 state.ResumeTiming();
112 }
113
114 template <class ValueType, class F>
runOpOnCopies(benchmark::State & state,size_t Quantity,Order O,bool CountElements,F f)115 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
116 bool CountElements, F f) {
117 auto Copies = makeOrderedValues<ValueType>(Quantity, O);
118 const auto Orig = Copies[0];
119
120 const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
121 while (state.KeepRunningBatch(Batch)) {
122 for (auto& Copy : Copies) {
123 f(Copy);
124 benchmark::DoNotOptimize(Copy);
125 }
126 resetCopies(state, Copies, Orig);
127 }
128 }
129
130 template <class ValueType, class Order>
131 struct Sort {
132 size_t Quantity;
133
run__anone25e4fa60111::Sort134 void run(benchmark::State& state) const {
135 runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
136 std::sort(Copy.begin(), Copy.end());
137 });
138 }
139
skip__anone25e4fa60111::Sort140 bool skip() const { return Order() == ::Order::Heap; }
141
name__anone25e4fa60111::Sort142 std::string name() const {
143 return "BM_Sort" + ValueType::name() + Order::name() + "_" +
144 std::to_string(Quantity);
145 };
146 };
147
148 template <class ValueType, class Order>
149 struct StableSort {
150 size_t Quantity;
151
run__anone25e4fa60111::StableSort152 void run(benchmark::State& state) const {
153 runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
154 std::stable_sort(Copy.begin(), Copy.end());
155 });
156 }
157
skip__anone25e4fa60111::StableSort158 bool skip() const { return Order() == ::Order::Heap; }
159
name__anone25e4fa60111::StableSort160 std::string name() const {
161 return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
162 std::to_string(Quantity);
163 };
164 };
165
166 template <class ValueType, class Order>
167 struct MakeHeap {
168 size_t Quantity;
169
run__anone25e4fa60111::MakeHeap170 void run(benchmark::State& state) const {
171 runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
172 std::make_heap(Copy.begin(), Copy.end());
173 });
174 }
175
name__anone25e4fa60111::MakeHeap176 std::string name() const {
177 return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
178 std::to_string(Quantity);
179 };
180 };
181
182 template <class ValueType>
183 struct SortHeap {
184 size_t Quantity;
185
run__anone25e4fa60111::SortHeap186 void run(benchmark::State& state) const {
187 runOpOnCopies<ValueType>(
188 state, Quantity, Order::Heap, false,
189 [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
190 }
191
name__anone25e4fa60111::SortHeap192 std::string name() const {
193 return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
194 };
195 };
196
197 template <class ValueType, class Order>
198 struct MakeThenSortHeap {
199 size_t Quantity;
200
run__anone25e4fa60111::MakeThenSortHeap201 void run(benchmark::State& state) const {
202 runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
203 std::make_heap(Copy.begin(), Copy.end());
204 std::sort_heap(Copy.begin(), Copy.end());
205 });
206 }
207
name__anone25e4fa60111::MakeThenSortHeap208 std::string name() const {
209 return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
210 std::to_string(Quantity);
211 };
212 };
213
214 template <class ValueType, class Order>
215 struct PushHeap {
216 size_t Quantity;
217
run__anone25e4fa60111::PushHeap218 void run(benchmark::State& state) const {
219 runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
220 for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
221 std::push_heap(Copy.begin(), I + 1);
222 }
223 });
224 }
225
skip__anone25e4fa60111::PushHeap226 bool skip() const { return Order() == ::Order::Heap; }
227
name__anone25e4fa60111::PushHeap228 std::string name() const {
229 return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
230 std::to_string(Quantity);
231 };
232 };
233
234 template <class ValueType>
235 struct PopHeap {
236 size_t Quantity;
237
run__anone25e4fa60111::PopHeap238 void run(benchmark::State& state) const {
239 runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
240 for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
241 std::pop_heap(B, I);
242 }
243 });
244 }
245
name__anone25e4fa60111::PopHeap246 std::string name() const {
247 return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
248 };
249 };
250
251 } // namespace
252
main(int argc,char ** argv)253 int main(int argc, char** argv) {
254 benchmark::Initialize(&argc, argv);
255 if (benchmark::ReportUnrecognizedArguments(argc, argv))
256 return 1;
257
258 const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6,
259 1 << 8, 1 << 10, 1 << 14, 1 << 18};
260 makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
261 makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
262 Quantities);
263 makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
264 makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
265 makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
266 Quantities);
267 makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
268 makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
269 benchmark::RunSpecifiedBenchmarks();
270 }
271