libcxx/benchmarks/algorithms/common.h

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