Add new dynamic table to look up ancestors of CPU stack samples.
This removes the need for a recursive query which is a significant
performance bottle neck.
I validated the results on a test trace with results here:
https://docs.google.com/spreadsheets/d/1whwjzHbU7QQ1iaR3W-dqLRRBxl5LAY5NKnBeRmidFCk/edit?usp=sharing&resourcekey=0-5u4EtMsfmDyD1X_lvLi9CA
The new method just skips a row in the validation which was repeated
in the recursive query (I think this was a bug? please double check
though).
Trying on the example trace in the bug and selecting a stack sample
from ChromeIOThread over the IOHandler::OnIOCompleted the performance
was similar. This does not bode well for this fix.
Bug: 168056830
Change-Id: I89f2e042d0d4dc43f424272e71aced4c0c426346
diff --git a/Android.bp b/Android.bp
index 3289c41..eb4a59c 100644
--- a/Android.bp
+++ b/Android.bp
@@ -7155,7 +7155,7 @@
filegroup {
name: "perfetto_src_trace_processor_lib",
srcs: [
- "src/trace_processor/dynamic/ancestor_slice_generator.cc",
+ "src/trace_processor/dynamic/ancestor_generator.cc",
"src/trace_processor/dynamic/connected_flow_generator.cc",
"src/trace_processor/dynamic/descendant_slice_generator.cc",
"src/trace_processor/dynamic/describe_slice_generator.cc",
diff --git a/BUILD b/BUILD
index 09effaa..991e2fb 100644
--- a/BUILD
+++ b/BUILD
@@ -1064,8 +1064,8 @@
filegroup(
name = "src_trace_processor_lib",
srcs = [
- "src/trace_processor/dynamic/ancestor_slice_generator.cc",
- "src/trace_processor/dynamic/ancestor_slice_generator.h",
+ "src/trace_processor/dynamic/ancestor_generator.cc",
+ "src/trace_processor/dynamic/ancestor_generator.h",
"src/trace_processor/dynamic/connected_flow_generator.cc",
"src/trace_processor/dynamic/connected_flow_generator.h",
"src/trace_processor/dynamic/descendant_slice_generator.cc",
diff --git a/src/trace_processor/BUILD.gn b/src/trace_processor/BUILD.gn
index b6641ab..2d18f6d 100644
--- a/src/trace_processor/BUILD.gn
+++ b/src/trace_processor/BUILD.gn
@@ -289,8 +289,8 @@
if (enable_perfetto_trace_processor_sqlite) {
source_set("lib") {
sources = [
- "dynamic/ancestor_slice_generator.cc",
- "dynamic/ancestor_slice_generator.h",
+ "dynamic/ancestor_generator.cc",
+ "dynamic/ancestor_generator.h",
"dynamic/connected_flow_generator.cc",
"dynamic/connected_flow_generator.h",
"dynamic/descendant_slice_generator.cc",
diff --git a/src/trace_processor/dynamic/ancestor_generator.cc b/src/trace_processor/dynamic/ancestor_generator.cc
new file mode 100644
index 0000000..3cb6356
--- /dev/null
+++ b/src/trace_processor/dynamic/ancestor_generator.cc
@@ -0,0 +1,140 @@
+/*
+ * Copyright (C) 2020 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 "src/trace_processor/dynamic/ancestor_generator.h"
+
+#include <memory>
+#include <set>
+
+#include "src/trace_processor/types/trace_processor_context.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+uint32_t GetConstraintColumnIndex(AncestorGenerator::Ancestor type,
+ TraceProcessorContext* context) {
+ switch (type) {
+ case AncestorGenerator::Ancestor::kSlice:
+ return context->storage->slice_table().GetColumnCount();
+ case AncestorGenerator::Ancestor::kStackProfileCallsite:
+ return context->storage->stack_profile_callsite_table().GetColumnCount();
+ }
+ return 0;
+}
+
+template <typename T>
+std::unique_ptr<Table> BuildAncestors(const T& table, uint32_t starting_id) {
+ auto start_row = table.id().IndexOf(typename T::Id(starting_id));
+
+ if (!start_row) {
+ // TODO(lalitm): Ideally this should result in an error, or be filtered out
+ // during ValidateConstraints so we can just dereference |start_row|
+ // directly. However ValidateConstraints doesn't know the value we're
+ // filtering for so can't ensure it exists. For now we return a nullptr
+ // which will cause the query to surface an error with the message "SQL
+ // error: constraint failed".
+ return nullptr;
+ }
+
+ // Build up all the parents row ids, and a new column that includes the
+ // constraint.
+ std::vector<uint32_t> ids;
+ std::unique_ptr<NullableVector<uint32_t>> child_ids(
+ new NullableVector<uint32_t>());
+
+ auto maybe_parent_id = table.parent_id()[*start_row];
+ while (maybe_parent_id) {
+ ids.push_back(maybe_parent_id.value().value);
+ child_ids->Append(starting_id);
+ // Update the loop variable by looking up the next parent_id.
+ maybe_parent_id = table.parent_id()[*table.id().IndexOf(*maybe_parent_id)];
+ }
+ return std::unique_ptr<Table>(
+ new Table(table.Apply(RowMap(std::move(ids)))
+ .ExtendWithColumn("start_id", std::move(child_ids),
+ TypedColumn<uint32_t>::default_flags() |
+ TypedColumn<uint32_t>::kHidden)));
+}
+} // namespace
+
+AncestorGenerator::AncestorGenerator(Ancestor type,
+ TraceProcessorContext* context)
+ : type_(type), context_(context) {}
+
+util::Status AncestorGenerator::ValidateConstraints(
+ const QueryConstraints& qc) {
+ const auto& cs = qc.constraints();
+
+ int column = static_cast<int>(GetConstraintColumnIndex(type_, context_));
+ auto id_fn = [column](const QueryConstraints::Constraint& c) {
+ return c.column == column && c.op == SQLITE_INDEX_CONSTRAINT_EQ;
+ };
+ bool has_id_cs = std::find_if(cs.begin(), cs.end(), id_fn) != cs.end();
+ return has_id_cs ? util::OkStatus()
+ : util::ErrStatus("Failed to find required constraints");
+}
+
+std::unique_ptr<Table> AncestorGenerator::ComputeTable(
+ const std::vector<Constraint>& cs,
+ const std::vector<Order>&) {
+ uint32_t column = GetConstraintColumnIndex(type_, context_);
+ auto it = std::find_if(cs.begin(), cs.end(), [column](const Constraint& c) {
+ return c.col_idx == column && c.op == FilterOp::kEq;
+ });
+ PERFETTO_DCHECK(it != cs.end());
+
+ auto start_id = static_cast<uint32_t>(it->value.AsLong());
+ switch (type_) {
+ case Ancestor::kSlice:
+ return BuildAncestors(context_->storage->slice_table(), start_id);
+ case Ancestor::kStackProfileCallsite:
+ return BuildAncestors(context_->storage->stack_profile_callsite_table(),
+ start_id);
+ }
+ return nullptr;
+}
+
+Table::Schema AncestorGenerator::CreateSchema() {
+ Table::Schema final_schema;
+ switch (type_) {
+ case Ancestor::kSlice:
+ final_schema = tables::SliceTable::Schema();
+ break;
+ case Ancestor::kStackProfileCallsite:
+ final_schema = tables::StackProfileCallsiteTable::Schema();
+ break;
+ }
+ final_schema.columns.push_back(Table::Schema::Column{
+ "start_id", SqlValue::Type::kLong, /* is_id = */ false,
+ /* is_sorted = */ false, /* is_hidden = */ true});
+ return final_schema;
+}
+
+std::string AncestorGenerator::TableName() {
+ switch (type_) {
+ case Ancestor::kSlice:
+ return "ancestor_slice";
+ case Ancestor::kStackProfileCallsite:
+ return "experimental_ancestor_stack_profile_callsite";
+ }
+ return "ancestor_unknown";
+}
+
+uint32_t AncestorGenerator::EstimateRowCount() {
+ return 1;
+}
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/dynamic/ancestor_slice_generator.h b/src/trace_processor/dynamic/ancestor_generator.h
similarity index 77%
rename from src/trace_processor/dynamic/ancestor_slice_generator.h
rename to src/trace_processor/dynamic/ancestor_generator.h
index 265172e..e39d25d 100644
--- a/src/trace_processor/dynamic/ancestor_slice_generator.h
+++ b/src/trace_processor/dynamic/ancestor_generator.h
@@ -14,8 +14,8 @@
* limitations under the License.
*/
-#ifndef SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_SLICE_GENERATOR_H_
-#define SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_SLICE_GENERATOR_H_
+#ifndef SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_GENERATOR_H_
+#define SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_GENERATOR_H_
#include "src/trace_processor/sqlite/db_sqlite_table.h"
@@ -29,10 +29,11 @@
// Dynamic table for implementing the table.
// See /docs/analysis.md for details about the functionality and usage of this
// table.
-class AncestorSliceGenerator : public DbSqliteTable::DynamicTableGenerator {
+class AncestorGenerator : public DbSqliteTable::DynamicTableGenerator {
public:
- explicit AncestorSliceGenerator(TraceProcessorContext* context);
- ~AncestorSliceGenerator() override;
+ enum class Ancestor { kSlice = 1, kStackProfileCallsite = 2 };
+
+ AncestorGenerator(Ancestor type, TraceProcessorContext* context);
Table::Schema CreateSchema() override;
std::string TableName() override;
@@ -42,10 +43,11 @@
const std::vector<Order>& ob) override;
private:
+ Ancestor type_;
TraceProcessorContext* context_ = nullptr;
};
} // namespace trace_processor
} // namespace perfetto
-#endif // SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_SLICE_GENERATOR_H_
+#endif // SRC_TRACE_PROCESSOR_DYNAMIC_ANCESTOR_GENERATOR_H_
diff --git a/src/trace_processor/dynamic/ancestor_slice_generator.cc b/src/trace_processor/dynamic/ancestor_slice_generator.cc
deleted file mode 100644
index ff17f91..0000000
--- a/src/trace_processor/dynamic/ancestor_slice_generator.cc
+++ /dev/null
@@ -1,110 +0,0 @@
-/*
- * Copyright (C) 2020 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 "src/trace_processor/dynamic/ancestor_slice_generator.h"
-
-#include <memory>
-#include <set>
-
-#include "src/trace_processor/types/trace_processor_context.h"
-
-namespace perfetto {
-namespace trace_processor {
-
-AncestorSliceGenerator::AncestorSliceGenerator(TraceProcessorContext* context)
- : context_(context) {}
-
-AncestorSliceGenerator::~AncestorSliceGenerator() = default;
-
-util::Status AncestorSliceGenerator::ValidateConstraints(
- const QueryConstraints& qc) {
- const auto& cs = qc.constraints();
-
- auto slice_id_fn = [this](const QueryConstraints::Constraint& c) {
- return c.column == static_cast<int>(
- context_->storage->slice_table().GetColumnCount()) &&
- c.op == SQLITE_INDEX_CONSTRAINT_EQ;
- };
- bool has_slice_id_cs =
- std::find_if(cs.begin(), cs.end(), slice_id_fn) != cs.end();
-
- return has_slice_id_cs
- ? util::OkStatus()
- : util::ErrStatus("Failed to find required constraints");
-}
-
-std::unique_ptr<Table> AncestorSliceGenerator::ComputeTable(
- const std::vector<Constraint>& cs,
- const std::vector<Order>&) {
- using S = tables::SliceTable;
-
- auto it = std::find_if(cs.begin(), cs.end(), [this](const Constraint& c) {
- return c.col_idx == context_->storage->slice_table().GetColumnCount() &&
- c.op == FilterOp::kEq;
- });
- PERFETTO_DCHECK(it != cs.end());
-
- const auto& slice = context_->storage->slice_table();
- uint32_t child_id = static_cast<uint32_t>(it->value.AsLong());
- auto start_row = slice.id().IndexOf(S::Id(child_id));
-
- if (!start_row) {
- // TODO(lalitm): Ideally this should result in an error, or be filtered out
- // during ValidateConstraints so we can just dereference |start_row|
- // directly. However ValidateConstraints doesn't know the value we're
- // filtering for so can't ensure it exists. For now we return a nullptr
- // which will cause the query to surface an error with the message "SQL
- // error: constraint failed".
- return nullptr;
- }
-
- // Build up all the parents row ids, and a new column that includes the
- // constraint.
- std::vector<uint32_t> ids;
- std::unique_ptr<NullableVector<uint32_t>> child_ids(
- new NullableVector<uint32_t>());
-
- auto maybe_parent_id = slice.parent_id()[*start_row];
- while (maybe_parent_id) {
- ids.push_back(maybe_parent_id.value().value);
- child_ids->Append(child_id);
- // Update the loop variable by looking up the next parent_id.
- maybe_parent_id = slice.parent_id()[*slice.id().IndexOf(*maybe_parent_id)];
- }
- return std::unique_ptr<Table>(
- new Table(slice.Apply(RowMap(std::move(ids)))
- .ExtendWithColumn("start_id", std::move(child_ids),
- TypedColumn<uint32_t>::default_flags() |
- TypedColumn<uint32_t>::kHidden)));
-}
-
-Table::Schema AncestorSliceGenerator::CreateSchema() {
- auto schema = tables::SliceTable::Schema();
- schema.columns.push_back(Table::Schema::Column{
- "start_id", SqlValue::Type::kLong, /* is_id = */ false,
- /* is_sorted = */ false, /* is_hidden = */ true});
- return schema;
-}
-
-std::string AncestorSliceGenerator::TableName() {
- return "ancestor_slice";
-}
-
-uint32_t AncestorSliceGenerator::EstimateRowCount() {
- return 1;
-}
-} // namespace trace_processor
-} // namespace perfetto
diff --git a/src/trace_processor/trace_processor_impl.cc b/src/trace_processor/trace_processor_impl.cc
index c401d7b..1fc79f6 100644
--- a/src/trace_processor/trace_processor_impl.cc
+++ b/src/trace_processor/trace_processor_impl.cc
@@ -23,7 +23,7 @@
#include "perfetto/base/time.h"
#include "perfetto/ext/base/string_splitter.h"
#include "perfetto/ext/base/string_utils.h"
-#include "src/trace_processor/dynamic/ancestor_slice_generator.h"
+#include "src/trace_processor/dynamic/ancestor_generator.h"
#include "src/trace_processor/dynamic/connected_flow_generator.h"
#include "src/trace_processor/dynamic/descendant_slice_generator.h"
#include "src/trace_processor/dynamic/describe_slice_generator.h"
@@ -740,8 +740,10 @@
new ExperimentalSliceLayoutGenerator(
context_.storage.get()->mutable_string_pool(),
&storage->slice_table())));
- RegisterDynamicTable(std::unique_ptr<AncestorSliceGenerator>(
- new AncestorSliceGenerator(&context_)));
+ RegisterDynamicTable(std::unique_ptr<AncestorGenerator>(
+ new AncestorGenerator(AncestorGenerator::Ancestor::kSlice, &context_)));
+ RegisterDynamicTable(std::unique_ptr<AncestorGenerator>(new AncestorGenerator(
+ AncestorGenerator::Ancestor::kStackProfileCallsite, &context_)));
RegisterDynamicTable(std::unique_ptr<DescendantSliceGenerator>(
new DescendantSliceGenerator(&context_)));
RegisterDynamicTable(
diff --git a/ui/src/controller/cpu_profile_controller.ts b/ui/src/controller/cpu_profile_controller.ts
index 1450e94..f53d28c 100644
--- a/ui/src/controller/cpu_profile_controller.ts
+++ b/ui/src/controller/cpu_profile_controller.ts
@@ -105,21 +105,21 @@
stack_profile_mapping.name AS mapping_name
FROM
(
- WITH
- RECURSIVE
- callsite_parser(callsite_id, current_id, position)
- AS (
- SELECT id, id, 0 FROM stack_profile_callsite
- UNION
- SELECT callsite_id, parent_id, position + 1
- FROM callsite_parser
- JOIN
- stack_profile_callsite
- ON stack_profile_callsite.id = current_id
- WHERE stack_profile_callsite.depth > 0
- )
- SELECT *
- FROM callsite_parser
+ SELECT
+ stack.id as callsite_id,
+ COALESCE(ancestor.id, stack.id) as current_id,
+ stack.depth - COALESCE(ancestor.depth, stack.depth) as position
+ FROM
+ stack_profile_callsite stack LEFT JOIN
+ experimental_ancestor_stack_profile_callsite(stack.id) AS
+ ancestor
+ UNION ALL
+ SELECT
+ id,
+ id,
+ 0
+ FROM stack_profile_callsite
+ WHERE parent_id IS NOT NULL AND id != 0
) AS flattened_callsite
LEFT JOIN stack_profile_callsite AS spc
LEFT JOIN