index.rst (3804B)
1 ========== 2 Dominators 3 ========== 4 5 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. 6 7 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. 8 9 You can see the dominators in a page using the :doc:`Dominators view <../dominators_view/index>` in the Memory tool. 10 11 12 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. 13 14 15 .. _memory-dominators-reachability: 16 17 Reachability 18 ************ 19 20 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". 21 22 .. image:: memory-graph.svg 23 :class: center 24 25 26 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. 27 28 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: 29 30 .. image:: memory-graph-unreachable.svg 31 :class: center 32 33 34 Conversely, this means that objects are kept alive as long as some other reachable object is holding a reference to them. 35 36 37 .. _shallow-and-retained-size: 38 39 Shallow and retained size 40 ************************* 41 42 This gives rise to a distinction between two ways to look at the size of an object: 43 44 45 - *shallow size*: the size of the object itself 46 - *retained size*: the size of the object itself, plus the size of other objects that are kept alive by this object 47 48 49 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?". 50 51 52 Dominators 53 ********** 54 55 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: 56 57 .. image:: memory-graph-dominators.svg 58 :class: center 59 60 61 If any of node A's dominators are freed, then node A itself becomes eligible for garbage collection. 62 63 64 .. _memory-dominators-immediate-dominator: 65 66 If node B dominates node A, but does not dominate any of A's other dominators, then B is the *immediate dominator* of A: 67 68 .. image:: memory-graph-immediate-dominator.svg 69 :class: center 70 71 72 .. _memory-dominators-multiple-paths: 73 74 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: 75 76 .. image:: memory-graph-dominator-multiple-references.svg 77 :class: center 78 79 80 See also 81 ******** 82 83 84 - `Dominators in graph theory <https://en.wikipedia.org/wiki/Dominator_%28graph_theory%29>`_. 85 - `Tracing garbage collection <https://en.wikipedia.org/wiki/Tracing_garbage_collection>`_.