Home | History | Annotate | Download | only in benchmarks 
      1 #include <array>
      2 #include <algorithm>
      3 #include <cassert>
      4 #include <cstdint>
      5 #include <tuple>
      6 #include <vector>
      7 
      8 #include "benchmark/benchmark.h"
      9 
     10 #include "CartesianBenchmarks.hpp"
     11 #include "GenerateInput.hpp"
     12 
     13 namespace {
     14 
     15 template <typename I, typename N>
     16 std::array<I, 10> every_10th_percentile_N(I first, N n) {
     17   N step = n / 10;
     18   std::array<I, 10> res;
     19 
     20   for (size_t i = 0; i < 10; ++i) {
     21     res[i] = first;
     22     std::advance(first, step);
     23   }
     24 
     25   return res;
     26 }
     27 
     28 template <class IntT>
     29 struct TestIntBase {
     30   static std::vector<IntT> generateInput(size_t size) {
     31     std::vector<IntT> Res(size);
     32     std::generate(Res.begin(), Res.end(),
     33                   [] { return getRandomInteger<IntT>(); });
     34     return Res;
     35   }
     36 };
     37 
     38 struct TestInt32 : TestIntBase<std::int32_t> {
     39   static constexpr const char* Name = "TestInt32";
     40 };
     41 
     42 struct TestInt64 : TestIntBase<std::int64_t> {
     43   static constexpr const char* Name = "TestInt64";
     44 };
     45 
     46 struct TestUint32 : TestIntBase<std::uint32_t> {
     47   static constexpr const char* Name = "TestUint32";
     48 };
     49 
     50 struct TestMediumString {
     51   static constexpr const char* Name = "TestMediumString";
     52   static constexpr size_t StringSize = 32;
     53 
     54   static std::vector<std::string> generateInput(size_t size) {
     55     std::vector<std::string> Res(size);
     56     std::generate(Res.begin(), Res.end(), [] { return getRandomString(StringSize); });
     57     return Res;
     58   }
     59 };
     60 
     61 using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>;
     62 
     63 struct LowerBoundAlg {
     64   template <class I, class V>
     65   I operator()(I first, I last, const V& value) const {
     66     return std::lower_bound(first, last, value);
     67   }
     68 
     69   static constexpr const char* Name = "LowerBoundAlg";
     70 };
     71 
     72 struct UpperBoundAlg {
     73   template <class I, class V>
     74   I operator()(I first, I last, const V& value) const {
     75     return std::upper_bound(first, last, value);
     76   }
     77 
     78   static constexpr const char* Name = "UpperBoundAlg";
     79 };
     80 
     81 struct EqualRangeAlg {
     82   template <class I, class V>
     83   std::pair<I, I> operator()(I first, I last, const V& value) const {
     84     return std::equal_range(first, last, value);
     85   }
     86 
     87   static constexpr const char* Name = "EqualRangeAlg";
     88 };
     89 
     90 using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>;
     91 
     92 template <class Alg, class TestType>
     93 struct PartitionPointBench {
     94   size_t Quantity;
     95 
     96   std::string name() const {
     97     return std::string("PartitionPointBench_") + Alg::Name + "_" +
     98            TestType::Name + '/' + std::to_string(Quantity);
     99   }
    100 
    101   void run(benchmark::State& state) const {
    102     auto Data = TestType::generateInput(Quantity);
    103     std::sort(Data.begin(), Data.end());
    104     auto Every10Percentile = every_10th_percentile_N(Data.begin(), Data.size());
    105 
    106     for (auto _ : state) {
    107       for (auto Test : Every10Percentile)
    108         benchmark::DoNotOptimize(Alg{}(Data.begin(), Data.end(), *Test));
    109     }
    110   }
    111 };
    112 
    113 } // namespace
    114 
    115 int main(int argc, char** argv) {
    116   benchmark::Initialize(&argc, argv);
    117   if (benchmark::ReportUnrecognizedArguments(argc, argv))
    118     return 1;
    119 
    120   const std::vector<size_t> Quantities = {1 << 8, 1 << 10, 1 << 20};
    121   makeCartesianProductBenchmark<PartitionPointBench, AllAlgs, AllTestTypes>(
    122       Quantities);
    123   benchmark::RunSpecifiedBenchmarks();
    124 }
    125