Observatory: Add view of dominator tree with siblings merged by class.

runtime/observatory/lib/object_graph.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library object_graph;
 
 import 'dart:async';
 import 'dart:collection';
 import 'dart:typed_data';
 
@@ skipping 264 matching lines @@
     for (var childId = 1; childId <= N; childId++) {
       if (doms[childId] == parentId) {
         domChildren.add(new ObjectVertex._(childId, _graph));
       }
     }
 
     return domChildren;
   }
 }
 
+
+class MergedObjectVertex {

[Cutch, 2016/11/14 17:24:13]

Doc comment explaining what this represents at a high level, for example:

A dominator tree of objects where sibling nodes with the same class are
collapsed / merged.

This class needs to implement ObjectVertex.

[rmacnak, 2016/11/15 00:44:15]

Added comment. This class does *not* implement ObjectVertex.

+  // 0 represents invalid/uninitialized, 1 is the root.

[Cutch, 2016/11/14 17:24:13]

Let's use a constant for 0 where you mean the invalid node sentinel.

const int invalidNodeIndex = 0;
const int rootNodeIndex = 1;

(here and elsewhere)

+  final int _id;
+  final ObjectGraph _graph;
+
+  MergedObjectVertex._(this._id, this._graph);
+
+  bool get isRoot => _id == 1;
+
+  bool operator ==(other) => _id == other._id && _graph == other._graph;
+  int get hashCode => _id;
+
+  int get vmCid => _graph._cids[_id];
+
+  int get shallowSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != 0 &&
+           cids[sibling] == cids[_id]) {
+      size += _graph._shallowSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get retainedSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != 0 &&

[Cutch, 2016/11/14 17:24:13]

here and elsewhere != invalidNodeIndex

+           cids[sibling] == cids[_id]) {
+      size += _graph._retainedSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get instanceCount {
+    var cids = _graph._cids;
+    var count = 0;
+    var sibling = _id;
+    while (sibling != 0 &&
+           cids[sibling] == cids[_id]) {
+      count++;
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return count;
+  }
+
+  List<ObjectVertex> dominatorTreeChildren() {
+    var next = _graph._mergedDomNext;
+    var cids = _graph._cids;
+
+    var domChildren = [];
+    var prev = 0;
+    var child = _graph._mergedDomHead[_id];
+    while (child != 0) {

[Cutch, 2016/11/14 17:24:13]

Scan the list of siblings, creating MergedObjectVertex nodes whenever the class
id changes. 

This code ensures that the child index is the head of sibling list for that
given class id.

[rmacnak, 2016/11/15 00:44:15]

Done.

+      if (prev == 0 ||
+          cids[prev] != cids[child]) {
+        domChildren.add(new MergedObjectVertex._(child, _graph));
+      }
+      prev = child;
+      child = next[child];
+    }
+
+    return domChildren;
+  }
+}
+
 class _SuccessorsIterable extends IterableBase<ObjectVertex> {
   final ObjectGraph _graph;
   final int _id;
 
   _SuccessorsIterable(this._graph, this._id);
 
   Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id);
 }
 
 class _SuccessorsIterator implements Iterator<ObjectVertex> {
@@ skipping 44 matching lines @@
 class ObjectGraph {
   ObjectGraph(List<ByteData> chunks, int nodeCount)
       : this._chunks = chunks,
         this._N = nodeCount;
 
   int get size => _size;
   int get vertexCount => _N;
   int get edgeCount => _E;
 
   ObjectVertex get root => new ObjectVertex._(1, this);
+  MergedObjectVertex get mergedRoot => new MergedObjectVertex._(1, this);
   Iterable<ObjectVertex> get vertices => new _VerticesIterable(this);
 
   Iterable<ObjectVertex> getMostRetained({int classId, int limit}) {
     List<ObjectVertex> _mostRetained =
         new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot));
     _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize);
 
     var result = _mostRetained;
     if (classId != null) {
       result = result.where((u) => u.vmCid == classId);
@@ skipping 15 matching lines @@
 
       controller.add(["Remapping $_E references...", 15.0]);
       await new Future(() => _remapEdges());
 
       _addrToId = null;
       _chunks = null;
 
       controller.add(["Finding depth-first order...", 30.0]);
       await new Future(() => _dfs());
 
-      controller.add(["Finding predecessors...", 45.0]);
+      controller.add(["Finding predecessors...", 40.0]);
       await new Future(() => _buildPredecessors());
 
-      controller.add(["Finding dominators...", 60.0]);
+      controller.add(["Finding dominators...", 50.0]);
       await new Future(() => _buildDominators());
 
       _firstPreds = null;
       _preds = null;
 
       _semi = null;
       _parent = null;
 
-      controller.add(["Finding retained sizes...", 75.0]);
+      controller.add(["Finding retained sizes...", 60.0]);
       await new Future(() => _calculateRetainedSizes());
 
       _vertex = null;
 
-      controller.add(["Loaded", 100.0]);
+      controller.add(["Linking dominator tree children...", 70.0]);
+      await new Future(() => _linkDominatorChildren());
+
+      controller.add(["Sorting dominator tree children...", 80.0]);
+      await new Future(() => _sortDominatorChildren());
+
+      controller.add(["Merging dominator tree siblings...", 90.0]);
+      await new Future(() => _mergeDominatorSiblings());
+
+      controller.add(["Processed", 100.0]);
       controller.close();
     }());
     return controller.stream;
   }
 
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _N;
   int _E;
@@ skipping 12 matching lines @@
   AddressMapper _addrToId;
   Uint32List _vertex;
   Uint32List _parent;
   Uint32List _semi;
   Uint32List _firstPreds; // Offset into preds.
   Uint32List _preds;
 
   // Outputs.
   Uint32List _doms;
   Uint32List _retainedSizes;
+  Uint32List _mergedDomHead;
+  Uint32List _mergedDomNext;
 
   void _remapNodes() {
     var N = _N;
     var E = 0;
     var addrToId = new AddressMapper(N);
 
     var addressesHigh = new Uint32List(N + 1);
     var addressesLow = new Uint32List(N + 1);
     var shallowSizes = new Uint32List(N + 1);
     var cids = new Uint16List(N + 1);
@@ skipping 361 matching lines @@
     // size, skipping root.
     for (var i = N; i > 1; i--) {
       var v = vertex[i];
       assert(v != 1);
       retainedSizes[doms[i]] += retainedSizes[i];
     }
 
     _retainedSizes = retainedSizes;
     _size = size;
   }
+
+  void _linkDominatorChildren() {

[Cutch, 2016/11/14 17:24:13]

// Build a set of linked lists of children dominated by common parents.

+    var N = _N;

[Cutch, 2016/11/14 17:24:13]

Let's start typing local variables ....

[rmacnak, 2016/11/15 00:44:15]

Not while we can still write Dart.

+    var doms = _doms;
+    var head = new Uint32List(N + 1);

[Cutch, 2016/11/14 17:24:13]

We need to start commenting at a high level what is being computed. For example:

// The head of a linked list containing all nodes dominated by the same parent
node. Indexed by node id.

+    var next = new Uint32List(N + 1);
+
+    for (var child = 1; child <= N; child++) {
+      var parent = doms[child];
+      next[child] = head[parent];
+      head[parent] = child;
+    }
+
+    _mergedDomHead = head;
+    _mergedDomNext = next;
+  }
+
+  static int _mergeSorted(int head1, int head2,
+                          Uint32List next, Uint16List key) {
+    var head = head1;
+    var beforeInsert = 0;
+    var afterInsert = head1;
+    var startInsert = head2;
+
+    while (startInsert != 0) {
+      while ((afterInsert != 0) &&
+             (key[afterInsert] <= key[startInsert])) {
+        beforeInsert = afterInsert;
+        afterInsert = next[beforeInsert];
+      }
+
+      var endInsert = startInsert;
+      var peek = next[endInsert];
+
+      while ((peek != 0) && (key[peek] < key[afterInsert])) {
+        endInsert = peek;
+        peek = next[endInsert];
+      }
+      assert(endInsert != 0);
+
+      if (beforeInsert == 0) {
+        head = startInsert;
+      } else {
+        next[beforeInsert] = startInsert;
+      }
+      next[endInsert] = afterInsert;
+
+      startInsert = peek;
+      beforeInsert = endInsert;
+    }
+
+    return head;
+  }
+
+  void _sortDominatorChildren() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+
+    int sort(int head) {

[Cutch, 2016/11/14 17:24:13]

/// Returns the first node index in the list after being sorted.

+      if (head == 0) return 0;

[Cutch, 2016/11/14 17:24:13]

... == invalidNodeIndex) {
  return invalidNodeIndex;
}

+      if (next[head] == 0) return head;
+

[Cutch, 2016/11/14 17:24:13]

// Determine the mid and end point of the list by walking two cursors down the
list in parallel. The first, 'slow', walks 1 node per iteration and 'fast' walks
2 nodes per iteration. When 'fast' hits the end of the list, 'slow' will be at
the middle.

+      int head1 = head;
+      int slow = head;
+      int fast = head;
+      while (next[fast] != 0 &&
+             next[next[fast]] != 0) {
+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      int head2 = next[slow];

[Cutch, 2016/11/14 17:24:13]

// Split the list in half.

+      next[slow] = 0;
+
+      assert(head1 != head2);
+      int newHead1 = sort(head1);

[Cutch, 2016/11/14 17:24:13]

Recursively sort each of the sublists

+      int newHead2 = sort(head2);
+      return _mergeSorted(newHead1, newHead2, next, cids);

[Cutch, 2016/11/14 17:24:13]

Merge them

+    }
+
+    for (var parent = 1; parent <= N; parent++) {

[Cutch, 2016/11/14 17:24:13]

Sort all of the merged dominator sibling lists so that siblings with a common
class id are next to each other.

+      head[parent] = sort(head[parent]);
+    }
+  }
+
+  void _mergeDominatorSiblings() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+    var workStack = new Uint32List(N);
+    var workStackTop = 0;
+
+    mergeChildrenAndSort(var parent1, var end) {
+      assert(parent1 != 0);
+      if (next[parent1] == end) return;
+
+      int cid = cids[parent1];
+      int slow = parent1;
+      int fast = parent1;
+      while (next[fast] != end &&
+             next[next[fast]] != end) {

[Cutch, 2016/11/14 17:24:13]

this should be factored out and reused with the code above. maybe return a list
[mid, end]

+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      int parent2 = next[slow];
+
+      assert(parent2 != 0);
+      assert(parent1 != parent2);
+      assert(cids[parent1] == cids[parent2]);
+
+      mergeChildrenAndSort(parent1, parent2);
+      mergeChildrenAndSort(parent2, end);
+
+      head[parent1] = _mergeSorted(head[parent1], head[parent2], next, cids);
+      head[parent2] = 0;

[Cutch, 2016/11/14 17:24:12]

// We have merged the siblings of parent2 into parent1. Clear out the linked
list for parent 2.

+    }
+
+    // Push root.
+    workStack[workStackTop++] = 1;
+
+    while (workStackTop > 0) {
+      var parent = workStack[--workStackTop];
+
+      var prev = 0;
+      var child = head[parent];
+      while (child != 0) {
+        // Push child.
+        workStack[workStackTop++] = child;
+
+        // Next sibling with a different cid.
+        var after = child;
+        while (after != 0 &&
+               cids[after] == cids[child]) {
+          after = next[after];
+        }
+
+        mergeChildrenAndSort(child, after);

[Cutch, 2016/11/14 17:24:13]

// child is the first node with cid A and after is the node just 'after' the
last node with cid A.
// collapse / merge all the nodes between child and after into child.

+
+        child = after;
+      }
+    }
+  }
 }