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 <cstdlib>
17 #include <optional>
18 #include <random>
19
20 #include <benchmark/benchmark.h>
21
22 #include "perfetto/trace_processor/basic_types.h"
23 #include "src/trace_processor/containers/row_map.h"
24 #include "src/trace_processor/containers/string_pool.h"
25 #include "src/trace_processor/db/column/types.h"
26 #include "src/trace_processor/db/table.h"
27 #include "src/trace_processor/tables/py_tables_benchmark_py.h"
28
29 namespace perfetto::trace_processor::tables {
30
31 RootTestTable::~RootTestTable() = default;
32 ChildTestTable::~ChildTestTable() = default;
33
34 } // namespace perfetto::trace_processor::tables
35
36 namespace {
37
IsBenchmarkFunctionalOnly()38 bool IsBenchmarkFunctionalOnly() {
39 return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
40 }
41
TableFilterArgs(benchmark::internal::Benchmark * b)42 void TableFilterArgs(benchmark::internal::Benchmark* b) {
43 if (IsBenchmarkFunctionalOnly()) {
44 b->Arg(1024);
45 } else {
46 b->Arg(2ull * 1024 * 1024);
47 }
48 }
49
TableSortArgs(benchmark::internal::Benchmark * b)50 void TableSortArgs(benchmark::internal::Benchmark* b) {
51 if (IsBenchmarkFunctionalOnly()) {
52 b->Arg(64);
53 } else {
54 b->Arg(256ull * 1024);
55 }
56 }
57
58 } // namespace
59
60 using perfetto::trace_processor::Query;
61 using perfetto::trace_processor::RowMap;
62 using perfetto::trace_processor::SqlValue;
63 using perfetto::trace_processor::StringPool;
64 using perfetto::trace_processor::Table;
65 using perfetto::trace_processor::tables::ChildTestTable;
66 using perfetto::trace_processor::tables::RootTestTable;
67
BM_TableInsert(benchmark::State & state)68 static void BM_TableInsert(benchmark::State& state) {
69 StringPool pool;
70 RootTestTable root(&pool);
71
72 for (auto _ : state) {
73 benchmark::DoNotOptimize(root.Insert({}));
74 }
75 }
76 BENCHMARK(BM_TableInsert);
77
BM_TableIteratorChild(benchmark::State & state)78 static void BM_TableIteratorChild(benchmark::State& state) {
79 StringPool pool;
80 RootTestTable root(&pool);
81 ChildTestTable child(&pool, &root);
82
83 uint32_t size = static_cast<uint32_t>(state.range(0));
84 for (uint32_t i = 0; i < size; ++i) {
85 child.Insert({});
86 root.Insert({});
87 }
88
89 auto it = static_cast<Table&>(child).IterateRows();
90 for (auto _ : state) {
91 for (uint32_t i = 0; i < child.columns().size(); ++i) {
92 benchmark::DoNotOptimize(it.Get(i));
93 }
94 if (!++it)
95 it = static_cast<Table&>(child).IterateRows();
96 }
97 }
98 BENCHMARK(BM_TableIteratorChild)->Apply(TableFilterArgs);
99
BM_TableFilterRootId(benchmark::State & state)100 static void BM_TableFilterRootId(benchmark::State& state) {
101 StringPool pool;
102 RootTestTable root(&pool);
103 Query q;
104 q.constraints = {root.id().eq(30)};
105
106 uint32_t size = static_cast<uint32_t>(state.range(0));
107 for (uint32_t i = 0; i < size; ++i)
108 root.Insert({});
109
110 for (auto _ : state) {
111 benchmark::DoNotOptimize(root.FilterToIterator(q));
112 }
113 }
114 BENCHMARK(BM_TableFilterRootId)->Apply(TableFilterArgs);
115
BM_TableFilterRootIdAndOther(benchmark::State & state)116 static void BM_TableFilterRootIdAndOther(benchmark::State& state) {
117 StringPool pool;
118 RootTestTable root(&pool);
119 Query q;
120 q.constraints = {root.id().eq(root.row_count() - 1),
121 root.root_non_null().gt(100)};
122
123 uint32_t size = static_cast<uint32_t>(state.range(0));
124
125 for (uint32_t i = 0; i < size; ++i) {
126 RootTestTable::Row root_row;
127 root_row.root_non_null = i * 4;
128 root.Insert(root_row);
129 }
130
131 for (auto _ : state) {
132 benchmark::DoNotOptimize(root.FilterToIterator(q));
133 }
134 }
135 BENCHMARK(BM_TableFilterRootIdAndOther)->Apply(TableFilterArgs);
136
BM_TableFilterChildId(benchmark::State & state)137 static void BM_TableFilterChildId(benchmark::State& state) {
138 StringPool pool;
139 RootTestTable root(&pool);
140 ChildTestTable child(&pool, &root);
141 Query q;
142 q.constraints = {child.id().eq(30)};
143
144 uint32_t size = static_cast<uint32_t>(state.range(0));
145 for (uint32_t i = 0; i < size; ++i) {
146 root.Insert({});
147 child.Insert({});
148 }
149
150 for (auto _ : state) {
151 benchmark::DoNotOptimize(child.FilterToIterator(q));
152 }
153 }
154 BENCHMARK(BM_TableFilterChildId)->Apply(TableFilterArgs);
155
BM_TableFilterChildIdAndSortedInRoot(benchmark::State & state)156 static void BM_TableFilterChildIdAndSortedInRoot(benchmark::State& state) {
157 StringPool pool;
158 RootTestTable root(&pool);
159 ChildTestTable child(&pool, &root);
160 Query q;
161 q.constraints = {child.id().eq(30), child.root_sorted().gt(1024)};
162
163 uint32_t size = static_cast<uint32_t>(state.range(0));
164 for (uint32_t i = 0; i < size; ++i) {
165 RootTestTable::Row root_row;
166 root_row.root_sorted = i * 2;
167 root.Insert(root_row);
168
169 ChildTestTable::Row child_row;
170 child_row.root_sorted = i * 2 + 1;
171 child.Insert(child_row);
172 }
173
174 for (auto _ : state) {
175 benchmark::DoNotOptimize(child.FilterToIterator(q));
176 }
177 }
178 BENCHMARK(BM_TableFilterChildIdAndSortedInRoot)->Apply(TableFilterArgs);
179
BM_TableFilterRootNonNullEqMatchMany(benchmark::State & state)180 static void BM_TableFilterRootNonNullEqMatchMany(benchmark::State& state) {
181 StringPool pool;
182 RootTestTable root(&pool);
183 Query q;
184 q.constraints = {root.root_non_null().eq(0)};
185
186 auto size = static_cast<uint32_t>(state.range(0));
187 uint32_t partitions = size / 1024;
188
189 std::minstd_rand0 rnd_engine;
190 for (uint32_t i = 0; i < size; ++i) {
191 RootTestTable::Row row(static_cast<uint32_t>(rnd_engine() % partitions));
192 root.Insert(row);
193 }
194
195 for (auto _ : state) {
196 benchmark::DoNotOptimize(root.FilterToIterator(q));
197 }
198 }
199 BENCHMARK(BM_TableFilterRootNonNullEqMatchMany)->Apply(TableFilterArgs);
200
BM_TableFilterRootMultipleNonNull(benchmark::State & state)201 static void BM_TableFilterRootMultipleNonNull(benchmark::State& state) {
202 StringPool pool;
203 RootTestTable root(&pool);
204 Query q;
205 q.constraints = {root.root_non_null().lt(4), root.root_non_null_2().lt(10)};
206
207 auto size = static_cast<uint32_t>(state.range(0));
208 uint32_t partitions = size / 512;
209
210 std::minstd_rand0 rnd_engine;
211 for (uint32_t i = 0; i < size; ++i) {
212 RootTestTable::Row row;
213 row.root_non_null = rnd_engine() % partitions;
214 row.root_non_null_2 = rnd_engine() % partitions;
215 root.Insert(row);
216 }
217
218 for (auto _ : state) {
219 benchmark::DoNotOptimize(root.FilterToIterator(q));
220 }
221 }
222 BENCHMARK(BM_TableFilterRootMultipleNonNull)->Apply(TableFilterArgs);
223
BM_TableFilterRootNullableEqMatchMany(benchmark::State & state)224 static void BM_TableFilterRootNullableEqMatchMany(benchmark::State& state) {
225 StringPool pool;
226 RootTestTable root(&pool);
227 Query q;
228 q.constraints = {root.root_nullable().eq(1)};
229
230 auto size = static_cast<uint32_t>(state.range(0));
231 uint32_t partitions = size / 512;
232
233 std::minstd_rand0 rnd_engine;
234 for (uint32_t i = 0; i < size; ++i) {
235 uint32_t value = rnd_engine() % partitions;
236
237 RootTestTable::Row row;
238 row.root_nullable =
239 value % 2 == 0 ? std::nullopt : std::make_optional(value);
240 root.Insert(row);
241 }
242
243 for (auto _ : state) {
244 benchmark::DoNotOptimize(root.FilterToIterator(q));
245 }
246 }
247 BENCHMARK(BM_TableFilterRootNullableEqMatchMany)->Apply(TableFilterArgs);
248
BM_TableFilterChildNonNullEqMatchMany(benchmark::State & state)249 static void BM_TableFilterChildNonNullEqMatchMany(benchmark::State& state) {
250 StringPool pool;
251 RootTestTable root(&pool);
252 ChildTestTable child(&pool, &root);
253 Query q;
254 q.constraints = {child.child_non_null().eq(0)};
255
256 auto size = static_cast<uint32_t>(state.range(0));
257 uint32_t partitions = size / 1024;
258
259 std::minstd_rand0 rnd_engine;
260 for (uint32_t i = 0; i < size; ++i) {
261 ChildTestTable::Row row;
262 row.child_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
263 root.Insert({});
264 child.Insert(row);
265 }
266
267 for (auto _ : state) {
268 benchmark::DoNotOptimize(child.FilterToIterator(q));
269 }
270 }
271 BENCHMARK(BM_TableFilterChildNonNullEqMatchMany)->Apply(TableFilterArgs);
272
BM_TableFilterChildNullableEqMatchMany(benchmark::State & state)273 static void BM_TableFilterChildNullableEqMatchMany(benchmark::State& state) {
274 StringPool pool;
275 RootTestTable root(&pool);
276 ChildTestTable child(&pool, &root);
277 Query q;
278 q.constraints = {child.child_nullable().eq(1)};
279
280 auto size = static_cast<uint32_t>(state.range(0));
281 uint32_t partitions = size / 512;
282
283 std::minstd_rand0 rnd_engine;
284 for (uint32_t i = 0; i < size; ++i) {
285 uint32_t value = rnd_engine() % partitions;
286
287 ChildTestTable::Row row;
288 row.child_nullable =
289 value % 2 == 0 ? std::nullopt : std::make_optional(value);
290 root.Insert({});
291 child.Insert(row);
292 }
293
294 for (auto _ : state) {
295 benchmark::DoNotOptimize(child.FilterToIterator(q));
296 }
297 }
298 BENCHMARK(BM_TableFilterChildNullableEqMatchMany)->Apply(TableFilterArgs);
299
BM_TableFilterChildNonNullEqMatchManyInParent(benchmark::State & state)300 static void BM_TableFilterChildNonNullEqMatchManyInParent(
301 benchmark::State& state) {
302 StringPool pool;
303 RootTestTable root(&pool);
304 ChildTestTable child(&pool, &root);
305 Query q;
306 q.constraints = {child.root_non_null().eq(0)};
307
308 auto size = static_cast<uint32_t>(state.range(0));
309 uint32_t partitions = size / 1024;
310
311 std::minstd_rand0 rnd_engine;
312 for (uint32_t i = 0; i < size; ++i) {
313 ChildTestTable::Row row;
314 row.root_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
315 root.Insert({});
316 child.Insert(row);
317 }
318
319 for (auto _ : state) {
320 benchmark::DoNotOptimize(child.FilterToIterator(q));
321 }
322 }
323 BENCHMARK(BM_TableFilterChildNonNullEqMatchManyInParent)
324 ->Apply(TableFilterArgs);
325
BM_TableFilterChildNullableEqMatchManyInParent(benchmark::State & state)326 static void BM_TableFilterChildNullableEqMatchManyInParent(
327 benchmark::State& state) {
328 StringPool pool;
329 RootTestTable root(&pool);
330 ChildTestTable child(&pool, &root);
331
332 auto size = static_cast<uint32_t>(state.range(0));
333 uint32_t partitions = size / 512;
334
335 std::minstd_rand0 rnd_engine;
336 for (uint32_t i = 0; i < size; ++i) {
337 ChildTestTable::Row row;
338 row.root_nullable = static_cast<uint32_t>(rnd_engine() % partitions);
339 root.Insert({});
340 child.Insert(row);
341 }
342
343 Query q;
344 q.constraints = {child.root_nullable().eq(1)};
345 for (auto _ : state) {
346 benchmark::DoNotOptimize(child.FilterToIterator(q));
347 }
348 }
349 BENCHMARK(BM_TableFilterChildNullableEqMatchManyInParent)
350 ->Apply(TableFilterArgs);
351
BM_TableFilterParentSortedEq(benchmark::State & state)352 static void BM_TableFilterParentSortedEq(benchmark::State& state) {
353 StringPool pool;
354 RootTestTable root(&pool);
355
356 auto size = static_cast<uint32_t>(state.range(0));
357
358 for (uint32_t i = 0; i < size; ++i) {
359 RootTestTable::Row row;
360 row.root_sorted = i * 2;
361 root.Insert(row);
362 }
363
364 Query q;
365 q.constraints = {root.root_sorted().eq(22)};
366 for (auto _ : state) {
367 benchmark::DoNotOptimize(root.FilterToIterator(q));
368 }
369 }
370 BENCHMARK(BM_TableFilterParentSortedEq)->Apply(TableFilterArgs);
371
BM_TableFilterParentSortedAndOther(benchmark::State & state)372 static void BM_TableFilterParentSortedAndOther(benchmark::State& state) {
373 StringPool pool;
374 RootTestTable root(&pool);
375
376 auto size = static_cast<uint32_t>(state.range(0));
377
378 for (uint32_t i = 0; i < size; ++i) {
379 // Group the rows into rows of 10. This emulates the behaviour of e.g.
380 // args.
381 RootTestTable::Row row;
382 row.root_sorted = (i / 10) * 10;
383 row.root_non_null = i;
384 root.Insert(row);
385 }
386
387 // We choose to search for the last group as if there is O(n^2), it will
388 // be more easily visible.
389 uint32_t last_group = ((size - 1) / 10) * 10;
390 Query q;
391 q.constraints = {root.root_sorted().eq(last_group),
392 root.root_non_null().eq(size - 1)};
393 for (auto _ : state) {
394 benchmark::DoNotOptimize(root.FilterToIterator(q));
395 }
396 }
397 BENCHMARK(BM_TableFilterParentSortedAndOther)->Apply(TableFilterArgs);
398
BM_TableFilterChildSortedEq(benchmark::State & state)399 static void BM_TableFilterChildSortedEq(benchmark::State& state) {
400 StringPool pool;
401 RootTestTable root(&pool);
402 ChildTestTable child(&pool, &root);
403
404 auto size = static_cast<uint32_t>(state.range(0));
405
406 for (uint32_t i = 0; i < size; ++i) {
407 ChildTestTable::Row row;
408 row.child_sorted = i * 2;
409 root.Insert({});
410 child.Insert(row);
411 }
412
413 Query q;
414 q.constraints = {child.child_sorted().eq(22)};
415 for (auto _ : state) {
416 benchmark::DoNotOptimize(child.FilterToIterator(q));
417 }
418 }
419 BENCHMARK(BM_TableFilterChildSortedEq)->Apply(TableFilterArgs);
420
BM_TableFilterChildSortedEqInParent(benchmark::State & state)421 static void BM_TableFilterChildSortedEqInParent(benchmark::State& state) {
422 StringPool pool;
423 RootTestTable root(&pool);
424 ChildTestTable child(&pool, &root);
425
426 auto size = static_cast<uint32_t>(state.range(0));
427
428 for (uint32_t i = 0; i < size; ++i) {
429 RootTestTable::Row root_row;
430 root_row.root_sorted = i * 4;
431 root.Insert(root_row);
432
433 ChildTestTable::Row row;
434 row.root_sorted = i * 4 + 2;
435 child.Insert(row);
436 }
437
438 Query q;
439 q.constraints = {child.root_sorted().eq(22)};
440 for (auto _ : state) {
441 benchmark::DoNotOptimize(child.FilterToIterator(q));
442 }
443 }
444 BENCHMARK(BM_TableFilterChildSortedEqInParent)->Apply(TableFilterArgs);
445
BM_TableSortRootNonNull(benchmark::State & state)446 static void BM_TableSortRootNonNull(benchmark::State& state) {
447 StringPool pool;
448 RootTestTable root(&pool);
449
450 auto size = static_cast<uint32_t>(state.range(0));
451
452 std::minstd_rand0 rnd_engine;
453 for (uint32_t i = 0; i < size; ++i) {
454 const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
455
456 RootTestTable::Row row;
457 row.root_non_null = root_value;
458 root.Insert(row);
459 }
460
461 Query q;
462 q.orders = {root.root_non_null().ascending()};
463 for (auto _ : state) {
464 benchmark::DoNotOptimize(root.FilterToIterator(q));
465 }
466 }
467 BENCHMARK(BM_TableSortRootNonNull)->Apply(TableSortArgs);
468
BM_TableSortRootNullable(benchmark::State & state)469 static void BM_TableSortRootNullable(benchmark::State& state) {
470 StringPool pool;
471 RootTestTable root(&pool);
472
473 auto size = static_cast<uint32_t>(state.range(0));
474
475 std::minstd_rand0 rnd_engine;
476 for (uint32_t i = 0; i < size; ++i) {
477 const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
478
479 RootTestTable::Row row;
480 row.root_nullable =
481 root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
482 root.Insert(row);
483 }
484
485 Query q;
486 q.orders = {root.root_nullable().ascending()};
487 for (auto _ : state) {
488 benchmark::DoNotOptimize(root.FilterToIterator(q));
489 }
490 }
491 BENCHMARK(BM_TableSortRootNullable)->Apply(TableSortArgs);
492
BM_TableSortChildNonNullInParent(benchmark::State & state)493 static void BM_TableSortChildNonNullInParent(benchmark::State& state) {
494 StringPool pool;
495 RootTestTable root(&pool);
496 ChildTestTable child(&pool, &root);
497
498 auto size = static_cast<uint32_t>(state.range(0));
499
500 std::minstd_rand0 rnd_engine;
501 for (uint32_t i = 0; i < size; ++i) {
502 const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
503
504 RootTestTable::Row root_row;
505 root_row.root_non_null = root_value;
506 root.Insert(root_row);
507
508 const uint32_t child_value = static_cast<uint32_t>(rnd_engine());
509
510 ChildTestTable::Row child_row;
511 child_row.root_non_null = child_value;
512 child.Insert(child_row);
513 }
514
515 Query q;
516 q.orders = {child.root_non_null().ascending()};
517 for (auto _ : state) {
518 benchmark::DoNotOptimize(child.FilterToIterator(q));
519 }
520 }
521 BENCHMARK(BM_TableSortChildNonNullInParent)->Apply(TableSortArgs);
522
BM_TableSortChildNullableInParent(benchmark::State & state)523 static void BM_TableSortChildNullableInParent(benchmark::State& state) {
524 StringPool pool;
525 RootTestTable root(&pool);
526 ChildTestTable child(&pool, &root);
527
528 auto size = static_cast<uint32_t>(state.range(0));
529
530 std::minstd_rand0 rnd_engine;
531 for (uint32_t i = 0; i < size; ++i) {
532 const auto root_value = static_cast<uint32_t>(rnd_engine());
533
534 RootTestTable::Row root_row;
535 root_row.root_nullable =
536 root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
537 root.Insert(root_row);
538
539 const auto child_value = static_cast<uint32_t>(rnd_engine());
540
541 ChildTestTable::Row child_row;
542 child_row.root_nullable =
543 child_value % 2 == 0 ? std::nullopt : std::make_optional(child_value);
544 child.Insert(child_row);
545 }
546
547 Query q;
548 q.orders = {child.root_nullable().ascending()};
549 for (auto _ : state) {
550 benchmark::DoNotOptimize(child.FilterToIterator(q));
551 }
552 }
553 BENCHMARK(BM_TableSortChildNullableInParent)->Apply(TableSortArgs);
554