Unpack the heap snapshot from a representation of var ints and addresses to a representation of fix…

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 98 matching lines @@
 
   int get clampedUint32 {
     if (high != 0 || mid > 0xF) {
       return 0xFFFFFFFF;
     } else {
       // Not shift as JS shifts are signed 32-bit.
       return mid * 0x10000000 + low;
     }
   }
 
+  int get highUint32 {
+    return high * (1 << 24) + (mid >> 4);
+  }
+
+  int get lowUint32 {
+    return (mid & 0xF) * (1 << 28) + low;
+  }
+
   bool get isZero {
     return (high == 0) && (mid == 0) && (low == 0);
   }
 
   void readUnsigned() {
     low = 0;
     mid = 0;
     high = 0;
 
     // Low 28 bits.
@@ skipping 88 matching lines @@
   ObjectVertex._(this._id, this._graph);
 
   bool get isRoot => _id == 1;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
 
   int get retainedSize => _graph._retainedSizes[_id];
   ObjectVertex get dominator => new ObjectVertex._(_graph._doms[_id], _graph);
 
-  int get shallowSize {
-    var stream = new ReadStream(_graph._chunks);
-    stream.position = _graph._positions[_id];
-    stream.skipUnsigned(); // addr
-    stream.readUnsigned(); // shallowSize
-    return stream.clampedUint32;
-  }
-
-  int get vmCid {
-    var stream = new ReadStream(_graph._chunks);
-    stream.position = _graph._positions[_id];
-    stream.skipUnsigned(); // addr
-    stream.skipUnsigned(); // shallowSize
-    stream.readUnsigned(); // cid
-    return stream.clampedUint32;
-  }
+  int get shallowSize => _graph._shallowSizes[_id];
+  int get vmCid => _graph._cids[_id];
 
   get successors => new _SuccessorsIterable(_graph, _id);
 
   String get address {
     // Note that everywhere else in this file, "address" really means an address
     // scaled down by kObjectAlignment. They were scaled down so they would fit
     // into Smis on the client.
-    var stream = new ReadStream(_graph._chunks);
-    stream.position = _graph._positions[_id];
-    stream.readUnsigned();
 
-    // Complicated way to do (high:mid:low * _kObjectAlignment).toHexString()
+    var high32 = _graph._addressesHigh[_id];
+    var low32 = _graph._addressesLow[_id];
+
+    // Complicated way to do (high:low * _kObjectAlignment).toHexString()
     // without intermediate values exceeding int32.
 
     var strAddr = "";
     var carry = 0;
     combine4(nibble) {
       nibble = nibble * _graph._kObjectAlignment + carry;
       carry = nibble >> 4;
       nibble = nibble & 0xF;
       strAddr = nibble.toRadixString(16) + strAddr;
     }
-    combine28(twentyEightBits) {
-      for (int shift = 0; shift < 28; shift += 4) {
-        combine4((twentyEightBits >> shift) & 0xF);
+    combine32(thirtyTwoBits) {
+      for (int shift = 0; shift < 32; shift += 4) {
+        combine4((thirtyTwoBits >> shift) & 0xF);
       }
     }
-    combine28(stream.low);
-    combine28(stream.mid);
-    combine28(stream.high);
+    combine32(low32);
+    combine32(high32);
     return strAddr;
   }
 
   List<ObjectVertex> dominatorTreeChildren() {
     var N = _graph._N;
     var doms = _graph._doms;
 
     var parentId = _id;
     var domChildren = [];
 
@@ skipping 11 matching lines @@
   final ObjectGraph _graph;
   final int _id;
 
   _SuccessorsIterable(this._graph, this._id);
 
   Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id);
 }
 
 class _SuccessorsIterator implements Iterator<ObjectVertex> {
   final ObjectGraph _graph;
-  ReadStream _stream;
+  int _nextSuccIndex;
+  int _limitSuccIndex;
 
   ObjectVertex current;
 
   _SuccessorsIterator(this._graph, int id) {
-    _stream = new ReadStream(this._graph._chunks);
-    _stream.position = _graph._positions[id];
-    _stream.skipUnsigned(); // addr
-    _stream.skipUnsigned(); // shallowSize
-    _stream.skipUnsigned(); // cid
+    _nextSuccIndex = _graph._firstSuccs[id];
+    _limitSuccIndex = _graph._firstSuccs[id + 1];
   }
 
   bool moveNext() {
-    while (true) {
-      _stream.readUnsigned();
-      if (_stream.isZero) return false;
-      var nextId = _graph._addrToId.get(_stream.high, _stream.mid, _stream.low);
-      if (nextId == null) continue; // Reference to VM isolate's heap.
-      current = new ObjectVertex._(nextId, _graph);
+    if (_nextSuccIndex < _limitSuccIndex) {
+      var succId = _graph._succs[_nextSuccIndex++];
+      current = new ObjectVertex._(succId, _graph);
       return true;
     }
+    return false;
   }
 }
 
 class _VerticesIterable extends IterableBase<ObjectVertex> {
   final ObjectGraph _graph;
 
   _VerticesIterable(this._graph);
 
   Iterator<ObjectVertex> get iterator => new _VerticesIterator(_graph);
 }
@@ skipping 37 matching lines @@
     if (limit != null) {
       result = result.take(limit);
     }
     return result;
   }
 
   Future process(statusReporter) async {
     // We build futures here instead of marking the steps as async to avoid the
     // heavy lifting being inside a transformed method.
 
-    statusReporter.add("Finding node positions...");
-    await new Future(() => _buildPositions());
+    statusReporter.add("Remapping $_N objects...");
+    await new Future(() => _remapNodes());
+
+    statusReporter.add("Remapping $_E references...");
+    await new Future(() => _remapEdges());
+
+    _addrToId = null;
+    _chunks = null;
 
     statusReporter.add("Finding post order...");
     await new Future(() => _buildPostOrder());
 
     statusReporter.add("Finding predecessors...");
     await new Future(() => _buildPredecessors());
 
     statusReporter.add("Finding dominators...");
     await new Future(() => _buildDominators());
 
     _firstPreds = null;
     _preds = null;
     _postOrderIndices = null;
 
     statusReporter.add("Finding retained sizes...");
     await new Future(() => _calculateRetainedSizes());
 
     _postOrderOrdinals = null;
 
     statusReporter.add("Loaded");
     return this;
   }
 
-  final List<ByteData> _chunks;
+  List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _N;
   int _E;
   int _size;
 
+  // Indexed by node id, with id 0 representing invalid/uninitialized.
+  // From snapshot.
+  Uint16List _cids;
+  Uint32List _shallowSizes;
+  Uint32List _firstSuccs;
+  Uint32List _succs;
+  Uint32List _addressesLow; // No Uint64List in Javascript.
+  Uint32List _addressesHigh;
+
+  // Intermediates.
   AddressMapper _addrToId;
-
-  // Indexed by node id, with id 0 representing invalid/uninitialized.
-  Uint32List _positions; // Position of the node in the snapshot.
   Uint32List _postOrderOrdinals; // post-order index -> id
   Uint32List _postOrderIndices; // id -> post-order index
   Uint32List _firstPreds; // Offset into preds.
   Uint32List _preds;
+
+  // Outputs.
   Uint32List _doms;
   Uint32List _retainedSizes;
 
-  void _buildPositions() {
+  void _remapNodes() {
     var N = _N;
+    var E = 0;
     var addrToId = new AddressMapper(N);
 
-    var positions = new Uint32List(N + 1);
+    var addressesHigh = new Uint32List(N + 1);
+    var addressesLow = new Uint32List(N + 1);
+    var shallowSizes = new Uint32List(N + 1);
+    var cids = new Uint16List(N + 1);
 
     var stream = new ReadStream(_chunks);
     stream.readUnsigned();
     _kObjectAlignment = stream.clampedUint32;
 
     var id = 1;
     while (stream.pendingBytes > 0) {
-      positions[id] = stream.position;
       stream.readUnsigned(); // addr
       addrToId.put(stream.high, stream.mid, stream.low, id);
-      stream.skipUnsigned(); // shallowSize
-      stream.skipUnsigned(); // cid
+      addressesHigh[id] = stream.highUint32;
+      addressesLow[id] = stream.lowUint32;
+      stream.readUnsigned(); // shallowSize
+      shallowSizes[id] = stream.clampedUint32;
+      stream.readUnsigned(); // cid
+      cids[id] = stream.clampedUint32;
 
       stream.readUnsigned();
       while (!stream.isZero) {
+        E++;
         stream.readUnsigned();
       }
       id++;
     }
     assert(id == (N + 1));
 
     var root = addrToId.get(0, 0, 0);
     assert(root == 1);
 
+    _E = E;
     _addrToId = addrToId;
-    _positions = positions;
+    _addressesLow = addressesLow;
+    _addressesHigh = addressesHigh;
+    _shallowSizes = shallowSizes;
+    _cids = cids;
+  }
+
+  void _remapEdges() {
+    var N = _N;
+    var E = _E;
+    var addrToId = _addrToId;
+
+    var firstSuccs = new Uint32List(N + 2);
+    var succs = new Uint32List(E);
+
+    var stream = new ReadStream(_chunks);
+    stream.skipUnsigned(); // addr alignment
+
+    var id = 1, edge = 0;
+    while (stream.pendingBytes > 0) {
+      stream.skipUnsigned(); // addr
+      stream.skipUnsigned(); // shallowSize
+      stream.skipUnsigned(); // cid
+
+      firstSuccs[id] = edge;
+
+      stream.readUnsigned();
+      while (!stream.isZero) {
+        var childId = addrToId.get(stream.high, stream.mid, stream.low);
+        if (childId != null) {
+          succs[edge] = childId;
+          edge++;
+        } else { 
+          // Reference into VM isolate's heap.
+        }
+        stream.readUnsigned();
+      }
+      id++;
+    }
+    firstSuccs[id] = edge; // Extra entry for cheap boundary detection.
+
+    assert(id == N + 1);
+    assert(edge <= E); // edge is smaller because E was computed before we knew
+                       // if references pointed into the VM isolate
+
+    _E = edge;
+    _firstSuccs = firstSuccs;
+    _succs = succs;
   }
 
   void _buildPostOrder() {
     var N = _N;
-    var E = 0;
-    var addrToId = _addrToId;
-    var positions = _positions;
+    var E = _E;
+    var firstSuccs = _firstSuccs;
+    var succs = _succs;
 
     var postOrderOrdinals = new Uint32List(N);
     var postOrderIndices = new Uint32List(N + 1);
     var stackNodes = new Uint32List(N);
     var stackCurrentEdgePos = new Uint32List(N);
 
     var visited = new Uint8List(N + 1);
     var postOrderIndex = 0;
     var stackTop = 0;
     var root = 1;
 
     stackNodes[0] = root;
-
-    var stream = new ReadStream(_chunks);
-    stream.position = positions[root];
-    stream.skipUnsigned(); // addr
-    stream.skipUnsigned(); // shallowSize
-    stream.skipUnsigned(); // cid
-    stackCurrentEdgePos[0] = stream.position;
+    stackCurrentEdgePos[0] = firstSuccs[root];
     visited[root] = 1;
 
     while (stackTop >= 0) {
       var n = stackNodes[stackTop];
       var edgePos = stackCurrentEdgePos[stackTop];
 
-      stream.position = edgePos;
-      stream.readUnsigned();  // childAddr
-      if (!stream.isZero) {
-        stackCurrentEdgePos[stackTop] = stream.position;
-        var childId = addrToId.get(stream.high, stream.mid, stream.low);
-        if (childId == null) continue; // Reference to VM isolate's heap.
-        E++;
+      if (edgePos < firstSuccs[n + 1]) {
+        var childId = succs[edgePos];
+        edgePos++;
+        stackCurrentEdgePos[stackTop] = edgePos;
         if (visited[childId] == 1) continue;
 
+        // Push child.
         stackTop++;
         stackNodes[stackTop] = childId;
-
-        stream.position = positions[childId];
-        stream.skipUnsigned(); // addr
-        stream.skipUnsigned(); // shallowSize
-        stream.skipUnsigned(); // cid
-        stackCurrentEdgePos[stackTop] = stream.position; // i.e., first edge
+        edgePos = firstSuccs[childId];
+        stackCurrentEdgePos[stackTop] = edgePos;
         visited[childId] = 1;
       } else {
         // Done with all children.
         postOrderIndices[n] = postOrderIndex;
         postOrderOrdinals[postOrderIndex++] = n;
         stackTop--;
       }
     }
 
     assert(postOrderIndex == N);
     assert(postOrderOrdinals[N - 1] == root);
 
     _postOrderOrdinals = postOrderOrdinals;
     _postOrderIndices = postOrderIndices;
     _E = E;
   }
 
   void _buildPredecessors() {
     var N = _N;
     var E = _E;
-    var addrToId = _addrToId;
-    var positions = _positions;
+    var firstSuccs = _firstSuccs;
+    var succs = _succs;
 
     // This is first filled with the predecessor counts, then reused to hold the
     // offset to the first predecessor (see alias below).
     // + 1 because 0 is a sentinel
     // + 1 so the number of predecessors can be found from the difference with
     // the next node's offset.
     var numPreds = new Uint32List(N + 2);
     var preds = new Uint32List(E);
 
     // Count predecessors of each node.
-    var stream = new ReadStream(_chunks);
-    for (var i = 1; i <= N; i++) {
-      stream.position = positions[i];
-      stream.skipUnsigned(); // addr
-      stream.skipUnsigned(); // shallowSize
-      stream.skipUnsigned(); // cid
-      stream.readUnsigned(); // succAddr
-      while (!stream.isZero) {
-        var succId = addrToId.get(stream.high, stream.mid, stream.low);
-        if (succId != null) {
-          numPreds[succId]++;
-        } else {
-          // Reference to VM isolate's heap.
-        }
-        stream.readUnsigned(); // succAddr
-      }
+    for (var succIndex = 0; succIndex < E; succIndex++) {
+      var succId = succs[succIndex];
+      numPreds[succId]++;
     }
 
     // Assign indices into predecessors array.
     var firstPreds = numPreds;  // Alias.
     var nextPreds = new Uint32List(N + 1);
     var predIndex = 0;
     for (var i = 1; i <= N; i++) {
       var thisPredIndex = predIndex;
       predIndex += numPreds[i];
       firstPreds[i] = thisPredIndex;
       nextPreds[i] = thisPredIndex;
     }
     assert(predIndex == E);
     firstPreds[N + 1] = E; // Extra entry for cheap boundary detection.
 
     // Fill predecessors array.
     for (var i = 1; i <= N; i++) {
-      stream.position = positions[i];
-      stream.skipUnsigned(); // addr
-      stream.skipUnsigned(); // shallowSize
-      stream.skipUnsigned(); // cid
-      stream.readUnsigned(); // succAddr
-      while (!stream.isZero) {
-        var succId = addrToId.get(stream.high, stream.mid, stream.low);
-        if (succId != null) {
-          var predIndex = nextPreds[succId]++;
-          preds[predIndex] = i;
-        } else {
-          // Reference to VM isolate's heap.
-        }
-        stream.readUnsigned(); // succAddr
+      var startSuccIndex = firstSuccs[i];
+      var limitSuccIndex = firstSuccs[i + 1];
+      for (var succIndex = startSuccIndex;
+           succIndex < limitSuccIndex;
+           succIndex++) {
+        var succId = succs[succIndex];
+        var predIndex = nextPreds[succId]++;
+        preds[predIndex] = i;
       }
     }
 
     _firstPreds = firstPreds;
     _preds = preds;
   }
 
   // "A Simple, Fast Dominance Algorithm"
   // Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
   void _buildDominators() {
@@ skipping 73 matching lines @@
 
     domById[root] = 0;
 
     _doms = domById;
   }
 
   void _calculateRetainedSizes() {
     var N = _N;
 
     var size = 0;
-    var positions = _positions;
+    var shallowSizes = _shallowSizes;
     var postOrderOrdinals = _postOrderOrdinals;
     var doms = _doms;
-    var retainedSizes = new Uint32List(N + 1);
+
+    // Sum shallow sizes.
+    for (var i = 1; i < N; i++) {
+      size += shallowSizes[i];
+    }
 
     // Start with retained size as shallow size.
-    var reader = new ReadStream(_chunks);
-    for (var i = 1; i <= N; i++) {
-      reader.position = positions[i];
-      reader.skipUnsigned(); // addr
-      reader.readUnsigned(); // shallowSize
-      var shallowSize = reader.clampedUint32;
-      retainedSizes[i] = shallowSize;
-      size += shallowSize;
-    }
+    var retainedSizes = new Uint32List.fromList(shallowSizes);
 
     // In post order (bottom up), add retained size to dominator's retained
     // size, skipping root.
     for (var o = 0; o < (N - 1); o++) {
       var i = postOrderOrdinals[o];
       assert(i != 1);
       retainedSizes[doms[i]] += retainedSizes[i];
     }
 
     _retainedSizes = retainedSizes;
     _size = size;
   }
 }