libcxx/benchmarks/algorithms.bench.cpp

   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 }