blob: c946696bdf7a585ef713447364b4a3ab16c641c3 [file] [log] [blame]
// Copyright (C) 2019 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include <random>
#include <benchmark/benchmark.h>
#include "src/trace_processor/tables/macros.h"
namespace perfetto {
namespace trace_processor {
namespace {
#define PERFETTO_TP_ROOT_TEST_TABLE(NAME, PARENT, C) \
NAME(RootTestTable, "root_table") \
PERFETTO_TP_ROOT_TABLE(PARENT, C) \
C(uint32_t, root_sorted, Column::Flag::kSorted) \
C(uint32_t, root_non_null) \
C(uint32_t, root_non_null_2) \
C(std::optional<uint32_t>, root_nullable)
PERFETTO_TP_TABLE(PERFETTO_TP_ROOT_TEST_TABLE);
#define PERFETTO_TP_CHILD_TABLE(NAME, PARENT, C) \
NAME(ChildTestTable, "child_table") \
PARENT(PERFETTO_TP_ROOT_TEST_TABLE, C) \
C(uint32_t, child_sorted, Column::Flag::kSorted) \
C(uint32_t, child_non_null) \
C(std::optional<uint32_t>, child_nullable)
PERFETTO_TP_TABLE(PERFETTO_TP_CHILD_TABLE);
RootTestTable::~RootTestTable() = default;
ChildTestTable::~ChildTestTable() = default;
} // namespace
} // namespace trace_processor
} // namespace perfetto
namespace {
bool IsBenchmarkFunctionalOnly() {
return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
}
void TableFilterArgs(benchmark::internal::Benchmark* b) {
if (IsBenchmarkFunctionalOnly()) {
b->Arg(1024);
} else {
b->RangeMultiplier(8);
b->Range(1024, 2 * 1024 * 1024);
}
}
void TableSortArgs(benchmark::internal::Benchmark* b) {
if (IsBenchmarkFunctionalOnly()) {
b->Arg(64);
} else {
b->RangeMultiplier(8);
b->Range(1024, 256 * 1024);
}
}
} // namespace
using perfetto::trace_processor::ChildTestTable;
using perfetto::trace_processor::RootTestTable;
using perfetto::trace_processor::RowMap;
using perfetto::trace_processor::SqlValue;
using perfetto::trace_processor::StringPool;
using perfetto::trace_processor::Table;
static void BM_TableInsert(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
for (auto _ : state) {
benchmark::DoNotOptimize(root.Insert({}));
}
}
BENCHMARK(BM_TableInsert);
static void BM_TableIteratorChild(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
child.Insert({});
root.Insert({});
}
auto it = static_cast<Table&>(child).IterateRows();
for (auto _ : state) {
for (uint32_t i = 0; i < child.GetColumnCount(); ++i) {
benchmark::DoNotOptimize(it.Get(i));
}
it.Next();
if (!it)
it = static_cast<Table&>(child).IterateRows();
}
}
BENCHMARK(BM_TableIteratorChild)->Apply(TableFilterArgs);
static void BM_TableFilterAndSortRoot(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = 8;
std::minstd_rand0 rnd_engine(45);
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row row;
row.root_non_null = rnd_engine() % partitions;
row.root_non_null_2 = static_cast<uint32_t>(rnd_engine());
root.Insert(row);
}
for (auto _ : state) {
Table filtered = root.Filter({root.root_non_null().eq(5)},
RowMap::OptimizeFor::kLookupSpeed);
benchmark::DoNotOptimize(
filtered.Sort({root.root_non_null_2().ascending()}));
}
}
BENCHMARK(BM_TableFilterAndSortRoot)->Apply(TableFilterArgs);
static void BM_TableFilterRootId(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i)
root.Insert({});
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter({root.id().eq(30)}));
}
}
BENCHMARK(BM_TableFilterRootId)->Apply(TableFilterArgs);
static void BM_TableFilterRootIdAndOther(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row root_row;
root_row.root_non_null = i * 4;
root.Insert(root_row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter(
{root.id().eq(root.row_count() - 1), root.root_non_null().gt(100)}));
}
}
BENCHMARK(BM_TableFilterRootIdAndOther)->Apply(TableFilterArgs);
static void BM_TableFilterChildId(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
root.Insert({});
child.Insert({});
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.id().eq(30)}));
}
}
BENCHMARK(BM_TableFilterChildId)->Apply(TableFilterArgs);
static void BM_TableFilterChildIdAndSortedInRoot(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row root_row;
root_row.root_sorted = i * 2;
root.Insert(root_row);
ChildTestTable::Row child_row;
child_row.root_sorted = i * 2 + 1;
child.Insert(child_row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(
child.Filter({child.id().eq(30), child.root_sorted().gt(1024)}));
}
}
BENCHMARK(BM_TableFilterChildIdAndSortedInRoot)->Apply(TableFilterArgs);
static void BM_TableFilterRootNonNullEqMatchMany(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 1024;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row row(static_cast<uint32_t>(rnd_engine() % partitions));
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter({root.root_non_null().eq(0)}));
}
}
BENCHMARK(BM_TableFilterRootNonNullEqMatchMany)->Apply(TableFilterArgs);
static void BM_TableFilterRootMultipleNonNull(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 512;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row row;
row.root_non_null = rnd_engine() % partitions;
row.root_non_null_2 = rnd_engine() % partitions;
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter(
{root.root_non_null().lt(4), root.root_non_null_2().lt(10)}));
}
}
BENCHMARK(BM_TableFilterRootMultipleNonNull)->Apply(TableFilterArgs);
static void BM_TableFilterRootNullableEqMatchMany(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 512;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
uint32_t value = rnd_engine() % partitions;
RootTestTable::Row row;
row.root_nullable =
value % 2 == 0 ? std::nullopt : std::make_optional(value);
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter({root.root_nullable().eq(1)}));
}
}
BENCHMARK(BM_TableFilterRootNullableEqMatchMany)->Apply(TableFilterArgs);
static void BM_TableFilterChildNonNullEqMatchMany(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 1024;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
ChildTestTable::Row row;
row.child_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
root.Insert({});
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.child_non_null().eq(0)}));
}
}
BENCHMARK(BM_TableFilterChildNonNullEqMatchMany)->Apply(TableFilterArgs);
static void BM_TableFilterChildNullableEqMatchMany(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 512;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
uint32_t value = rnd_engine() % partitions;
ChildTestTable::Row row;
row.child_nullable =
value % 2 == 0 ? std::nullopt : std::make_optional(value);
root.Insert({});
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.child_nullable().eq(1)}));
}
}
BENCHMARK(BM_TableFilterChildNullableEqMatchMany)->Apply(TableFilterArgs);
static void BM_TableFilterChildNonNullEqMatchManyInParent(
benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 1024;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
ChildTestTable::Row row;
row.root_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
root.Insert({});
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.root_non_null().eq(0)}));
}
}
BENCHMARK(BM_TableFilterChildNonNullEqMatchManyInParent)
->Apply(TableFilterArgs);
static void BM_TableFilterChildNullableEqMatchManyInParent(
benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
uint32_t partitions = size / 512;
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
ChildTestTable::Row row;
row.root_nullable = static_cast<uint32_t>(rnd_engine() % partitions);
root.Insert({});
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.root_nullable().eq(1)}));
}
}
BENCHMARK(BM_TableFilterChildNullableEqMatchManyInParent)
->Apply(TableFilterArgs);
static void BM_TableFilterParentSortedEq(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row row;
row.root_sorted = i * 2;
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter({root.root_sorted().eq(22)}));
}
}
BENCHMARK(BM_TableFilterParentSortedEq)->Apply(TableFilterArgs);
static void BM_TableFilterParentSortedAndOther(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
// Group the rows into rows of 10. This emulates the behaviour of e.g.
// args.
RootTestTable::Row row;
row.root_sorted = (i / 10) * 10;
row.root_non_null = i;
root.Insert(row);
}
// We choose to search for the last group as if there is O(n^2), it will
// be more easily visible.
uint32_t last_group = ((size - 1) / 10) * 10;
for (auto _ : state) {
benchmark::DoNotOptimize(root.Filter({root.root_sorted().eq(last_group),
root.root_non_null().eq(size - 1)}));
}
}
BENCHMARK(BM_TableFilterParentSortedAndOther)->Apply(TableFilterArgs);
static void BM_TableFilterChildSortedEq(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
ChildTestTable::Row row;
row.child_sorted = i * 2;
root.Insert({});
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.child_sorted().eq(22)}));
}
}
BENCHMARK(BM_TableFilterChildSortedEq)->Apply(TableFilterArgs);
static void BM_TableFilterChildSortedEqInParent(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
for (uint32_t i = 0; i < size; ++i) {
RootTestTable::Row root_row;
root_row.root_sorted = i * 4;
root.Insert(root_row);
ChildTestTable::Row row;
row.root_sorted = i * 4 + 2;
child.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Filter({child.root_sorted().eq(22)}));
}
}
BENCHMARK(BM_TableFilterChildSortedEqInParent)->Apply(TableFilterArgs);
static void BM_TableSortRootNonNull(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
RootTestTable::Row row;
row.root_non_null = root_value;
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Sort({root.root_non_null().ascending()}));
}
}
BENCHMARK(BM_TableSortRootNonNull)->Apply(TableSortArgs);
static void BM_TableSortRootNullable(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
uint32_t size = static_cast<uint32_t>(state.range(0));
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
RootTestTable::Row row;
row.root_nullable =
root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
root.Insert(row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(root.Sort({root.root_nullable().ascending()}));
}
}
BENCHMARK(BM_TableSortRootNullable)->Apply(TableSortArgs);
static void BM_TableSortChildNonNullInParent(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
RootTestTable::Row root_row;
root_row.root_non_null = root_value;
root.Insert(root_row);
const uint32_t child_value = static_cast<uint32_t>(rnd_engine());
ChildTestTable::Row child_row;
child_row.root_non_null = child_value;
child.Insert(child_row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Sort({child.root_non_null().ascending()}));
}
}
BENCHMARK(BM_TableSortChildNonNullInParent)->Apply(TableSortArgs);
static void BM_TableSortChildNullableInParent(benchmark::State& state) {
StringPool pool;
RootTestTable root(&pool, nullptr);
ChildTestTable child(&pool, &root);
uint32_t size = static_cast<uint32_t>(state.range(0));
std::minstd_rand0 rnd_engine;
for (uint32_t i = 0; i < size; ++i) {
const uint32_t root_value = static_cast<uint32_t>(rnd_engine());
RootTestTable::Row root_row;
root_row.root_nullable =
root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
root.Insert(root_row);
const uint32_t child_value = static_cast<uint32_t>(rnd_engine());
ChildTestTable::Row child_row;
child_row.root_nullable =
child_value % 2 == 0 ? std::nullopt : std::make_optional(child_value);
child.Insert(child_row);
}
for (auto _ : state) {
benchmark::DoNotOptimize(child.Sort({child.root_nullable().ascending()}));
}
}
BENCHMARK(BM_TableSortChildNullableInParent)->Apply(TableSortArgs);