Skip to content

v2.0.4

@JacksonGL JacksonGL tagged this 10 Jul 16:26
Summary:
The dominator-tree and retained-size computation in `TraceFinder` used the iterative Cooper-Harvey-Kennedy fix-point. On some real browser heap snapshots it could spin forever at the "calculating dominators and retained sizes" step (one CPU pinned at 100% with a flat heap, never completing): the post-order assigned to orphan / weakly-reachable nodes (nodes unreachable from the GC root) can violate the invariant the fix-point's two-finger `intersect()` walk relies on, so a finger either steps onto the out-of-bounds "empty" sentinel (`dominators[emptySlot]` reads past the end of the array) or walks a cycle in the provisional dominator pointers, and the loop never terminates. Even when it did terminate it needed O(graph-depth) sweeps. A contributing bug: the forward post-order pass (`buildPostOrderIndex`) and the backward retainer pass (`calculateDominatorNodesFromPostOrder`) used different edge-essentiality predicates — the backward pass applied an extra `shouldTraverseEdge()` leak-trace filter the forward pass did not — so their reachability disagreed and corrupted the dominator relation.

This replaces the fix-point with the Lengauer-Tarjan algorithm (Lengauer & Tarjan, 1979), the same near-linear, single-pass algorithm Chrome DevTools now uses. It gives every node a valid DFS number (handling orphans and mutually-retaining "clique" nodes by attaching them to the root), computes immediate dominators in one pass with no fix-point to oscillate, and uses a single shared essential-edge predicate for both the forward DFS and the backward retainer scan so the two passes always agree.

Result: a 371 MB / 3,419,351-node / 19,954,862-edge browser snapshot that previously hung indefinitely now loads in ~14s with correct retained sizes.

Reviewed By: boujeepossum

Differential Revision: D111340869

fbshipit-source-id: bb136334faff61a5a43e36c5c56377c7f5fa331f
Assets 2
Loading