Home | History | Annotate | 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.hpp"
     11 #include "GenerateInput.hpp"
     12 #include "benchmark/benchmark.h"
     13 #include "test_macros.h"
     14 
     15 namespace {
     16 
     17 enum class ValueType { Uint32, String };
     18 struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
     19   static constexpr const char* Names[] = {"uint32", "string"};
     20 };
     21 
     22 template <class V>
     23 using Value =
     24     std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
     25 
     26 enum class Order {
     27   Random,
     28   Ascending,
     29   Descending,
     30   SingleElement,
     31   PipeOrgan,
     32   Heap
     33 };
     34 struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
     35   static constexpr const char* Names[] = {"Random",     "Ascending",
     36                                           "Descending", "SingleElement",
     37                                           "PipeOrgan",  "Heap"};
     38 };
     39 
     40 void fillValues(std::vector<uint32_t>& V, size_t N, Order O) {
     41   if (O == Order::SingleElement) {
     42     V.resize(N, 0);
     43   } else {
     44     while (V.size() < N)
     45       V.push_back(V.size());
     46   }
     47 }
     48 
     49 void fillValues(std::vector<std::string>& V, size_t N, Order O) {
     50 
     51   if (O == Order::SingleElement) {
     52     V.resize(N, getRandomString(1024));
     53   } else {
     54     while (V.size() < N)
     55       V.push_back(getRandomString(1024));
     56   }
     57 }
     58 
     59 template <class T>
     60 void sortValues(T& V, Order O) {
     61   assert(std::is_sorted(V.begin(), V.end()));
     62   switch (O) {
     63   case Order::Random: {
     64     std::random_device R;
     65     std::mt19937 M(R());
     66     std::shuffle(V.begin(), V.end(), M);
     67     break;
     68   }
     69   case Order::Ascending:
     70     std::sort(V.begin(), V.end());
     71     break;
     72   case Order::Descending:
     73     std::sort(V.begin(), V.end(), std::greater<>());
     74     break;
     75   case Order::SingleElement:
     76     // Nothing to do
     77     break;
     78   case Order::PipeOrgan:
     79     std::sort(V.begin(), V.end());
     80     std::reverse(V.begin() + V.size() / 2, V.end());
     81     break;
     82   case Order::Heap:
     83     std::make_heap(V.begin(), V.end());
     84     break;
     85   }
     86 }
     87 
     88 template <class ValueType>
     89 std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
     90                                                                Order O) {
     91   // Let's make sure that all random sequences of the same size are the same.
     92   // That way we can compare the different algorithms with the same input.
     93   static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
     94       Cached;
     95 
     96   auto& Values = Cached[{N, O}];
     97   if (Values.empty()) {
     98     fillValues(Values, N, O);
     99     sortValues(Values, O);
    100   };
    101   const size_t NumCopies = std::max(size_t{1}, 1000 / N);
    102   return { NumCopies, Values };
    103 }
    104 
    105 template <class T, class U>
    106 TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
    107                                     U& Orig) {
    108   state.PauseTiming();
    109   for (auto& Copy : Copies)
    110     Copy = Orig;
    111   state.ResumeTiming();
    112 }
    113 
    114 template <class ValueType, class F>
    115 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
    116                    bool CountElements, F f) {
    117   auto Copies = makeOrderedValues<ValueType>(Quantity, O);
    118   const auto Orig = Copies[0];
    119 
    120   const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
    121   while (state.KeepRunningBatch(Batch)) {
    122     for (auto& Copy : Copies) {
    123       f(Copy);
    124       benchmark::DoNotOptimize(Copy);
    125     }
    126     resetCopies(state, Copies, Orig);
    127   }
    128 }
    129 
    130 template <class ValueType, class Order>
    131 struct Sort {
    132   size_t Quantity;
    133 
    134   void run(benchmark::State& state) const {
    135     runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
    136       std::sort(Copy.begin(), Copy.end());
    137     });
    138   }
    139 
    140   bool skip() const { return Order() == ::Order::Heap; }
    141 
    142   std::string name() const {
    143     return "BM_Sort" + ValueType::name() + Order::name() + "_" +
    144            std::to_string(Quantity);
    145   };
    146 };
    147 
    148 template <class ValueType, class Order>
    149 struct StableSort {
    150   size_t Quantity;
    151 
    152   void run(benchmark::State& state) const {
    153     runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
    154       std::stable_sort(Copy.begin(), Copy.end());
    155     });
    156   }
    157 
    158   bool skip() const { return Order() == ::Order::Heap; }
    159 
    160   std::string name() const {
    161     return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
    162            std::to_string(Quantity);
    163   };
    164 };
    165 
    166 template <class ValueType, class Order>
    167 struct MakeHeap {
    168   size_t Quantity;
    169 
    170   void run(benchmark::State& state) const {
    171     runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
    172       std::make_heap(Copy.begin(), Copy.end());
    173     });
    174   }
    175 
    176   std::string name() const {
    177     return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
    178            std::to_string(Quantity);
    179   };
    180 };
    181 
    182 template <class ValueType>
    183 struct SortHeap {
    184   size_t Quantity;
    185 
    186   void run(benchmark::State& state) const {
    187     runOpOnCopies<ValueType>(
    188         state, Quantity, Order::Heap, false,
    189         [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
    190   }
    191 
    192   std::string name() const {
    193     return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
    194   };
    195 };
    196 
    197 template <class ValueType, class Order>
    198 struct MakeThenSortHeap {
    199   size_t Quantity;
    200 
    201   void run(benchmark::State& state) const {
    202     runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
    203       std::make_heap(Copy.begin(), Copy.end());
    204       std::sort_heap(Copy.begin(), Copy.end());
    205     });
    206   }
    207 
    208   std::string name() const {
    209     return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
    210            std::to_string(Quantity);
    211   };
    212 };
    213 
    214 template <class ValueType, class Order>
    215 struct PushHeap {
    216   size_t Quantity;
    217 
    218   void run(benchmark::State& state) const {
    219     runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
    220       for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
    221         std::push_heap(Copy.begin(), I + 1);
    222       }
    223     });
    224   }
    225 
    226   bool skip() const { return Order() == ::Order::Heap; }
    227 
    228   std::string name() const {
    229     return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
    230            std::to_string(Quantity);
    231   };
    232 };
    233 
    234 template <class ValueType>
    235 struct PopHeap {
    236   size_t Quantity;
    237 
    238   void run(benchmark::State& state) const {
    239     runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
    240       for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
    241         std::pop_heap(B, I);
    242       }
    243     });
    244   }
    245 
    246   std::string name() const {
    247     return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
    248   };
    249 };
    250 
    251 } // namespace
    252 
    253 int main(int argc, char** argv) {
    254   benchmark::Initialize(&argc, argv);
    255   if (benchmark::ReportUnrecognizedArguments(argc, argv))
    256     return 1;
    257 
    258   const std::vector<size_t> Quantities = {1 << 0, 1 << 2,  1 << 4,  1 << 6,
    259                                           1 << 8, 1 << 10, 1 << 14, 1 << 18};
    260   makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
    261   makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
    262       Quantities);
    263   makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
    264   makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
    265   makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
    266       Quantities);
    267   makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
    268   makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
    269   benchmark::RunSpecifiedBenchmarks();
    270 }
    271