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>
every_10th_percentile_N(I first,N 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 {
generateInput__anon536c62c10111::TestIntBase30 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
generateInput__anon536c62c10111::TestMediumString54 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>
operator ()__anon536c62c10111::LowerBoundAlg65 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>
operator ()__anon536c62c10111::UpperBoundAlg74 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>
operator ()__anon536c62c10111::EqualRangeAlg83 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
name__anon536c62c10111::PartitionPointBench96 std::string name() const {
97 return std::string("PartitionPointBench_") + Alg::Name + "_" +
98 TestType::Name + '/' + std::to_string(Quantity);
99 }
100
run__anon536c62c10111::PartitionPointBench101 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
main(int argc,char ** argv)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