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