[stdlib]: Add a generic critical path graph module
This brings us closer to productionizing and generalizing
the critical path algorithm. Still in experimental until the API
is fully fledged.
2 functions extracted out:
1. _critical_path(graph_table, root_table)
2. _critical_path_intervals(graph_table, root_table, interval_table)
The first works completely in id space, the second 'flattens' for the UI
Change-Id: I04130e421eb7ccdb43965fccc01e809c6afbae61
diff --git a/Android.bp b/Android.bp
index 11c9b2a..279cfe9 100644
--- a/Android.bp
+++ b/Android.bp
@@ -13163,6 +13163,7 @@
"src/trace_processor/perfetto_sql/stdlib/deprecated/v42/common/slices.sql",
"src/trace_processor/perfetto_sql/stdlib/deprecated/v42/common/timestamps.sql",
"src/trace_processor/perfetto_sql/stdlib/export/to_firefox_profile.sql",
+ "src/trace_processor/perfetto_sql/stdlib/graphs/critical_path.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/partition.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/scan.sql",
diff --git a/BUILD b/BUILD
index 24543ae..cf94216 100644
--- a/BUILD
+++ b/BUILD
@@ -2662,6 +2662,7 @@
perfetto_filegroup(
name = "src_trace_processor_perfetto_sql_stdlib_graphs_graphs",
srcs = [
+ "src/trace_processor/perfetto_sql/stdlib/graphs/critical_path.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/partition.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/scan.sql",
diff --git a/src/trace_processor/perfetto_sql/stdlib/graphs/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/graphs/BUILD.gn
index 1710494..5167835 100644
--- a/src/trace_processor/perfetto_sql/stdlib/graphs/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/stdlib/graphs/BUILD.gn
@@ -16,6 +16,7 @@
perfetto_sql_source_set("graphs") {
sources = [
+ "critical_path.sql",
"dominator_tree.sql",
"partition.sql",
"scan.sql",
diff --git a/src/trace_processor/perfetto_sql/stdlib/graphs/critical_path.sql b/src/trace_processor/perfetto_sql/stdlib/graphs/critical_path.sql
new file mode 100644
index 0000000..652f8c0
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/graphs/critical_path.sql
@@ -0,0 +1,190 @@
+--
+-- Copyright 2024 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
+--
+-- https://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 PERFETTO MODULE graphs.search;
+
+-- Computes critical paths, the dependency graph of a task.
+-- The critical path is a set of edges reachable from a root node with the sum of the edge
+-- weights just exceeding the root node capacity. This ensures that the tasks in the critical path
+-- completely 'covers' the root capacity.
+-- Typically, every node represents a point in time on some task where it transitioned from
+-- idle to active state.
+--
+-- Example usage on traces with Linux sched information:
+-- ```
+-- -- Compute the userspace critical path from every task sleep.
+-- SELECT * FROM
+-- critical_path_intervals!(
+-- _wakeup_userspace_edges,
+-- (SELECT id AS root_node_id, prev_id - id FROM _wakeup_graph WHERE prev_id IS NOT NULL));
+-- ```
+CREATE PERFETTO MACRO _critical_path(
+ -- A table/view/subquery corresponding to a directed graph on which the
+ -- reachability search should be performed. This table must have the columns
+ -- "source_node_id", "dest_node_id" and "edge_weight" corresponding to the two nodes on
+ -- either end of the edges in the graph and the edge weight.
+ --
+ -- Note: the columns must contain uint32 similar to ids in trace processor
+ -- tables (i.e. the values should be relatively dense and close to zero). The
+ -- implementation makes assumptions on this for performance reasons and, if
+ -- this criteria is not, can lead to enormous amounts of memory being
+ -- allocated.
+ -- An edge weight is the absolute difference between the node ids forming the edge.
+ graph_table TableOrSubQuery,
+ -- A table/view/subquery corresponding to start nodes to |graph_table| which will be the
+ -- roots of the reachability trees. This table must have the columns
+ -- "root_node_id" and "capacity" corresponding to the starting node id and the capacity
+ -- of the root node to contain edge weights.
+ --
+ -- Note: the columns must contain uint32 similar to ids in trace processor
+ -- tables (i.e. the values should be relatively dense and close to zero). The
+ -- implementation makes assumptions on this for performance reasons and, if
+ -- this criteria is not, can lead to enormous amounts of memory being
+ -- allocated.
+ root_table TableOrSubQuery)
+ -- The returned table has the schema (root_id UINT32, id UINT32, parent_id UINT32).
+ -- |root_id| is the id of the root where the critical path computation started.
+ -- |id| is the id of a node in the critical path and |parent_id| is the predecessor of |id|.
+RETURNS TableOrSubQuery
+AS (
+ WITH
+ _edges AS (
+ SELECT source_node_id, dest_node_id, edge_weight FROM $graph_table
+ ),
+ _roots AS (
+ SELECT
+ root_node_id,
+ capacity AS root_target_weight
+ FROM $root_table
+ ),
+ _search_bounds AS (
+ SELECT MIN(root_node_id - root_target_weight) AS min_wakeup,
+ MAX(root_node_id + root_target_weight) AS max_wakeup
+ FROM _roots
+ ),
+ _graph AS (
+ SELECT
+ source_node_id,
+ COALESCE(dest_node_id, source_node_id) AS dest_node_id,
+ edge_weight
+ FROM _edges
+ JOIN _search_bounds
+ WHERE source_node_id BETWEEN min_wakeup AND max_wakeup AND source_node_id IS NOT NULL
+ )
+ SELECT DISTINCT
+ root_node_id AS root_id,
+ parent_node_id AS parent_id,
+ node_id AS id
+ FROM graph_reachable_weight_bounded_dfs !(_graph, _roots, 1) cr
+);
+
+-- Flattens overlapping tasks within a critical path and flattens overlapping critical paths.
+CREATE PERFETTO MACRO _critical_path_to_intervals(critical_path_table TableOrSubquery,
+ node_table TableOrSubquery)
+RETURNS TableOrSubquery
+AS (
+ WITH flat_tasks AS (
+ SELECT
+ node.ts,
+ cr.root_id,
+ cr.id,
+ LEAD(node.ts) OVER (PARTITION BY cr.root_id ORDER BY cr.id) - node.ts AS dur
+ FROM $critical_path_table cr
+ JOIN $node_table node USING(id)
+ ), span_starts AS (
+ SELECT
+ MAX(cr.ts, idle.ts - idle_dur) AS ts,
+ idle.ts AS idle_end_ts,
+ cr.ts + cr.dur AS cr_end_ts,
+ cr.id,
+ cr.root_id
+ FROM flat_tasks cr
+ JOIN $node_table idle ON cr.root_id = idle.id
+ )
+ SELECT
+ ts,
+ MIN(cr_end_ts, idle_end_ts) - ts AS dur,
+ id,
+ root_id
+ FROM span_starts
+ WHERE MIN(idle_end_ts, cr_end_ts) - ts > 0
+);
+
+-- Computes critical paths, the dependency graph of a task and returns a flattened view suitable
+-- for displaying in a UI track without any overlapping intervals.
+-- See the _critical_path MACRO above.
+--
+-- Example usage on traces with Linux sched information:
+-- ```
+-- -- Compute the userspace critical path from every task sleep.
+-- SELECT * FROM
+-- critical_path_intervals!(
+-- _wakeup_userspace_edges,
+-- (SELECT id AS root_node_id, prev_id - id FROM _wakeup_graph WHERE prev_id IS NOT NULL),
+-- _wakeup_intervals);
+-- ```
+CREATE PERFETTO MACRO _critical_path_intervals(
+ -- A table/view/subquery corresponding to a directed graph on which the
+ -- reachability search should be performed. This table must have the columns
+ -- "source_node_id", "dest_node_id" and "edge_weight" corresponding to the two nodes on
+ -- either end of the edges in the graph and the edge weight.
+ --
+ -- Note: the columns must contain uint32 similar to ids in trace processor
+ -- tables (i.e. the values should be relatively dense and close to zero). The
+ -- implementation makes assumptions on this for performance reasons and, if
+ -- this criteria is not, can lead to enormous amounts of memory being
+ -- allocated.
+ -- An edge weight is the absolute difference between the node ids forming the edge.
+ graph_table TableOrSubQuery,
+ -- A table/view/subquery corresponding to start nodes to |graph_table| which will be the
+ -- roots of the reachability trees. This table must have the columns
+ -- "root_node_id" and "capacity" corresponding to the starting node id and the capacity
+ -- of the root node to contain edge weights.
+ --
+ -- Note: the columns must contain uint32 similar to ids in trace processor
+ -- tables (i.e. the values should be relatively dense and close to zero). The
+ -- implementation makes assumptions on this for performance reasons and, if
+ -- this criteria is not, can lead to enormous amounts of memory being
+ -- allocated.
+ root_table TableOrSubQuery,
+ -- A table/view/subquery corresponding to the idle to active transition points on a task.
+ -- This table must have the columns, "id", "ts", "dur" and "idle_dur". ts and dur is the
+ -- timestamp when the task became active and how long it was active for respectively. idle_dur
+ -- is the duration it was idle for before it became active at "ts".
+ --
+ -- Note: the columns must contain uint32 similar to ids in trace processor
+ -- tables (i.e. the values should be relatively dense and close to zero). The
+ -- implementation makes assumptions on this for performance reasons and, if
+ -- this criteria is not, can lead to enormous amounts of memory being
+ -- allocated.
+ -- There should be one row for every node id encountered in the |graph_table|.
+ interval_table TableOrSubQuery)
+-- The returned table has the schema (id UINT32, ts INT64, dur INT64, idle_dur INT64).
+-- |root_node_id| is the id of the starting node under which this edge was encountered.
+-- |node_id| is the id of the node from the input graph and |parent_node_id|
+-- is the id of the node which was the first encountered predecessor in a DFS
+-- search of the graph.
+RETURNS TableOrSubQuery
+AS (
+ WITH _critical_path_nodes AS (
+ SELECT root_id, id FROM _critical_path!($graph_table, $root_table)
+ ) SELECT root_id, id, ts, dur
+ FROM _critical_path_to_intervals !(_critical_path_nodes, $interval_table)
+ UNION ALL
+ SELECT node.id AS root_id, node.id, node.ts, node.dur
+ FROM $interval_table node
+ JOIN $root_table ON root_node_id = id
+);
diff --git a/test/trace_processor/diff_tests/include_index.py b/test/trace_processor/diff_tests/include_index.py
index 534344f..b57a139 100644
--- a/test/trace_processor/diff_tests/include_index.py
+++ b/test/trace_processor/diff_tests/include_index.py
@@ -110,6 +110,7 @@
from diff_tests.stdlib.counters.tests import StdlibCounterIntervals
from diff_tests.stdlib.dynamic_tables.tests import DynamicTables
from diff_tests.stdlib.export.tests import ExportTests
+from diff_tests.stdlib.graphs.critical_path_tests import CriticalPathTests
from diff_tests.stdlib.graphs.dominator_tree_tests import DominatorTree
from diff_tests.stdlib.graphs.partition_tests import GraphPartitionTests
from diff_tests.stdlib.graphs.scan_tests import GraphScanTests
@@ -275,6 +276,7 @@
*AndroidStdlib(index_path, 'stdlib/android', 'AndroidStdlib').fetch(),
*LinuxCpu(index_path, 'stdlib/linux/cpu', 'LinuxCpu').fetch(),
*DominatorTree(index_path, 'stdlib/graphs', 'DominatorTree').fetch(),
+ *CriticalPathTests(index_path, 'stdlib/graphs', 'CriticalPath').fetch(),
*GraphScanTests(index_path, 'stdlib/graphs', 'GraphScan').fetch(),
*ExportTests(index_path, 'stdlib/export', 'ExportTests').fetch(),
*Frames(index_path, 'stdlib/android', 'Frames').fetch(),
diff --git a/test/trace_processor/diff_tests/stdlib/graphs/critical_path_tests.py b/test/trace_processor/diff_tests/stdlib/graphs/critical_path_tests.py
new file mode 100644
index 0000000..7b746aa
--- /dev/null
+++ b/test/trace_processor/diff_tests/stdlib/graphs/critical_path_tests.py
@@ -0,0 +1,104 @@
+#!/usr/bin/env python3
+# Copyright (C) 2024 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 a
+#
+# 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.
+
+from python.generators.diff_tests.testing import DataPath
+from python.generators.diff_tests.testing import Csv
+from python.generators.diff_tests.testing import DiffTestBlueprint
+from python.generators.diff_tests.testing import TestSuite
+
+class CriticalPathTests(TestSuite):
+
+ def test_critical_path_empty(self):
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE graphs.critical_path;
+
+ WITH edge AS (
+ SELECT 0 as source_node_id, 0 AS dest_node_id
+ WHERE FALSE
+ ), root AS (
+ SELECT 0 as root_node_id, 0 AS capacity
+ WHERE FALSE
+ )
+ SELECT * FROM _critical_path!(
+ (SELECT *, source_node_id - dest_node_id AS edge_weight FROM edge),
+ root
+ );
+ """,
+ out=Csv("""
+ "root_id","parent_id","id"
+ """))
+
+ def test_critical_path(self):
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE graphs.critical_path;
+
+ WITH edge(source_node_id, dest_node_id) AS (
+ values(8, 7), (7, 6), (6, 5), (6, 4), (4, 1), (5, 3), (3, 0)
+ ), root(root_node_id, capacity) AS (
+ values(8, 6)
+ )
+ SELECT * FROM _critical_path!(
+ (SELECT *, source_node_id - dest_node_id AS edge_weight FROM edge),
+ root
+ );
+ """,
+ out=Csv("""
+ "root_id","parent_id","id"
+ 8,"[NULL]",8
+ 8,3,0
+ 8,5,3
+ 8,6,5
+ 8,7,6
+ 8,8,7
+ """))
+
+ def test_critical_path_intervals(self):
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE graphs.critical_path;
+
+ WITH edge(source_node_id, dest_node_id) AS (
+ values(8, 7), (7, 6), (6, 5), (6, 4), (4, 1), (5, 3), (3, 0)
+ ), root(root_node_id, capacity) AS (
+ values(8, 6)
+ ), interval(id, ts, dur, idle_dur) AS (
+ values(8, 8, 1, 6),
+ (7, 7, 1, 1),
+ (6, 6, 1, 1),
+ (5, 5, 1, 1),
+ (4, 4, 1, 1),
+ (3, 3, 1, 1),
+ (2, 2, 1, 1),
+ (1, 1, 1, 1)
+ )
+ SELECT * FROM _critical_path_intervals!(
+ (SELECT *, source_node_id - dest_node_id AS edge_weight FROM edge),
+ root,
+ interval
+ );
+ """,
+ out=Csv("""
+ "root_id","id","ts","dur"
+ 8,3,3,2
+ 8,5,5,1
+ 8,6,6,1
+ 8,7,7,1
+ 8,8,8,1
+ """))
