Just another weblog

Memory leaks are easy to find

Posted by damuchinni on February 18, 2009

So what exactly is the dominator tree?


An object A dominates on an object B if all the paths to object B pass through object A.

Remember that the Garbage Collector removes all objects that are not referenced anymore. If A dominates B and A could be removed from memory, that means that there’s no path anymore that leads to B. B is therefore unreachable and would be reclaimed by the Garbage Collector.
One could also say that A is the single object that is responsible for B still being there!

The Dominator Tree

Using the the “dominates” relationship we can create a dominator tree out of the the graph of objects in memory. At each node of this tree we store the amount of memory that would be freed (= retained size).
At the top of the tree we have a “virtual” root object, which we also use to represent objects that don’t have “real” single dominator.
Here’s an example of an object tree (on the left) and the corresponding dominator tree (on the right) :


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: