libcxx/test/benchmarks/algorithms.partition_point.bench.cpp

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