Heap snapshot visualizations

Heap snapshot visualizations:
- Dominator tree with retained sizes
- Merge nodes by class

- Split snapshot into chunks so the browser's websockets implementation can handle them.
- Use TypedData indexed by node ids instead of lists of objects and a higher time complexity but more memory efficient algorithm to find the dominator tree (reduces memory usage to ~2X the size of the heap being analyzed from >10X).

R=johnmccutchan@google.com, koda@google.com

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

[rmacnak, 2015-05-15 16:53:04]

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

[koda, 2015-05-19 20:12:36]

First batch of comments.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/elements.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/elements.dart:27: export
'package:observatory/src/elements/heap_snapshot.dart';
Once should suffice.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:53: final int _id;
The root now has id 1?

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:91: List<ObjectVertex> get
dominatorTreeChildren {
Is this really fast/simple enough to be a getter?

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:278: var postOrderIndexx = new
Uint32List(N + 1);
xx?

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:341: var numPreds = new Uint32List(N +
2);
Explain the +2 (space for sentinel(s)?)

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:416: print("round $round");
Remove or change to debug Log with default off.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/src/elements/heap_snapshot.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/elements/heap_snapshot.dart:361: edge.shallowSize +=
(vertex2.shallowSize == null ? 0 : vertex2.shallowSize);
Line length.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/elements/heap_snapshot.dart:433: var rootRow = new
DominatorTreeRow(tree, null, snapshot.graph.root, snapshot);
Ditto.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/src/service/object.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/service/object.dart:872: Future<List<Class>>
_loadClasses(ServiceMap classList) {
Is this one still needed?

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/service/object.dart:1463: int i, n, nodeCount;
Consider more descriptive names.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/object_graph.h
File runtime/vm/object_graph.h (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/object_grap...
runtime/vm/object_graph.h:94: intptr_t Serialize(WriteStream* stream);
Document return value.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc
File runtime/vm/service.cc (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc#...
runtime/vm/service.cc:2258: // snapshot in megabyte-sized chunks instead.
Add named constant for chunk size.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc#...
runtime/vm/service.cc:2278: intptr_t chunk_size = (i + 1 == num_chunks)
Does this do the right thing when the last chunk is exactly 1 MB? The remainder
will be 0.

[rmacnak, 2015-05-19 22:16:08]

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/elements.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/elements.dart:27: export
'package:observatory/src/elements/heap_snapshot.dart';
On 2015/05/19 20:12:35, koda wrote:
> Once should suffice.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:53: final int _id;
On 2015/05/19 20:12:35, koda wrote:
> The root now has id 1?

Yes, documented below by the arrays this indexes into. Added that here as well.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:91: List<ObjectVertex> get
dominatorTreeChildren {
On 2015/05/19 20:12:35, koda wrote:
> Is this really fast/simple enough to be a getter?

No, this is O(2 million) for a dart2js heap.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:278: var postOrderIndexx = new
Uint32List(N + 1);
On 2015/05/19 20:12:35, koda wrote:
> xx?

Renamed to postOrderIndices.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:341: var numPreds = new Uint32List(N +
2);
On 2015/05/19 20:12:35, koda wrote:
> Explain the +2 (space for sentinel(s)?)

Added comment. +1 for 0 sentinel and +1 for deriving size by looking one
further.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:416: print("round $round");
On 2015/05/19 20:12:35, koda wrote:
> Remove or change to debug Log with default off.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/src/elements/heap_snapshot.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/elements/heap_snapshot.dart:361: edge.shallowSize +=
(vertex2.shallowSize == null ? 0 : vertex2.shallowSize);
On 2015/05/19 20:12:35, koda wrote:
> Line length.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/elements/heap_snapshot.dart:433: var rootRow = new
DominatorTreeRow(tree, null, snapshot.graph.root, snapshot);
On 2015/05/19 20:12:35, koda wrote:
> Ditto.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
File runtime/observatory/lib/src/service/object.dart (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/observatory/li...
runtime/observatory/lib/src/service/object.dart:872: Future<List<Class>>
_loadClasses(ServiceMap classList) {
On 2015/05/19 20:12:35, koda wrote:
> Is this one still needed?

Used by getClassHierarchy.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/object_graph.h
File runtime/vm/object_graph.h (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/object_grap...
runtime/vm/object_graph.h:94: intptr_t Serialize(WriteStream* stream);
On 2015/05/19 20:12:35, koda wrote:
> Document return value.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc
File runtime/vm/service.cc (right):

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc#...
runtime/vm/service.cc:2258: // snapshot in megabyte-sized chunks instead.
On 2015/05/19 20:12:36, koda wrote:
> Add named constant for chunk size.

Done.

https://codereview.chromium.org/1124153006/diff/100001/runtime/vm/service.cc#...
runtime/vm/service.cc:2278: intptr_t chunk_size = (i + 1 == num_chunks)
On 2015/05/19 20:12:35, koda wrote:
> Does this do the right thing when the last chunk is exactly 1 MB? The
remainder
> will be 0.

No, fixed.

[koda, 2015-05-21 02:05:10]

LGTM with minor comments

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:9: import 'dart:collection';
Sort imports.

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:131: _stream.readUnsigned(); // cid
Consider having a sanity check on 'cid' here to catch encoding errors or format
mismatch early.

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:198: // heavy lifting being inside a
tranformed method.
tranformed -> transformed

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:245: var addrToId = _addrToId;
Can you make the field final and get rid of this manual caching?

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:277: var addrToId = _addrToId;
Ditto.

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:382: firstPreds[N + 1] = E; // Extra
entry for cheap boundry detection.
boundry -> boundary

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:434: --curPostOrderIndex) {
Be consistent w.r.t. pre/post-increment.

https://codereview.chromium.org/1124153006/diff/120001/runtime/observatory/li...
runtime/observatory/lib/object_graph.dart:487: final N = _N;
Be consistent in whether you make locals final.

[rmacnak, 2015-05-22 21:41:55]

Fixed displaying header when navigating back to an already loaded snapshot.

Fixed displayed shallow size of a merged edge.

Fixed display of merged edges from the root.

Added labels to reference/instance counts in grouped by class view.

Fixed errors when another client is loading a snapshot.

Display a notice before locking up to do merged class view, only seems happen
soon enough on Dartium.

[Cutch, 2015-05-26 21:02:53]

LGTM with the following comments / suggestions:

- Please add a disclaimer at the top that this is a work in progress feature.
- Clear the tree when switching modes
- See if there is a natural pause point in the collect by class work so that
Chrome doesn't pop up the script kill dialogue. 

Thanks for this!

[rmacnak, 2015-05-26 21:23:31]

On 2015/05/26 21:02:53, Cutch wrote:
> LGTM with the following comments / suggestions:
> 
> - Please add a disclaimer at the top that this is a work in progress feature.

Done

> - Clear the tree when switching modes

Done

> - See if there is a natural pause point in the collect by class work so that
> Chrome doesn't pop up the script kill dialogue. 

This doesn't work very well in practice - the natural point is actually per
instance and this introduces far too much event loop overhead to complete in
reasonable time. Yielding every thousand instances or so still leads to
non-responsiveness :(

[rmacnak, 2015-05-26 21:46:34]

Committed patchset #11 (id:200001) manually as
bad1ccb2f7fcbf8fa589572b147fa19ddb8666a4 (presubmit successful).