ui: Three flamegraph perf wins: skip empty walk, pre-floor trim, parentCum Three independent bit-identical optimizations that together shave ~20% off native bottom-up pipeline time (measured -16s on a 17M-walk-row heap-graph trace, 83s -> 67s). All three are surgical: same output, no algorithmic change, just removing wasted work. 1. Skip the empty UNION side in the hash walk. For BOTTOM_UP the downwards walk has empty inits (showDownward=FALSE) so it produces no rows, but graph_scan still does setup work. For TOP_DOWN the upwards walk is similarly empty (isPivot is never true). In the TS layer, only call whichever macro actually produces rows. 2. Pre-floor the trim propagation. The floor threshold (min_value) is now applied at the scan edge filter instead of inside the per-node IIF. Dest nodes below min_value are unreachable from the seeded roots, which is exactly the "dead" semantic the original implementation achieved via +inf propagation. On this trace the scan input shrinks from 8.4M rows to ~108K rows; the propagation step drops from 12.65s to 1.03s. Output bit-identical. 3. Precompute parentCumulativeValue. resolve_groups already does LEFT JOIN $grouped p to assign parentId; pulling p.cumulativeValue through as a new column is free. trim_with_placeholder now carries it forward (placeholders use MIN(d.parentCumulativeValue) since all dropped children of a parent share it). global_layout reads it directly from s instead of doing its own LEFT JOIN $merged p. global_layout drops from 13.2s to 1.0s. Also adds ORDER BY id to trim_with_placeholder. The merged UNION ALL wasn't emitting rows in dense id order, which the journal from the prior commit noted makes graph_scan 5x slower downstream in global_layout. Fixing it recovers global_layout's speedup from E.
diff --git a/src/trace_processor/perfetto_sql/stdlib/viz/flamegraph.sql b/src/trace_processor/perfetto_sql/stdlib/viz/flamegraph.sql index 8018b9e..4207a04 100644 --- a/src/trace_processor/perfetto_sql/stdlib/viz/flamegraph.sql +++ b/src/trace_processor/perfetto_sql/stdlib/viz/flamegraph.sql
@@ -343,6 +343,11 @@ -- _merge_hashes did - 4x fewer JOIN rows, since |grouped| has one row -- per unique hash rather than one per walk visit. -- +-- The parent's cumulativeValue is also carried through as +-- |parentCumulativeValue|. It piggybacks on the LEFT JOIN already used +-- for parentId, so it's essentially free here and lets +-- _viz_flamegraph_global_layout avoid a LEFT JOIN of its own. +-- -- |grouped_cols| are pass-through references to the columns that were -- aggregated by _viz_flamegraph_group_hashes (their names, not the agg -- expressions). @@ -363,6 +368,7 @@ __intrinsic_token_apply!(_viz_flamegraph_g_prefix, $grouped_cols), g.value, g.cumulativeValue, + p.cumulativeValue AS parentCumulativeValue, FALSE AS isPlaceholder FROM $grouped g LEFT JOIN $grouped p ON p.hash = g.parentHash @@ -373,16 +379,19 @@ ORDER BY g.id ); --- Per-node propagation pass for the trim. For each node in |merged| emits: --- alive - whether the node itself survives the join thresholds. +-- Per-node propagation pass for the trim. For each node visited, emits: +-- alive - whether the node survives the join thresholds. -- requiredCum - the cumulativeValue this node's CHILDREN must clear. --- Roots are always alive and emit requiredCum = 0. A node that itself --- failed the thresholds emits requiredCum = +inf, which kills its whole --- subtree on the next step (no cumulativeValue can be >= +inf). +-- Roots are always alive (seeded with requiredCum = 0). A node whose +-- cumulativeValue < parent's requiredCum emits requiredCum = +inf, which +-- kills its whole subtree on the next step. -- --- Computing |alive| inside the scan rather than via a downstream JOIN of --- merged with propagated avoids an N x N pass over the merged tree, which --- on WASM-sized inputs (millions of rows) was the dominant cost. +-- The floor threshold |min_value| is applied by pre-filtering scan +-- edges: only dest nodes whose cumulativeValue clears the floor are +-- propagated. Sub-floor subtrees are naturally dead because scan +-- output excludes unreachable nodes, which is what alive_set reads. +-- This is ~12x faster than keeping the floor check inside the scan on +-- large trees because the scan input shrinks proportionally. -- -- Caller should materialize the result into a Perfetto table with an -- index on |id|, since _viz_flamegraph_trim_with_placeholder looks up @@ -396,11 +405,16 @@ AS ( SELECT id, requiredCum, alive FROM _graph_aggregating_scan!( + -- Edge filter is the floor: exclude dest rows below min_value. + -- The scan can never reach them, so they end up implicitly dead. ( SELECT m.parentId AS source_node_id, m.id AS dest_node_id FROM $merged m WHERE m.parentId IS NOT NULL + AND m.cumulativeValue >= $min_value ), + -- Roots stay alive regardless of floor (matches the prior semantic + -- where the init always seeded TRUE). ( SELECT id, 0.0 AS requiredCum, TRUE AS alive FROM $merged WHERE parentId IS NULL @@ -410,13 +424,11 @@ SELECT x.id, IIF( - t.cumulativeValue >= x.incoming - AND t.cumulativeValue >= $min_value, + t.cumulativeValue >= x.incoming, $ratio * t.cumulativeValue, 1e308 ) AS requiredCum, - (t.cumulativeValue >= x.incoming - AND t.cumulativeValue >= $min_value) AS alive + (t.cumulativeValue >= x.incoming) AS alive FROM ( SELECT id, MIN(requiredCum) AS incoming FROM $table @@ -454,38 +466,47 @@ AS ( WITH _max_id AS ( SELECT COALESCE(MAX(id), 0) AS v FROM $merged + ), + _unsorted AS ( + SELECT + m.id, m.parentId, m.depth, m.name, + __intrinsic_token_apply!(_col_list_id, $grouping), + __intrinsic_token_apply!(_col_list_id, $grouped), + m.value, m.cumulativeValue, m.parentCumulativeValue, + FALSE AS isPlaceholder + FROM $merged m + JOIN $alive a USING (id) + UNION ALL + SELECT + (SELECT v FROM _max_id) + + ROW_NUMBER() OVER (ORDER BY d.parentId, (d.depth > 0)) AS id, + d.parentId, + -- All dropped children of one parent on one side of the root share + -- the same depth in a tree, so MIN/MAX/ANY are equivalent. + MIN(d.depth) AS depth, + '(merged)' AS name, + __intrinsic_token_apply!(_col_list_null, $grouping), + __intrinsic_token_apply!(_col_list_null, $grouped), + SUM(d.value) AS value, + SUM(d.cumulativeValue) AS cumulativeValue, + -- All dropped children of one parent share the same parent, so + -- MIN is just "any" here - we use it to stay inside GROUP BY. + MIN(d.parentCumulativeValue) AS parentCumulativeValue, + TRUE AS isPlaceholder + FROM $merged d + LEFT JOIN $alive a ON a.id = d.id + WHERE + a.id IS NULL + AND d.parentId IS NOT NULL + AND d.parentId IN (SELECT id FROM $alive) + -- A root node can have both upward and downward dropped subtrees; + -- keep them as separate placeholders since they sit on opposite sides. + GROUP BY d.parentId, (d.depth > 0) ) - SELECT - m.id, m.parentId, m.depth, m.name, - __intrinsic_token_apply!(_col_list_id, $grouping), - __intrinsic_token_apply!(_col_list_id, $grouped), - m.value, m.cumulativeValue, - FALSE AS isPlaceholder - FROM $merged m - JOIN $alive a USING (id) - UNION ALL - SELECT - (SELECT v FROM _max_id) - + ROW_NUMBER() OVER (ORDER BY d.parentId, (d.depth > 0)) AS id, - d.parentId, - -- All dropped children of one parent on one side of the root share - -- the same depth in a tree, so MIN/MAX/ANY are equivalent. - MIN(d.depth) AS depth, - '(merged)' AS name, - __intrinsic_token_apply!(_col_list_null, $grouping), - __intrinsic_token_apply!(_col_list_null, $grouped), - SUM(d.value) AS value, - SUM(d.cumulativeValue) AS cumulativeValue, - TRUE AS isPlaceholder - FROM $merged d - LEFT JOIN $alive a ON a.id = d.id - WHERE - a.id IS NULL - AND d.parentId IS NOT NULL - AND d.parentId IN (SELECT id FROM $alive) - -- A root node can have both upward and downward dropped subtrees; - -- keep them as separate placeholders since they sit on opposite sides. - GROUP BY d.parentId, (d.depth > 0) + -- Order by id so the resulting Perfetto table is dense in id-order; + -- _viz_flamegraph_global_layout's graph_scan over (parentId, id) is + -- sensitive to non-sequential id storage (~5x slower without). + SELECT * FROM _unsorted ORDER BY id ); -- Performs a "layout" of nodes in the flamegraph relative to their @@ -542,7 +563,7 @@ __intrinsic_token_apply!(_viz_flamegraph_s_prefix, $grouped), s.value AS selfValue, s.cumulativeValue, - p.cumulativeValue AS parentCumulativeValue, + s.parentCumulativeValue, s.depth, g.xStart, g.xEnd, @@ -562,6 +583,5 @@ ) ) g JOIN $merged s USING (id) - LEFT JOIN $merged p ON s.parentId = p.id ORDER BY rootDistance, xStart );
diff --git a/ui/src/components/query_flamegraph.ts b/ui/src/components/query_flamegraph.ts index 10140d9..09ec133 100644 --- a/ui/src/components/query_flamegraph.ts +++ b/ui/src/components/query_flamegraph.ts
@@ -441,20 +441,16 @@ // per-merged-row representative, which is ~4x cheaper than joining at // every walk row. We deliberately skip ORDER BY here - the grouping // step uses a hash index instead. - disposable.use( - await createPerfettoTable({ - engine, - name: `_flamegraph_hash_${uuid}`, - as: ` - select * - from _viz_flamegraph_downwards_hash!( - _flamegraph_source_${uuid}, - _flamegraph_filtered_${uuid}, - _flamegraph_accumulated_${uuid}, - ${groupedColumns}, - ${view.kind === 'BOTTOM_UP' ? 'FALSE' : 'TRUE'} - ) - union all + // + // Only one of upwards/downwards is non-empty for a given view: + // BOTTOM_UP: upwards_hash has pivot-seeded inits, downwards_hash + // is empty (showDownward=FALSE). + // TOP_DOWN: downwards_hash has root-seeded inits, upwards_hash is + // empty (no rows match the pivot filter). + // So we skip the empty side entirely to avoid its graph_scan setup. + const hashWalkSql = + view.kind === 'BOTTOM_UP' + ? ` select * from _viz_flamegraph_upwards_hash!( _flamegraph_source_${uuid}, @@ -462,7 +458,22 @@ _flamegraph_accumulated_${uuid}, ${groupedColumns} ) - `, + ` + : ` + select * + from _viz_flamegraph_downwards_hash!( + _flamegraph_source_${uuid}, + _flamegraph_filtered_${uuid}, + _flamegraph_accumulated_${uuid}, + ${groupedColumns}, + TRUE + ) + `; + disposable.use( + await createPerfettoTable({ + engine, + name: `_flamegraph_hash_${uuid}`, + as: hashWalkSql, }), ); disposable.use(