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_BitVectorSet(benchmark::State & state)97 static void BM_BitVectorSet(benchmark::State& state) {
98 static constexpr uint32_t kRandomSeed = 42;
99 std::minstd_rand0 rnd_engine(kRandomSeed);
100
101 uint32_t size = static_cast<uint32_t>(state.range(0));
102 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
103
104 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
105
106 static constexpr uint32_t kPoolSize = 1024 * 1024;
107 std::vector<bool> bit_pool(kPoolSize);
108 std::vector<uint32_t> row_pool(kPoolSize);
109 for (uint32_t i = 0; i < kPoolSize; ++i) {
110 bit_pool[i] = rnd_engine() % 2;
111 row_pool[i] = rnd_engine() % size;
112 }
113
114 uint32_t pool_idx = 0;
115 for (auto _ : state) {
116 bv.Set(row_pool[pool_idx]);
117 pool_idx = (pool_idx + 1) % kPoolSize;
118 benchmark::ClobberMemory();
119 }
120 }
121 BENCHMARK(BM_BitVectorSet)->Apply(BitVectorArgs);
122
BM_BitVectorClear(benchmark::State & state)123 static void BM_BitVectorClear(benchmark::State& state) {
124 static constexpr uint32_t kRandomSeed = 42;
125 std::minstd_rand0 rnd_engine(kRandomSeed);
126
127 uint32_t size = static_cast<uint32_t>(state.range(0));
128 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
129
130 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
131
132 static constexpr uint32_t kPoolSize = 1024 * 1024;
133 std::vector<uint32_t> row_pool(kPoolSize);
134 for (uint32_t i = 0; i < kPoolSize; ++i) {
135 row_pool[i] = rnd_engine() % size;
136 }
137
138 uint32_t pool_idx = 0;
139 for (auto _ : state) {
140 bv.Clear(row_pool[pool_idx]);
141 pool_idx = (pool_idx + 1) % kPoolSize;
142 benchmark::ClobberMemory();
143 }
144 }
145 BENCHMARK(BM_BitVectorClear)->Apply(BitVectorArgs);
146
BM_BitVectorIndexOfNthSet(benchmark::State & state)147 static void BM_BitVectorIndexOfNthSet(benchmark::State& state) {
148 static constexpr uint32_t kRandomSeed = 42;
149 std::minstd_rand0 rnd_engine(kRandomSeed);
150
151 uint32_t size = static_cast<uint32_t>(state.range(0));
152 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
153
154 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
155 static constexpr uint32_t kPoolSize = 1024 * 1024;
156 std::vector<uint32_t> row_pool(kPoolSize);
157 uint32_t set_bit_count = bv.CountSetBits();
158 if (set_bit_count == 0) {
159 state.SkipWithError("Cannot find set bit in all zeros bitvector");
160 return;
161 }
162
163 for (uint32_t i = 0; i < kPoolSize; ++i) {
164 row_pool[i] = rnd_engine() % set_bit_count;
165 }
166
167 uint32_t pool_idx = 0;
168 for (auto _ : state) {
169 benchmark::DoNotOptimize(bv.IndexOfNthSet(row_pool[pool_idx]));
170 pool_idx = (pool_idx + 1) % kPoolSize;
171 }
172 }
173 BENCHMARK(BM_BitVectorIndexOfNthSet)->Apply(BitVectorArgs);
174
BM_BitVectorCountSetBits(benchmark::State & state)175 static void BM_BitVectorCountSetBits(benchmark::State& state) {
176 static constexpr uint32_t kRandomSeed = 42;
177 std::minstd_rand0 rnd_engine(kRandomSeed);
178
179 uint32_t size = static_cast<uint32_t>(state.range(0));
180 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
181
182 uint32_t count = 0;
183 BitVector bv;
184 for (uint32_t i = 0; i < size; ++i) {
185 bool value = rnd_engine() % 100 < set_percentage;
186 if (value) {
187 bv.AppendTrue();
188 } else {
189 bv.AppendFalse();
190 }
191
192 if (value)
193 count++;
194 }
195
196 uint32_t res = count;
197 for (auto _ : state) {
198 benchmark::DoNotOptimize(res &= bv.CountSetBits());
199 }
200 PERFETTO_CHECK(res == count);
201 }
202 BENCHMARK(BM_BitVectorCountSetBits)->Apply(BitVectorArgs);
203
BM_BitVectorGetSetBitIndices(benchmark::State & state)204 static void BM_BitVectorGetSetBitIndices(benchmark::State& state) {
205 static constexpr uint32_t kRandomSeed = 42;
206 std::minstd_rand0 rnd_engine(kRandomSeed);
207
208 auto size = static_cast<uint32_t>(state.range(0));
209 auto set_percentage = static_cast<uint32_t>(state.range(1));
210
211 BitVector bv;
212 for (uint32_t i = 0; i < size; ++i) {
213 bool value = rnd_engine() % 100 < set_percentage;
214 if (value) {
215 bv.AppendTrue();
216 } else {
217 bv.AppendFalse();
218 }
219 }
220
221 for (auto _ : state) {
222 benchmark::DoNotOptimize(bv.GetSetBitIndices());
223 }
224 }
225 BENCHMARK(BM_BitVectorGetSetBitIndices)->Apply(BitVectorArgs);
226
BM_BitVectorResize(benchmark::State & state)227 static void BM_BitVectorResize(benchmark::State& state) {
228 static constexpr uint32_t kRandomSeed = 42;
229 std::minstd_rand0 rnd_engine(kRandomSeed);
230
231 static constexpr uint32_t kPoolSize = 1024 * 1024;
232 static constexpr uint32_t kMaxSize = 1234567;
233
234 std::vector<bool> resize_fill_pool(kPoolSize);
235 std::vector<uint32_t> resize_count_pool(kPoolSize);
236 for (uint32_t i = 0; i < kPoolSize; ++i) {
237 resize_fill_pool[i] = rnd_engine() % 2;
238 resize_count_pool[i] = rnd_engine() % kMaxSize;
239 }
240
241 uint32_t pool_idx = 0;
242 BitVector bv;
243 for (auto _ : state) {
244 bv.Resize(resize_count_pool[pool_idx], resize_fill_pool[pool_idx]);
245 pool_idx = (pool_idx + 1) % kPoolSize;
246 benchmark::ClobberMemory();
247 }
248 }
249 BENCHMARK(BM_BitVectorResize);
250
BM_BitVectorUpdateSetBits(benchmark::State & state)251 static void BM_BitVectorUpdateSetBits(benchmark::State& state) {
252 static constexpr uint32_t kRandomSeed = 42;
253 std::minstd_rand0 rnd_engine(kRandomSeed);
254
255 uint32_t size = static_cast<uint32_t>(state.range(0));
256 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
257 uint32_t picker_set_percentage = static_cast<uint32_t>(state.range(2));
258
259 BitVector bv;
260 BitVector picker;
261 for (uint32_t i = 0; i < size; ++i) {
262 bool value = rnd_engine() % 100 < set_percentage;
263 if (value) {
264 bv.AppendTrue();
265
266 bool picker_value = rnd_engine() % 100 < picker_set_percentage;
267 if (picker_value) {
268 picker.AppendTrue();
269 } else {
270 picker.AppendFalse();
271 }
272 } else {
273 bv.AppendFalse();
274 }
275 }
276
277 uint32_t set_bit_count = bv.CountSetBits();
278 uint32_t picker_set_bit_count = picker.CountSetBits();
279
280 for (auto _ : state) {
281 BitVector copy = bv.Copy();
282 copy.UpdateSetBits(picker);
283 benchmark::DoNotOptimize(copy);
284 }
285
286 state.counters["s/set bit"] = benchmark::Counter(
287 set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
288 benchmark::Counter::kInvert);
289 state.counters["s/set picker bit"] = benchmark::Counter(
290 picker_set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
291 benchmark::Counter::kInvert);
292 }
293 BENCHMARK(BM_BitVectorUpdateSetBits)->Apply(UpdateSetBitsSelectBitsArgs);
294
BM_BitVectorSelectBits(benchmark::State & state)295 static void BM_BitVectorSelectBits(benchmark::State& state) {
296 static constexpr uint32_t kRandomSeed = 42;
297 std::minstd_rand0 rnd_engine(kRandomSeed);
298
299 auto size = static_cast<uint32_t>(state.range(0));
300 auto set_percentage = static_cast<uint32_t>(state.range(1));
301 auto mask_set_percentage = static_cast<uint32_t>(state.range(2));
302
303 BitVector bv;
304 BitVector mask;
305 for (uint32_t i = 0; i < size; ++i) {
306 bool value = rnd_engine() % 100 < set_percentage;
307 if (value) {
308 bv.AppendTrue();
309 } else {
310 bv.AppendFalse();
311 }
312 bool mask_value = rnd_engine() % 100 < mask_set_percentage;
313 if (mask_value) {
314 mask.AppendTrue();
315 } else {
316 mask.AppendFalse();
317 }
318 }
319
320 uint32_t set_bit_count = bv.CountSetBits();
321 uint32_t mask_set_bit_count = mask.CountSetBits();
322
323 for (auto _ : state) {
324 BitVector copy = bv.Copy();
325 copy.SelectBits(mask);
326 benchmark::DoNotOptimize(copy);
327 }
328
329 state.counters["s/set bit"] = benchmark::Counter(
330 set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
331 benchmark::Counter::kInvert);
332 state.counters["s/mask bit"] = benchmark::Counter(
333 mask_set_bit_count, benchmark::Counter::kIsIterationInvariantRate |
334 benchmark::Counter::kInvert);
335 }
336 BENCHMARK(BM_BitVectorSelectBits)->Apply(UpdateSetBitsSelectBitsArgs);
337
BM_BitVectorFromIndexVector(benchmark::State & state)338 static void BM_BitVectorFromIndexVector(benchmark::State& state) {
339 std::vector<int64_t> indices;
340 for (int64_t i = 0; i < 1024l * 1024l; i++) {
341 indices.push_back(i);
342 }
343
344 indices.push_back(std::numeric_limits<uint32_t>::max() >> 5);
345
346 for (auto _ : state) {
347 benchmark::DoNotOptimize(BitVector::FromSortedIndexVector(indices));
348 }
349 }
350 BENCHMARK(BM_BitVectorFromIndexVector);
351