1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/numeric/int128.h"
16
17 #include <algorithm>
18 #include <cstdint>
19 #include <random>
20 #include <vector>
21
22 #include "benchmark/benchmark.h"
23 #include "absl/base/config.h"
24
25 namespace {
26
27 constexpr size_t kSampleSize = 1000000;
28
MakeRandomEngine()29 std::mt19937 MakeRandomEngine() {
30 std::random_device r;
31 std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()});
32 return std::mt19937(seed);
33 }
34
35 std::vector<std::pair<absl::uint128, absl::uint128>>
GetRandomClass128SampleUniformDivisor()36 GetRandomClass128SampleUniformDivisor() {
37 std::vector<std::pair<absl::uint128, absl::uint128>> values;
38 std::mt19937 random = MakeRandomEngine();
39 std::uniform_int_distribution<uint64_t> uniform_uint64;
40 values.reserve(kSampleSize);
41 for (size_t i = 0; i < kSampleSize; ++i) {
42 absl::uint128 a =
43 absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
44 absl::uint128 b =
45 absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
46 values.emplace_back(std::max(a, b),
47 std::max(absl::uint128(2), std::min(a, b)));
48 }
49 return values;
50 }
51
BM_DivideClass128UniformDivisor(benchmark::State & state)52 void BM_DivideClass128UniformDivisor(benchmark::State& state) {
53 auto values = GetRandomClass128SampleUniformDivisor();
54 while (state.KeepRunningBatch(values.size())) {
55 for (const auto& pair : values) {
56 benchmark::DoNotOptimize(pair.first / pair.second);
57 }
58 }
59 }
60 BENCHMARK(BM_DivideClass128UniformDivisor);
61
62 std::vector<std::pair<absl::uint128, uint64_t>>
GetRandomClass128SampleSmallDivisor()63 GetRandomClass128SampleSmallDivisor() {
64 std::vector<std::pair<absl::uint128, uint64_t>> values;
65 std::mt19937 random = MakeRandomEngine();
66 std::uniform_int_distribution<uint64_t> uniform_uint64;
67 values.reserve(kSampleSize);
68 for (size_t i = 0; i < kSampleSize; ++i) {
69 absl::uint128 a =
70 absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
71 uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
72 values.emplace_back(std::max(a, absl::uint128(b)), b);
73 }
74 return values;
75 }
76
BM_DivideClass128SmallDivisor(benchmark::State & state)77 void BM_DivideClass128SmallDivisor(benchmark::State& state) {
78 auto values = GetRandomClass128SampleSmallDivisor();
79 while (state.KeepRunningBatch(values.size())) {
80 for (const auto& pair : values) {
81 benchmark::DoNotOptimize(pair.first / pair.second);
82 }
83 }
84 }
85 BENCHMARK(BM_DivideClass128SmallDivisor);
86
GetRandomClass128Sample()87 std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() {
88 std::vector<std::pair<absl::uint128, absl::uint128>> values;
89 std::mt19937 random = MakeRandomEngine();
90 std::uniform_int_distribution<uint64_t> uniform_uint64;
91 values.reserve(kSampleSize);
92 for (size_t i = 0; i < kSampleSize; ++i) {
93 values.emplace_back(
94 absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)),
95 absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)));
96 }
97 return values;
98 }
99
BM_MultiplyClass128(benchmark::State & state)100 void BM_MultiplyClass128(benchmark::State& state) {
101 auto values = GetRandomClass128Sample();
102 while (state.KeepRunningBatch(values.size())) {
103 for (const auto& pair : values) {
104 benchmark::DoNotOptimize(pair.first * pair.second);
105 }
106 }
107 }
108 BENCHMARK(BM_MultiplyClass128);
109
BM_AddClass128(benchmark::State & state)110 void BM_AddClass128(benchmark::State& state) {
111 auto values = GetRandomClass128Sample();
112 while (state.KeepRunningBatch(values.size())) {
113 for (const auto& pair : values) {
114 benchmark::DoNotOptimize(pair.first + pair.second);
115 }
116 }
117 }
118 BENCHMARK(BM_AddClass128);
119
120 #ifdef ABSL_HAVE_INTRINSIC_INT128
121
122 // Some implementations of <random> do not support __int128 when it is
123 // available, so we make our own uniform_int_distribution-like type.
124 class UniformIntDistribution128 {
125 public:
126 // NOLINTNEXTLINE: mimicking std::uniform_int_distribution API
operator ()(std::mt19937 & generator)127 unsigned __int128 operator()(std::mt19937& generator) {
128 return (static_cast<unsigned __int128>(dist64_(generator)) << 64) |
129 dist64_(generator);
130 }
131
132 private:
133 std::uniform_int_distribution<uint64_t> dist64_;
134 };
135
136 std::vector<std::pair<unsigned __int128, unsigned __int128>>
GetRandomIntrinsic128SampleUniformDivisor()137 GetRandomIntrinsic128SampleUniformDivisor() {
138 std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
139 std::mt19937 random = MakeRandomEngine();
140 UniformIntDistribution128 uniform_uint128;
141 values.reserve(kSampleSize);
142 for (size_t i = 0; i < kSampleSize; ++i) {
143 unsigned __int128 a = uniform_uint128(random);
144 unsigned __int128 b = uniform_uint128(random);
145 values.emplace_back(
146 std::max(a, b),
147 std::max(static_cast<unsigned __int128>(2), std::min(a, b)));
148 }
149 return values;
150 }
151
BM_DivideIntrinsic128UniformDivisor(benchmark::State & state)152 void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) {
153 auto values = GetRandomIntrinsic128SampleUniformDivisor();
154 while (state.KeepRunningBatch(values.size())) {
155 for (const auto& pair : values) {
156 benchmark::DoNotOptimize(pair.first / pair.second);
157 }
158 }
159 }
160 BENCHMARK(BM_DivideIntrinsic128UniformDivisor);
161
162 std::vector<std::pair<unsigned __int128, uint64_t>>
GetRandomIntrinsic128SampleSmallDivisor()163 GetRandomIntrinsic128SampleSmallDivisor() {
164 std::vector<std::pair<unsigned __int128, uint64_t>> values;
165 std::mt19937 random = MakeRandomEngine();
166 UniformIntDistribution128 uniform_uint128;
167 std::uniform_int_distribution<uint64_t> uniform_uint64;
168 values.reserve(kSampleSize);
169 for (size_t i = 0; i < kSampleSize; ++i) {
170 unsigned __int128 a = uniform_uint128(random);
171 uint64_t b = std::max(uint64_t{2}, uniform_uint64(random));
172 values.emplace_back(std::max(a, static_cast<unsigned __int128>(b)), b);
173 }
174 return values;
175 }
176
BM_DivideIntrinsic128SmallDivisor(benchmark::State & state)177 void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) {
178 auto values = GetRandomIntrinsic128SampleSmallDivisor();
179 while (state.KeepRunningBatch(values.size())) {
180 for (const auto& pair : values) {
181 benchmark::DoNotOptimize(pair.first / pair.second);
182 }
183 }
184 }
185 BENCHMARK(BM_DivideIntrinsic128SmallDivisor);
186
187 std::vector<std::pair<unsigned __int128, unsigned __int128>>
GetRandomIntrinsic128Sample()188 GetRandomIntrinsic128Sample() {
189 std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
190 std::mt19937 random = MakeRandomEngine();
191 UniformIntDistribution128 uniform_uint128;
192 values.reserve(kSampleSize);
193 for (size_t i = 0; i < kSampleSize; ++i) {
194 values.emplace_back(uniform_uint128(random), uniform_uint128(random));
195 }
196 return values;
197 }
198
BM_MultiplyIntrinsic128(benchmark::State & state)199 void BM_MultiplyIntrinsic128(benchmark::State& state) {
200 auto values = GetRandomIntrinsic128Sample();
201 while (state.KeepRunningBatch(values.size())) {
202 for (const auto& pair : values) {
203 benchmark::DoNotOptimize(pair.first * pair.second);
204 }
205 }
206 }
207 BENCHMARK(BM_MultiplyIntrinsic128);
208
BM_AddIntrinsic128(benchmark::State & state)209 void BM_AddIntrinsic128(benchmark::State& state) {
210 auto values = GetRandomIntrinsic128Sample();
211 while (state.KeepRunningBatch(values.size())) {
212 for (const auto& pair : values) {
213 benchmark::DoNotOptimize(pair.first + pair.second);
214 }
215 }
216 }
217 BENCHMARK(BM_AddIntrinsic128);
218
219 #endif // ABSL_HAVE_INTRINSIC_INT128
220
221 } // namespace
222