Why does a heap snapshot's dominator tree tell you which single edge, if cut, would free a whole subgraph?
answer
- turn a tangle into a tree
- all paths, not some path
- one chokepoint per subgraph
- immediate dominator is the parent
- a second referrer destroys domination
basics
~20 sAn object x dominates y when every path from a root to y passes through x. Cutting the reference that makes x reachable therefore makes the whole subtree x dominates unreachable at once, which is what its retained size counts.
solid answer
~50 sThe analyzer derives a **dominator tree** from the object graph. Object `x` dominates object `y` when *every* path from a root to `y` goes through `x` — so if `x` becomes unreachable, `y` must too. Retained size is just the sum of shallow sizes over `x`'s dominator subtree. That turns a tangled graph into a strict tree with a single chokepoint per subgraph: to free 1.4 GB you do not have to understand the whole subgraph, only to stop the *dominator* from being reachable, which usually means removing one reference in one place. The reasoning fails exactly where domination fails: if two independent holders can each reach the subgraph, neither dominates it, and the bytes are charged to their nearest common dominator instead. Then there is no single edge, and cutting either one frees nothing.
code
pseudocode · 13 lines// y is in x's dominator subtree when EVERY path
// from a root to y passes through x.
retained_size(x):
total = 0
for each y in dominator_subtree(x): // x included
total = total + shallow_size(y)
return total
// Sibling subtrees are disjoint, so:
retained_size(x) == shallow_size(x)
+ sum over c in dominator_children(x):
retained_size(c)go deeper
Take away one idea: if every route to a group of objects goes through one object, dropping that one object drops the whole group. That single object is what an analyzer's retained-size column is pointing at.
Be able to define domination as an all-paths property, connect it to retained size as a subtree sum, and explain why an immediate dominator gives every object exactly one parent in the tree.
Demonstrate the workflow on a real snapshot: top retained entries, the root path, the last edge, the code that installs it. Then name the failure case — two independent referrers — and how you recognise it before changing code.
The judgment is about where an hour of diagnosis buys the most: a measure that names one chokepoint beats a measure that names the fattest object. Also decide the house convention for clearable references, since it changes the numbers people argue over.
## From a graph to a tree An object graph has no natural notion of ownership: a container points at entries, entries point back at their container, and half the graph is reachable by several routes. **Domination** imposes a usable structure on it. Fix the set of roots — the fixed starting points from which the runtime considers everything reachable. Then: > Object `x` **dominates** object `y` when every path from any root to `y` passes through `x`. Domination is reflexive and transitive, and every object except the roots has a unique **immediate dominator**: the last object common to all root-to-object paths. Linking each object to its immediate dominator produces the **dominator tree**, a strict tree over the same objects. Two consequences follow immediately, and both are what make a snapshot tractable: - **Retained size is a subtree sum.** The retained size of `x` is the sum of shallow sizes over `x`'s dominator subtree, `x` included. - **One cut suffices.** Because every route to the subtree passes through `x`, making `x` unreachable makes the entire subtree unreachable in the same collection cycle. ## What that buys the investigation Without the dominator tree you would have to reason about a subgraph of millions of objects and argue that nothing else points into it. With it, the analyzer has already done that argument for you. The workflow on a search-indexing service's snapshot: 1. Sort by retained size and pick the first entry that is a surprising fraction of the heap for what it claims to be. 2. Ask for the path from a root to that object. That path is short — often three or four edges — because it is the only path. 3. Read the **last** edge on it: which field of which object holds this reference. That is the edge to cut. 4. Find the code that installs that reference and the code that was supposed to remove it. Step 3 is the whole payoff. The subgraph may be gigabytes of buffers, entries and keys; the fix is usually one line where something is added and never removed. ## Where domination breaks Domination is an all-paths property, so it is destroyed by a single extra route. | Graph shape | Who retains the subgraph | Is there one edge to cut | |---|---|---| | One holder, one path | that holder | yes — the edge into it | | Two independent holders | neither; their nearest common dominator | no — both edges must go | | Holder plus a diagnostic registry | the common dominator, often near the top | no | | Self-referential cycle below one holder | the holder above the cycle | yes | The second row is the trap that wastes an afternoon. Two suspects each show a modest retained size, the subgraph they both reach shows up under something near the top of the tree, and removing either holder frees nothing at all. The tell is a retained size that is far smaller than the object obviously ought to hold; when you see that, look for the second referrer before you touch any code. A related subtlety: an edge whose reference strength lets the collector clear it is not a guaranteed retaining edge, and analyzers differ on whether to include such edges when computing domination. A subgraph can therefore look retained under one setting and unretained under another. Check which convention the figure in front of you was produced with before you argue about it. ## The number is a ceiling Retained size says what *would* be freed if the object became unreachable. It does not say that one code change achieves that, it does not say the bytes are returned to the operating system afterwards, and it does not say the subgraph is a defect — a legitimately large index is legitimately large. What it does say, reliably, is where in the graph a single decision controls the most memory, and that is the right place to spend the next hour.
- The object you suspect shows a retained size far smaller than the subgraph it obviously holds. What is going on?Something else can reach that subgraph independently, so your suspect does not dominate it and the bytes are charged to the nearest object both paths share. Find the second referrer first: removing your suspect's reference alone would free almost nothing. Registries, caches and diagnostic listings are frequent second referrers.
- Does a cycle inside the subgraph stop the dominator reasoning from working?No. Domination is defined over paths from roots, not over acyclic structure, so a cycle sitting entirely beneath one holder is dominated by that holder and counted in its retained size. A tracing collector reclaims such a cycle once the holder is unreachable; only pure reference counting struggles with it.
- Why is the topmost entry in a retained-size ranking usually useless?The object nearest the roots dominates almost everything, so its retained size is close to the whole live set. That is arithmetic, not a finding. Useful entries are further down: an object whose retained size is a large fraction of the heap yet whose role in the system does not justify it.
A corridor every visitor to a wing must walk through: lock that one door and the whole wing is sealed, however many rooms it holds. A second staircase into the wing and the door is worthless.
saying these in an interview costs you the question
- Says x dominates y whenever x holds a reference to y
- Cuts one of two independent referrers and expects the memory back
- Thinks the dominator tree is just the reference graph redrawn
- Treats the top retained-size entry as the finding
- Believes a cycle below a holder cannot be reclaimed by tracing