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> 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> 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> 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> 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 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> 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> 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> 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> 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