==========
Dominators
==========

This article provides an introduction to the concepts of *Reachability*, *Shallow* versus *Retained* size, and *Dominators*, as they apply in garbage-collected languages like JavaScript.

These concepts matter in memory analysis, because often an object may itself be small, but may hold references to other much larger objects, and by doing this will prevent the garbage collector from freeing that extra memory.

You can see the dominators in a page using the :doc:`Dominators view <../dominators_view/index>` in the Memory tool.


With a garbage-collected language, like JavaScript, the programmer doesn't generally have to worry about deallocating memory. They can just create and use objects, and when the objects are no longer needed, the runtime takes care of cleaning up, and frees the memory the objects occupied.


.. _memory-dominators-reachability:

Reachability
************

In modern JavaScript implementations, the runtime decides whether an object is no longer needed based on *reachability*. In this system the heap is represented as one or more graphs. Each node in the graph represents an object, and each connection between nodes (edge) represents a reference from one object to another. The graph starts at a root node, indicated in these diagrams with "R".

.. image:: memory-graph.svg
  :class: center


During garbage collection, the runtime traverses the graph, starting at the root, and marks every object it finds. Any objects it doesn't find are unreachable, and can be deallocated.

So when an object becomes unreachable (for example, because it is only referenced by a single local variable which goes out of scope) then any objects it references also become unreachable, as long as no other objects reference them:

.. image:: memory-graph-unreachable.svg
  :class: center


Conversely, this means that objects are kept alive as long as some other reachable object is holding a reference to them.


.. _shallow-and-retained-size:

Shallow and retained size
*************************

This gives rise to a distinction between two ways to look at the size of an object:


- *shallow size*: the size of the object itself
- *retained size*: the size of the object itself, plus the size of other objects that are kept alive by this object


Often, objects will have a small shallow size but a much larger retained size, through the references they contain to other objects. Retained size is an important concept in analyzing memory usage, because it answers the question "if this object ceases to exist, what's the total amount of memory freed?".


Dominators
**********

A related concept is that of the *dominator*. Node B is said to dominate node A if every path from the root to A passes through B:

.. image:: memory-graph-dominators.svg
  :class: center


If any of node A's dominators are freed, then node A itself becomes eligible for garbage collection.


.. _memory-dominators-immediate-dominator:

If node B dominates node A, but does not dominate any of A's other dominators, then B is the *immediate dominator* of A:

.. image:: memory-graph-immediate-dominator.svg
  :class: center


.. _memory-dominators-multiple-paths:

One slight subtlety here is that if an object A is referenced by two other unrelated objects B and C, then neither object is its dominator, because you could remove either B or C from the graph, and A would still be retained by its other referrer. Instead, the immediate dominator of A would be its first common ancestor:

.. image:: memory-graph-dominator-multiple-references.svg
  :class: center


See also
********


- `Dominators in graph theory <https://en.wikipedia.org/wiki/Dominator_%28graph_theory%29>`_.
- `Tracing garbage collection <https://en.wikipedia.org/wiki/Tracing_garbage_collection>`_.
