Home | History | Annotate | Line # | Download | only in benchmarks 
      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 }