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 <random>
16
17 #include <benchmark/benchmark.h>
18
19 #include "src/trace_processor/containers/bit_vector.h"
20 #include "src/trace_processor/containers/bit_vector_iterators.h"
21
22 namespace {
23
24 using perfetto::trace_processor::BitVector;
25
IsBenchmarkFunctionalOnly()26 bool IsBenchmarkFunctionalOnly() {
27 return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
28 }
29
BitVectorArgs(benchmark::internal::Benchmark * b)30 void BitVectorArgs(benchmark::internal::Benchmark* b) {
31 std::vector<int> set_percentages;
32 if (IsBenchmarkFunctionalOnly()) {
33 set_percentages = std::vector<int>{50};
34 } else {
35 set_percentages = std::vector<int>{0, 1, 5, 50, 95, 99, 100};
36 }
37
38 for (int percentage : set_percentages) {
39 b->Args({64, percentage});
40
41 if (!IsBenchmarkFunctionalOnly()) {
42 b->Args({512, percentage});
43 b->Args({8192, percentage});
44 b->Args({123456, percentage});
45 b->Args({1234567, percentage});
46 }
47 }
48 }
49
BvWithSizeAndSetPercentage(uint32_t size,uint32_t set_percentage)50 BitVector BvWithSizeAndSetPercentage(uint32_t size, uint32_t set_percentage) {
51 static constexpr uint32_t kRandomSeed = 29;
52 std::minstd_rand0 rnd_engine(kRandomSeed);
53
54 BitVector bv;
55 for (uint32_t i = 0; i < size; ++i) {
56 if (rnd_engine() % 100 < set_percentage) {
57 bv.AppendTrue();
58 } else {
59 bv.AppendFalse();
60 }
61 }
62 return bv;
63 }
64
65 } // namespace
66
BM_BitVectorAppendTrue(benchmark::State & state)67 static void BM_BitVectorAppendTrue(benchmark::State& state) {
68 BitVector bv;
69 for (auto _ : state) {
70 bv.AppendTrue();
71 benchmark::ClobberMemory();
72 }
73 }
74 BENCHMARK(BM_BitVectorAppendTrue);
75
BM_BitVectorAppendFalse(benchmark::State & state)76 static void BM_BitVectorAppendFalse(benchmark::State& state) {
77 BitVector bv;
78 for (auto _ : state) {
79 bv.AppendFalse();
80 benchmark::ClobberMemory();
81 }
82 }
83 BENCHMARK(BM_BitVectorAppendFalse);
84
BM_BitVectorSet(benchmark::State & state)85 static void BM_BitVectorSet(benchmark::State& state) {
86 static constexpr uint32_t kRandomSeed = 42;
87 std::minstd_rand0 rnd_engine(kRandomSeed);
88
89 uint32_t size = static_cast<uint32_t>(state.range(0));
90 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
91
92 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
93
94 static constexpr uint32_t kPoolSize = 1024 * 1024;
95 std::vector<bool> bit_pool(kPoolSize);
96 std::vector<uint32_t> row_pool(kPoolSize);
97 for (uint32_t i = 0; i < kPoolSize; ++i) {
98 bit_pool[i] = rnd_engine() % 2;
99 row_pool[i] = rnd_engine() % size;
100 }
101
102 uint32_t pool_idx = 0;
103 for (auto _ : state) {
104 bv.Set(row_pool[pool_idx]);
105 pool_idx = (pool_idx + 1) % kPoolSize;
106 benchmark::ClobberMemory();
107 }
108 }
109 BENCHMARK(BM_BitVectorSet)->Apply(BitVectorArgs);
110
BM_BitVectorClear(benchmark::State & state)111 static void BM_BitVectorClear(benchmark::State& state) {
112 static constexpr uint32_t kRandomSeed = 42;
113 std::minstd_rand0 rnd_engine(kRandomSeed);
114
115 uint32_t size = static_cast<uint32_t>(state.range(0));
116 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
117
118 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
119
120 static constexpr uint32_t kPoolSize = 1024 * 1024;
121 std::vector<uint32_t> row_pool(kPoolSize);
122 for (uint32_t i = 0; i < kPoolSize; ++i) {
123 row_pool[i] = rnd_engine() % size;
124 }
125
126 uint32_t pool_idx = 0;
127 for (auto _ : state) {
128 bv.Clear(row_pool[pool_idx]);
129 pool_idx = (pool_idx + 1) % kPoolSize;
130 benchmark::ClobberMemory();
131 }
132 }
133 BENCHMARK(BM_BitVectorClear)->Apply(BitVectorArgs);
134
BM_BitVectorIndexOfNthSet(benchmark::State & state)135 static void BM_BitVectorIndexOfNthSet(benchmark::State& state) {
136 static constexpr uint32_t kRandomSeed = 42;
137 std::minstd_rand0 rnd_engine(kRandomSeed);
138
139 uint32_t size = static_cast<uint32_t>(state.range(0));
140 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
141
142 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
143 static constexpr uint32_t kPoolSize = 1024 * 1024;
144 std::vector<uint32_t> row_pool(kPoolSize);
145 uint32_t set_bit_count = bv.GetNumBitsSet();
146 if (set_bit_count == 0)
147 return;
148
149 for (uint32_t i = 0; i < kPoolSize; ++i) {
150 row_pool[i] = rnd_engine() % set_bit_count;
151 }
152
153 uint32_t pool_idx = 0;
154 for (auto _ : state) {
155 benchmark::DoNotOptimize(bv.IndexOfNthSet(row_pool[pool_idx]));
156 pool_idx = (pool_idx + 1) % kPoolSize;
157 }
158 }
159 BENCHMARK(BM_BitVectorIndexOfNthSet)->Apply(BitVectorArgs);
160
BM_BitVectorGetNumBitsSet(benchmark::State & state)161 static void BM_BitVectorGetNumBitsSet(benchmark::State& state) {
162 static constexpr uint32_t kRandomSeed = 42;
163 std::minstd_rand0 rnd_engine(kRandomSeed);
164
165 uint32_t size = static_cast<uint32_t>(state.range(0));
166 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
167
168 uint32_t count = 0;
169 BitVector bv;
170 for (uint32_t i = 0; i < size; ++i) {
171 bool value = rnd_engine() % 100 < set_percentage;
172 if (value) {
173 bv.AppendTrue();
174 } else {
175 bv.AppendFalse();
176 }
177
178 if (value)
179 count++;
180 }
181
182 uint32_t res = count;
183 for (auto _ : state) {
184 benchmark::DoNotOptimize(res &= bv.GetNumBitsSet());
185 }
186 PERFETTO_CHECK(res == count);
187 }
188 BENCHMARK(BM_BitVectorGetNumBitsSet)->Apply(BitVectorArgs);
189
BM_BitVectorResize(benchmark::State & state)190 static void BM_BitVectorResize(benchmark::State& state) {
191 static constexpr uint32_t kRandomSeed = 42;
192 std::minstd_rand0 rnd_engine(kRandomSeed);
193
194 static constexpr uint32_t kPoolSize = 1024 * 1024;
195 static constexpr uint32_t kMaxSize = 1234567;
196
197 std::vector<bool> resize_fill_pool(kPoolSize);
198 std::vector<uint32_t> resize_count_pool(kPoolSize);
199 for (uint32_t i = 0; i < kPoolSize; ++i) {
200 resize_fill_pool[i] = rnd_engine() % 2;
201 resize_count_pool[i] = rnd_engine() % kMaxSize;
202 }
203
204 uint32_t pool_idx = 0;
205 BitVector bv;
206 for (auto _ : state) {
207 bv.Resize(resize_count_pool[pool_idx], resize_fill_pool[pool_idx]);
208 pool_idx = (pool_idx + 1) % kPoolSize;
209 benchmark::ClobberMemory();
210 }
211 }
212 BENCHMARK(BM_BitVectorResize);
213
BM_BitVectorRangeFixedSize(benchmark::State & state)214 static void BM_BitVectorRangeFixedSize(benchmark::State& state) {
215 static constexpr uint32_t kRandomSeed = 42;
216 std::minstd_rand0 rnd_engine(kRandomSeed);
217
218 uint32_t size = static_cast<uint32_t>(state.range(0));
219 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
220
221 std::vector<uint32_t> resize_fill_pool(size);
222 for (uint32_t i = 0; i < size; ++i) {
223 resize_fill_pool[i] = rnd_engine() % 100 < set_percentage ? 90 : 100;
224 }
225
226 for (auto _ : state) {
227 auto filler = [&resize_fill_pool](uint32_t i) PERFETTO_ALWAYS_INLINE {
228 return resize_fill_pool[i] < 95;
229 };
230 BitVector bv = BitVector::Range(0, size, filler);
231 benchmark::ClobberMemory();
232 }
233 }
234 BENCHMARK(BM_BitVectorRangeFixedSize)->Apply(BitVectorArgs);
235
BM_BitVectorUpdateSetBits(benchmark::State & state)236 static void BM_BitVectorUpdateSetBits(benchmark::State& state) {
237 static constexpr uint32_t kRandomSeed = 42;
238 std::minstd_rand0 rnd_engine(kRandomSeed);
239
240 uint32_t size = static_cast<uint32_t>(state.range(0));
241 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
242
243 BitVector bv;
244 BitVector picker;
245 for (uint32_t i = 0; i < size; ++i) {
246 bool value = rnd_engine() % 100 < set_percentage;
247 if (value) {
248 bv.AppendTrue();
249
250 bool picker_value = rnd_engine() % 2;
251 if (picker_value) {
252 picker.AppendTrue();
253 } else {
254 picker.AppendFalse();
255 }
256 } else {
257 bv.AppendFalse();
258 }
259 }
260
261 for (auto _ : state) {
262 state.PauseTiming();
263 BitVector copy = bv.Copy();
264 state.ResumeTiming();
265
266 copy.UpdateSetBits(picker);
267 benchmark::ClobberMemory();
268 }
269 }
270 BENCHMARK(BM_BitVectorUpdateSetBits)->Apply(BitVectorArgs);
271
BM_BitVectorSetBitsIterator(benchmark::State & state)272 static void BM_BitVectorSetBitsIterator(benchmark::State& state) {
273 uint32_t size = static_cast<uint32_t>(state.range(0));
274 uint32_t set_percentage = static_cast<uint32_t>(state.range(1));
275
276 BitVector bv = BvWithSizeAndSetPercentage(size, set_percentage);
277 for (auto _ : state) {
278 for (auto it = bv.IterateSetBits(); it; it.Next()) {
279 benchmark::DoNotOptimize(it.index());
280 }
281 }
282 }
283 BENCHMARK(BM_BitVectorSetBitsIterator)->Apply(BitVectorArgs);
284