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 #ifndef LIBCXX_ALGORITHMS_COMMON_H
10 #define LIBCXX_ALGORITHMS_COMMON_H
11
12 #include <algorithm>
13 #include <numeric>
14 #include <tuple>
15 #include <vector>
16
17 #include "../CartesianBenchmarks.h"
18 #include "../GenerateInput.h"
19
20 enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float };
21 struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 6> {
22 static constexpr const char* Names[] = {"uint32", "uint64", "pair<uint32, uint32>", "tuple<uint32, uint64, uint32>",
23 "string", "float"};
24 };
25
26 using Types = std::tuple< uint32_t, uint64_t, std::pair<uint32_t, uint32_t>, std::tuple<uint32_t, uint64_t, uint32_t>,
27 std::string, float >;
28
29 template <class V>
30 using Value = std::tuple_element_t<(int)V::value, Types>;
31
32 enum class Order {
33 Random,
34 Ascending,
35 Descending,
36 SingleElement,
37 PipeOrgan,
38 Heap,
39 QuickSortAdversary,
40 };
41 struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
42 static constexpr const char* Names[] = {"Random", "Ascending",
43 "Descending", "SingleElement",
44 "PipeOrgan", "Heap",
45 "QuickSortAdversary"};
46 };
47
48 // fillAdversarialQuickSortInput fills the input vector with N int-like values.
49 // These values are arranged in such a way that they would invoke O(N^2)
50 // behavior on any quick sort implementation that satisifies certain conditions.
51 // Details are available in the following paper:
52 // "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &
53 // Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.
54 // https://dl.acm.org/doi/10.5555/311868.311871.
55 template <class T>
fillAdversarialQuickSortInput(T & V,size_t N)56 void fillAdversarialQuickSortInput(T& V, size_t N) {
57 assert(N > 0);
58 // If an element is equal to gas, it indicates that the value of the element
59 // is still to be decided and may change over the course of time.
60 const unsigned int gas = N - 1;
61 V.resize(N);
62 for (unsigned int i = 0; i < N; ++i) {
63 V[i] = gas;
64 }
65 // Candidate for the pivot position.
66 int candidate = 0;
67 int nsolid = 0;
68 // Populate all positions in the generated input to gas.
69 std::vector<int> ascVals(V.size());
70 // Fill up with ascending values from 0 to V.size()-1. These will act as
71 // indices into V.
72 std::iota(ascVals.begin(), ascVals.end(), 0);
73 std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {
74 if (V[x] == gas && V[y] == gas) {
75 // We are comparing two inputs whose value is still to be decided.
76 if (x == candidate) {
77 V[x] = nsolid++;
78 } else {
79 V[y] = nsolid++;
80 }
81 }
82 if (V[x] == gas) {
83 candidate = x;
84 } else if (V[y] == gas) {
85 candidate = y;
86 }
87 return V[x] < V[y];
88 });
89 }
90
91 template <typename T>
fillValues(std::vector<T> & V,size_t N,Order O)92 void fillValues(std::vector<T>& V, size_t N, Order O) {
93 if (O == Order::SingleElement) {
94 V.resize(N, 0);
95 } else if (O == Order::QuickSortAdversary) {
96 fillAdversarialQuickSortInput(V, N);
97 } else {
98 while (V.size() < N)
99 V.push_back(V.size());
100 }
101 }
102
103 template <typename T>
fillValues(std::vector<std::pair<T,T>> & V,size_t N,Order O)104 void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
105 if (O == Order::SingleElement) {
106 V.resize(N, std::make_pair(0, 0));
107 } else {
108 while (V.size() < N)
109 // Half of array will have the same first element.
110 if (V.size() % 2) {
111 V.push_back(std::make_pair(V.size(), V.size()));
112 } else {
113 V.push_back(std::make_pair(0, V.size()));
114 }
115 }
116 }
117
118 template <typename T1, typename T2, typename T3>
fillValues(std::vector<std::tuple<T1,T2,T3>> & V,size_t N,Order O)119 void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
120 if (O == Order::SingleElement) {
121 V.resize(N, std::make_tuple(0, 0, 0));
122 } else {
123 while (V.size() < N)
124 // One third of array will have the same first element.
125 // One third of array will have the same first element and the same second element.
126 switch (V.size() % 3) {
127 case 0:
128 V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
129 break;
130 case 1:
131 V.push_back(std::make_tuple(0, V.size(), V.size()));
132 break;
133 case 2:
134 V.push_back(std::make_tuple(0, 0, V.size()));
135 break;
136 }
137 }
138 }
139
fillValues(std::vector<std::string> & V,size_t N,Order O)140 inline void fillValues(std::vector<std::string>& V, size_t N, Order O) {
141 if (O == Order::SingleElement) {
142 V.resize(N, getRandomString(64));
143 } else {
144 while (V.size() < N)
145 V.push_back(getRandomString(64));
146 }
147 }
148
149 template <class T>
sortValues(T & V,Order O)150 void sortValues(T& V, Order O) {
151 switch (O) {
152 case Order::Random: {
153 std::random_device R;
154 std::mt19937 M(R());
155 std::shuffle(V.begin(), V.end(), M);
156 break;
157 }
158 case Order::Ascending:
159 std::sort(V.begin(), V.end());
160 break;
161 case Order::Descending:
162 std::sort(V.begin(), V.end(), std::greater<>());
163 break;
164 case Order::SingleElement:
165 // Nothing to do
166 break;
167 case Order::PipeOrgan:
168 std::sort(V.begin(), V.end());
169 std::reverse(V.begin() + V.size() / 2, V.end());
170 break;
171 case Order::Heap:
172 std::make_heap(V.begin(), V.end());
173 break;
174 case Order::QuickSortAdversary:
175 // Nothing to do
176 break;
177 }
178 }
179
180 constexpr size_t TestSetElements =
181 #if !TEST_HAS_FEATURE(memory_sanitizer)
182 1 << 18;
183 #else
184 1 << 14;
185 #endif
186
187 template <class ValueType>
makeOrderedValues(size_t N,Order O)188 std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
189 Order O) {
190 std::vector<std::vector<Value<ValueType> > > Ret;
191 const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
192 Ret.resize(NumCopies);
193 for (auto& V : Ret) {
194 fillValues(V, N, O);
195 sortValues(V, O);
196 }
197 return Ret;
198 }
199
200 template <class T, class U>
resetCopies(benchmark::State & state,T & Copies,U & Orig)201 TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
202 U& Orig) {
203 state.PauseTiming();
204 for (auto& Copy : Copies)
205 Copy = Orig;
206 state.ResumeTiming();
207 }
208
209 enum class BatchSize {
210 CountElements,
211 CountBatch,
212 };
213
214 template <class ValueType, class F>
runOpOnCopies(benchmark::State & state,size_t Quantity,Order O,BatchSize Count,F Body)215 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
216 BatchSize Count, F Body) {
217 auto Copies = makeOrderedValues<ValueType>(Quantity, O);
218 auto Orig = Copies;
219
220 const size_t Batch = Count == BatchSize::CountElements
221 ? Copies.size() * Quantity
222 : Copies.size();
223 while (state.KeepRunningBatch(Batch)) {
224 for (auto& Copy : Copies) {
225 Body(Copy);
226 benchmark::DoNotOptimize(Copy);
227 }
228 state.PauseTiming();
229 Copies = Orig;
230 state.ResumeTiming();
231 }
232 }
233
234
235 const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6,
236 1 << 8, 1 << 10, 1 << 14,
237 // Running each benchmark in parallel consumes too much memory with MSAN
238 // and can lead to the test process being killed.
239 #if !TEST_HAS_FEATURE(memory_sanitizer)
240 1 << 18
241 #endif
242 };
243
244 #endif // LIBCXX_ALGORITHMS_COMMON_H
245