1 // Copyright (C) 2019 The Android Open Source Project
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 // http://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 <cstdint>
16 #include <limits>
17 #include <random>
18 #include <vector>
19
20 #include <benchmark/benchmark.h>
21
22 #include "perfetto/base/logging.h"
23 #include "src/trace_processor/containers/bit_vector.h"
24
25 namespace {
26
27 using perfetto::trace_processor::BitVector;
28
IsBenchmarkFunctionalOnly()29 bool IsBenchmarkFunctionalOnly() {
30 return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
31 }
32
BitVectorArgs(benchmark::internal::Benchmark * b)33 void BitVectorArgs(benchmark::internal::Benchmark* b) {
34 std::vector<int> set_percentages;
35 if (IsBenchmarkFunctionalOnly()) {
36 set_percentages = std::vector<int>{50};
37 } else {
38 set_percentages = std::vector<int>{0, 1, 5, 50, 95, 99, 100};
39 }
40
41 for (int percentage : set_percentages) {
42 b->Args({64, percentage});
43
44 if (!IsBenchmarkFunctionalOnly()) {
45 b->Args({512, percentage});
46 b->Args({8192, percentage});
47 b->Args({123456, percentage});
48 b->Args({1234567, percentage});
49 }
50 }
51 }
52
UpdateSetBitsSelectBitsArgs(benchmark::internal::Benchmark * b)53 void UpdateSetBitsSelectBitsArgs(benchmark::internal::Benchmark* b) {
54 if (IsBenchmarkFunctionalOnly()) {
55 b->Args({64, 50, 50});
56 } else {
57 std::vector<int64_t> set_percentages{1, 5, 50, 95, 99};
58 b->ArgsProduct({{1234567}, set_percentages, set_percentages});
59 }
60 }
61
BvWithSizeAndSetPercentage(uint32_t size,uint32_t set_percentage)62 BitVector BvWithSizeAndSetPercentage(uint32_t size, uint32_t set_percentage) {
63 static constexpr uint32_t kRandomSeed = 29;
64 std::minstd_rand0 rnd_engine(kRandomSeed);
65
66 BitVector bv;
67 for (uint32_t i = 0; i < size; ++i) {
68 if (rnd_engine() % 100 < set_percentage) {
69 bv.AppendTrue();
70 } else {
71 bv.AppendFalse();
72 }
73 }
74 return bv;
75 }
76
77 } // namespace
78
BM_BitVectorAppendTrue(benchmark::State & state)79 static void BM_BitVectorAppendTrue(benchmark::State& state) {
80 BitVector bv;
81 for (auto _ : state) {
82 bv.AppendTrue();
83 benchmark::ClobberMemory();
84 }
85 }
86 BENCHMARK(BM_BitVectorAppendTrue);
87
BM_BitVectorAppendFalse(benchmark::State & state)88 static void BM_BitVectorAppendFalse(benchmark::State& state) {
89 BitVector bv;
90 for (auto _ : state) {
91 bv.AppendFalse();
92 benchmark::ClobberMemory();
93 }
94 }
95 BENCHMARK(BM_BitVectorAppendFalse);
96
BM_BitVectorIsSet(benchmark::State & state)97 static void BM_BitVectorIsSet(benchmark::State& state) {
98 static constexpr uint32_t kRandomSeed = 42;
99 std::minstd_rand0 rnd_engine(kRandomSeed);
100
101 BitVector bv = BvWithSizeAndSetPercentage(8192, 50);
102
103 static constexpr uint32_t kPoolSize = 1024 * 1024;
104 std::vector<bool> bit_pool(kPoolSize);
105 std::vector<uint32_t> row_pool(kPoolSize);
106 for (uint32_t i = 0; i < kPoolSize; ++i) {
107 bit_pool[i] = rnd_engine() % 2;
108 row_pool[i] = rnd_engine() % 8192;
109 }
110
111 uint32_t pool_idx = 0;
112 for (auto _ : state) {
113 benchmark::DoNotOptimize(bv.IsSet(row_pool[pool_idx]));
114 pool_idx = (pool_idx + 1) % kPoolSize;
115 }
116 }
117 BENCHMARK(BM_BitVectorIsSet);
118
BM_BitVectorSet(benchmark::State & state)119 static void BM_BitVectorSet(benchmark::State& state) {
120 static constexpr uint32_t kRandomSeed = 42;
121 std::minstd_rand0 rnd_engine(kRandomSeed);
122
123 uint32_t size = static_cast<uint32_t>(state.range(0));
124 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
125
126 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
127
128 static constexpr uint32_t kPoolSize = 1024 * 1024;
129 std::vector<bool> bit_pool(kPoolSize);
130 std::vector<uint32_t> row_pool(kPoolSize);
131 for (uint32_t i = 0; i < kPoolSize; ++i) {
132 bit_pool[i] = rnd_engine() % 2;
133 row_pool[i] = rnd_engine() % size;
134 }
135
136 uint32_t pool_idx = 0;
137 for (auto _ : state) {
138 bv.Set(row_pool[pool_idx]);
139 pool_idx = (pool_idx + 1) % kPoolSize;
140 benchmark::ClobberMemory();
141 }
142 }
143 BENCHMARK(BM_BitVectorSet)->Apply(BitVectorArgs);
144
BM_BitVectorClear(benchmark::State & state)145 static void BM_BitVectorClear(benchmark::State& state) {
146 static constexpr uint32_t kRandomSeed = 42;
147 std::minstd_rand0 rnd_engine(kRandomSeed);
148
149 uint32_t size = static_cast<uint32_t>(state.range(0));
150 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
151
152 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
153
154 static constexpr uint32_t kPoolSize = 1024 * 1024;
155 std::vector<uint32_t> row_pool(kPoolSize);
156 for (uint32_t i = 0; i < kPoolSize; ++i) {
157 row_pool[i] = rnd_engine() % size;
158 }
159
160 uint32_t pool_idx = 0;
161 for (auto _ : state) {
162 bv.Clear(row_pool[pool_idx]);
163 pool_idx = (pool_idx + 1) % kPoolSize;
164 benchmark::ClobberMemory();
165 }
166 }
167 BENCHMARK(BM_BitVectorClear)->Apply(BitVectorArgs);
168
BM_BitVectorIndexOfNthSet(benchmark::State & state)169 static void BM_BitVectorIndexOfNthSet(benchmark::State& state) {
170 static constexpr uint32_t kRandomSeed = 42;
171 std::minstd_rand0 rnd_engine(kRandomSeed);
172
173 uint32_t size = static_cast<uint32_t>(state.range(0));
174 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
175
176 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
177 static constexpr uint32_t kPoolSize = 1024 * 1024;
178 std::vector<uint32_t> row_pool(kPoolSize);
179 uint32_t set_bit_count = bv.CountSetBits();
180 if (set_bit_count == 0) {
181 state.SkipWithError("Cannot find set bit in all zeros bitvector");
182 return;
183 }
184
185 for (uint32_t i = 0; i < kPoolSize; ++i) {
186 row_pool[i] = rnd_engine() % set_bit_count;
187 }
188
189 uint32_t pool_idx = 0;
190 for (auto _ : state) {
191 benchmark::DoNotOptimize(bv.IndexOfNthSet(row_pool[pool_idx]));
192 pool_idx = (pool_idx + 1) % kPoolSize;
193 }
194 }
195 BENCHMARK(BM_BitVectorIndexOfNthSet)->Apply(BitVectorArgs);
196
BM_BitVectorCountSetBits(benchmark::State & state)197 static void BM_BitVectorCountSetBits(benchmark::State& state) {
198 static constexpr uint32_t kRandomSeed = 42;
199 std::minstd_rand0 rnd_engine(kRandomSeed);
200
201 uint32_t size = static_cast<uint32_t>(state.range(0));
202 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
203
204 uint32_t count = 0;
205 BitVector bv;
206 for (uint32_t i = 0; i < size; ++i) {
207 bool value = rnd_engine() % 100 < set_percentage;
208 if (value) {
209 bv.AppendTrue();
210 } else {
211 bv.AppendFalse();
212 }
213
214 if (value)
215 count++;
216 }
217
218 uint32_t res = count;
219 for (auto _ : state) {
220 benchmark::DoNotOptimize(res &= bv.CountSetBits());
221 }
222 PERFETTO_CHECK(res == count);
223 }
224 BENCHMARK(BM_BitVectorCountSetBits)->Apply(BitVectorArgs);
225
BM_BitVectorGetSetBitIndices(benchmark::State & state)226 static void BM_BitVectorGetSetBitIndices(benchmark::State& state) {
227 static constexpr uint32_t kRandomSeed = 42;
228 std::minstd_rand0 rnd_engine(kRandomSeed);
229
230 auto size = static_cast<uint32_t>(state.range(0));
231 auto set_percentage = static_cast<uint32_t>(state.range(1));
232
233 BitVector bv;
234 for (uint32_t i = 0; i < size; ++i) {
235 bool value = rnd_engine() % 100 < set_percentage;
236 if (value) {
237 bv.AppendTrue();
238 } else {
239 bv.AppendFalse();
240 }
241 }
242
243 for (auto _ : state) {
244 benchmark::DoNotOptimize(bv.GetSetBitIndices());
245 }
246 }
247 BENCHMARK(BM_BitVectorGetSetBitIndices)->Apply(BitVectorArgs);
248
BM_BitVectorResize(benchmark::State & state)249 static void BM_BitVectorResize(benchmark::State& state) {
250 static constexpr uint32_t kRandomSeed = 42;
251 std::minstd_rand0 rnd_engine(kRandomSeed);
252
253 static constexpr uint32_t kPoolSize = 1024 * 1024;
254 static constexpr uint32_t kMaxSize = 1234567;
255
256 std::vector<bool> resize_fill_pool(kPoolSize);
257 std::vector<uint32_t> resize_count_pool(kPoolSize);
258 for (uint32_t i = 0; i < kPoolSize; ++i) {
259 resize_fill_pool[i] = rnd_engine() % 2;
260 resize_count_pool[i] = rnd_engine() % kMaxSize;
261 }
262
263 uint32_t pool_idx = 0;
264 BitVector bv;
265 for (auto _ : state) {
266 bv.Resize(resize_count_pool[pool_idx], resize_fill_pool[pool_idx]);
267 pool_idx = (pool_idx + 1) % kPoolSize;
268 benchmark::ClobberMemory();
269 }
270 }
271 BENCHMARK(BM_BitVectorResize);
272
BM_BitVectorUpdateSetBits(benchmark::State & state)273 static void BM_BitVectorUpdateSetBits(benchmark::State& state) {
274 static constexpr uint32_t kRandomSeed = 42;
275 std::minstd_rand0 rnd_engine(kRandomSeed);
276
277 uint32_t size = static_cast<uint32_t>(state.range(0));
278 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
279 uint32_t picker_set_percentage = static_cast<uint32_t>(state.range(2));
280
281 BitVector bv;
282 BitVector picker;
283 for (uint32_t i = 0; i < size; ++i) {
284 bool value = rnd_engine() % 100 < set_percentage;
285 if (value) {
286 bv.AppendTrue();
287
288 bool picker_value = rnd_engine() % 100 < picker_set_percentage;
289 if (picker_value) {
290 picker.AppendTrue();
291 } else {
292 picker.AppendFalse();
293 }
294 } else {
295 bv.AppendFalse();
296 }
297 }
298
299 uint32_t set_bit_count = bv.CountSetBits();
300 uint32_t picker_set_bit_count = picker.CountSetBits();
301
302 for (auto _ : state) {
303 BitVector copy = bv.Copy();
304 copy.UpdateSetBits(picker);
305 benchmark::DoNotOptimize(copy);
306 }
307
308 state.counters["s/set bit"] = benchmark::Counter(
309 set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
310 benchmark::Counter::kInvert);
311 state.counters["s/set picker bit"] = benchmark::Counter(
312 picker_set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
313 benchmark::Counter::kInvert);
314 }
315 BENCHMARK(BM_BitVectorUpdateSetBits)->Apply(UpdateSetBitsSelectBitsArgs);
316
BM_BitVectorSelectBits(benchmark::State & state)317 static void BM_BitVectorSelectBits(benchmark::State& state) {
318 static constexpr uint32_t kRandomSeed = 42;
319 std::minstd_rand0 rnd_engine(kRandomSeed);
320
321 auto size = static_cast<uint32_t>(state.range(0));
322 auto set_percentage = static_cast<uint32_t>(state.range(1));
323 auto mask_set_percentage = static_cast<uint32_t>(state.range(2));
324
325 BitVector bv;
326 BitVector mask;
327 for (uint32_t i = 0; i < size; ++i) {
328 bool value = rnd_engine() % 100 < set_percentage;
329 if (value) {
330 bv.AppendTrue();
331 } else {
332 bv.AppendFalse();
333 }
334 bool mask_value = rnd_engine() % 100 < mask_set_percentage;
335 if (mask_value) {
336 mask.AppendTrue();
337 } else {
338 mask.AppendFalse();
339 }
340 }
341
342 uint32_t set_bit_count = bv.CountSetBits();
343 uint32_t mask_set_bit_count = mask.CountSetBits();
344
345 for (auto _ : state) {
346 BitVector copy = bv.Copy();
347 copy.SelectBits(mask);
348 benchmark::DoNotOptimize(copy);
349 }
350
351 state.counters["s/set bit"] = benchmark::Counter(
352 set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
353 benchmark::Counter::kInvert);
354 state.counters["s/mask bit"] = benchmark::Counter(
355 mask_set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
356 benchmark::Counter::kInvert);
357 }
358 BENCHMARK(BM_BitVectorSelectBits)->Apply(UpdateSetBitsSelectBitsArgs);
359
BM_BitVectorFromIndexVector(benchmark::State & state)360 static void BM_BitVectorFromIndexVector(benchmark::State& state) {
361 std::vector<int64_t> indices;
362 for (int64_t i = 0; i < 1024l * 1024l; i++) {
363 indices.push_back(i);
364 }
365
366 indices.push_back(std::numeric_limits<uint32_t>::max() >> 5);
367
368 for (auto _ : state) {
369 benchmark::DoNotOptimize(BitVector::FromSortedIndexVector(indices));
370 }
371 }
372 BENCHMARK(BM_BitVectorFromIndexVector);
373