libcxx/benchmarks/algorithms.partition_point.bench.cpp

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