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

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

R=johnmccutchan@google.com

Committed: https://github.com/dart-lang/sdk/commit/aa47407ab850f954b3865b3060f90e5529886b73

[rmacnak, 2016-11-07 23:54:52]

rmacnak@google.com changed reviewers:
+ johnmccutchan@google.com

[Cutch, 2016-11-14 17:24:14]

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:286: class MergedObjectVertex {
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.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:287: // 0 represents
invalid/uninitialized, 1 is the root.
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)

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:315: while (sibling != 0 &&
here and elsewhere != invalidNodeIndex

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:341: while (child != 0) {
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.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:897: void _linkDominatorChildren() {
// Build a set of linked lists of children dominated by common parents.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:898: var N = _N;
Let's start typing local variables ....

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:900: var head = new Uint32List(N + 1);
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.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:956: int sort(int head) {
/// Returns the first node index in the list after being sorted.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:957: if (head == 0) return 0;
... == invalidNodeIndex) {
  return invalidNodeIndex;
}

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:959: 
// 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.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:969: int head2 = next[slow];
// Split the list in half.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:973: int newHead1 = sort(head1);
Recursively sort each of the sublists

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:975: return _mergeSorted(newHead1,
newHead2, next, cids);
Merge them

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:978: for (var parent = 1; parent <= N;
parent++) {
Sort all of the merged dominator sibling lists so that siblings with a common
class id are next to each other.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:999: next[next[fast]] != end) {
this should be factored out and reused with the code above. maybe return a list
[mid, end]

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:1014: head[parent2] = 0;
// We have merged the siblings of parent2 into parent1. Clear out the linked
list for parent 2.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:1036: mergeChildrenAndSort(child,
after);
// 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.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
File runtime/observatory/lib/src/elements/heap_snapshot.dart (right):

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/src/elements/heap_snapshot.dart:283: 'retained sizes of
its children in the dominator tree '
This text should explain what "merge" means in more detail.

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

Plus various comments.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:286: class MergedObjectVertex {
On 2016/11/14 17:24:13, Cutch wrote:
> 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.

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

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:341: while (child != 0) {
On 2016/11/14 17:24:13, Cutch wrote:
> 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.

Done.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:898: var N = _N;
On 2016/11/14 17:24:13, Cutch wrote:
> Let's start typing local variables ....

Not while we can still write Dart.

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
File runtime/observatory/lib/src/elements/heap_snapshot.dart (right):

https://codereview.chromium.org/2480293003/diff/60001/runtime/observatory/lib...
runtime/observatory/lib/src/elements/heap_snapshot.dart:283: 'retained sizes of
its children in the dominator tree '
On 2016/11/14 17:24:13, Cutch wrote:
> This text should explain what "merge" means in more detail.

Done.

[Cutch, 2016-11-15 14:50:42]

LGTM wC

https://codereview.chromium.org/2480293003/diff/80001/runtime/observatory/lib...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/2480293003/diff/80001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:414: const ROOT = 1;
move these to the top and add doc comments

[rmacnak, 2016-11-15 17:40:28]

https://codereview.chromium.org/2480293003/diff/80001/runtime/observatory/lib...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/2480293003/diff/80001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:414: const ROOT = 1;
On 2016/11/15 14:50:42, Cutch wrote:
> move these to the top and add doc comments

Done.

[rmacnak, 2016-11-15 17:43:54]

Description was changed from

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

to

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

R=johnmccutchan@google.com

Committed:
https://github.com/dart-lang/sdk/commit/aa47407ab850f954b3865b3060f90e5529886b73
==========

[rmacnak, 2016-11-15 17:43:55]

Committed patchset #6 (id:100001) manually as
aa47407ab850f954b3865b3060f90e5529886b73 (presubmit successful).