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> 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> 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> 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 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> 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> 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> 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> 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 192 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 198 bool skip() const { return Order() == ::Order::Heap; } 199 200 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 210 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 216 bool skip() const { return Order() == ::Order::Heap; } 217 218 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 228 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 234 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 244 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 250 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 259 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 267 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 277 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 286 bool skip() const { return Order() == ::Order::Heap; } 287 288 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 298 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 307 std::string name() const { 308 return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity); 309 }; 310 }; 311 312 } // namespace 313 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 }