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
13namespace {
14
15template <typename I, typename N>
16std::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
28template <class IntT>
29struct 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
37struct TestInt32 : TestIntBase<std::int32_t> {
38 static constexpr const char* Name = "TestInt32";
39};
40
41struct TestInt64 : TestIntBase<std::int64_t> {
42 static constexpr const char* Name = "TestInt64";
43};
44
45struct TestUint32 : TestIntBase<std::uint32_t> {
46 static constexpr const char* Name = "TestUint32";
47};
48
49struct 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(first: Res.begin(), last: Res.end(), gen: [] { return getRandomString(Len: StringSize); });
56 return Res;
57 }
58};
59
60using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>;
61
62struct 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
71struct 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
80struct 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
89using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>;
90
91template <class Alg, class TestType>
92struct PartitionPointBench {
93 size_t Quantity;
94
95 std::string name() const {
96 return std::string("PartitionPointBench_") + Alg::Name + "_" + TestType::Name + '/' + std::to_string(val: 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
113int main(int argc, char** argv) {
114 benchmark::Initialize(argc: &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>(A: Quantities);
120 benchmark::RunSpecifiedBenchmarks();
121}
122

source code of libcxx/benchmarks/algorithms.partition_point.bench.cpp