Changeset 112523 in webkit


Ignore:
Timestamp:
Mar 29, 2012 5:38:43 AM (12 years ago)
Author:
yurys@chromium.org
Message:

Web Inspector: switch heap profiler front-end to separate storage of nodes and edges
​https://bugs.webkit.org/show_bug.cgi?id=82453

PerformanceTests:

Updated heap profiler performance test after heap profiler front-end
changes.

Reviewed by Pavel Feldman.

  • inspector/detailed-heapshots-smoke-test.html:

Source/WebCore:

When heap snapshot is completely loaded move nodes and containment edges
into two separate arrays. This way we don't need _nodeIndex and _nodePosition
maps to go from node offset inside the raw snapshot to its index and back, instead
we may just divide node offset by the number of node fields to get node index. After
the nodes and containment edges are separated original array (_nodes) is dropped.
All front-end code was switched to the new representation.

Reviewed by Pavel Feldman.

  • inspector/front-end/HeapSnapshot.js:

(WebInspector.HeapSnapshotRetainerEdge):
(WebInspector.HeapSnapshotRetainerEdge.prototype.clone):
(WebInspector.HeapSnapshotRetainerEdge.prototype.set edgeIndex):
(WebInspector.HeapSnapshotRetainerEdge.prototype.get _edge):
(WebInspector.HeapSnapshotRetainerEdgeIterator.prototype.hasNext):
(WebInspector.HeapSnapshotNode.prototype.get edgesCount):
(WebInspector.HeapSnapshotNode.prototype.get rawEdges):
(WebInspector.HeapSnapshotNode.prototype.get retainers):
(WebInspector.HeapSnapshotNode.prototype.get _nodes):
(WebInspector.HeapSnapshotNode.prototype._firstEdgeIndex):
(WebInspector.HeapSnapshotNode.prototype._afterLastEdgeIndex):
(WebInspector.HeapSnapshotNode.prototype.get _nextNodeIndex):
(WebInspector.HeapSnapshot.prototype._init):
(WebInspector.HeapSnapshot.prototype._splitNodesAndContainmentEdges):
(WebInspector.HeapSnapshot.prototype._createOnlyNodesArray):
(WebInspector.HeapSnapshot.prototype._createContainmentEdgesArray):
(WebInspector.HeapSnapshot.prototype._buildRetainers):
(WebInspector.HeapSnapshot.prototype.dispose):
(WebInspector.HeapSnapshot.prototype.get maxNodeId):
(WebInspector.HeapSnapshot.prototype._calculateObjectToWindowDistance):
(WebInspector.HeapSnapshot.prototype._bfs):
(WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
(WebInspector.HeapSnapshot.prototype._getDominatedIndex):
(WebInspector.HeapSnapshot.prototype._markInvisibleEdges):
(WebInspector.HeapSnapshot.prototype._markQueriableHeapObjects):

LayoutTests:

Updated heap profiler test after switching heap profiler front-end
to the new representation of nodes and edges.

Reviewed by Pavel Feldman.

  • inspector/profiler/heap-snapshot-expected.txt:
  • inspector/profiler/heap-snapshot-test.js:

(initialize_HeapSnapshotTest.InspectorTest.createHeapSnapshotMockObject):

  • inspector/profiler/heap-snapshot.html:
Location:
trunk
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r112522 r112523  
     12012-03-28  Yury Semikhatsky  <yurys@chromium.org>
     2
     3        Web Inspector: switch heap profiler front-end to separate storage of nodes and edges
     4        https://bugs.webkit.org/show_bug.cgi?id=82453
     5
     6        Updated heap profiler test after switching heap profiler front-end
     7        to the new representation of nodes and edges.
     8
     9        Reviewed by Pavel Feldman.
     10
     11        * inspector/profiler/heap-snapshot-expected.txt:
     12        * inspector/profiler/heap-snapshot-test.js:
     13        (initialize_HeapSnapshotTest.InspectorTest.createHeapSnapshotMockObject):
     14        * inspector/profiler/heap-snapshot.html:
     15
    1162012-03-29  Kristóf Kosztyó  <kkristof@inf.u-szeged.hu>
    217

  • trunk/LayoutTests/inspector/profiler/heap-snapshot-expected.txt

    r112262 r112523  
    1414Running: heapSnapshotSimpleTest
    1515
     16Running: testNodesAndEdgesSeparationInHeapSnapshot
     17
    1618Running: heapSnapshotRetainersTest
    1719

  • trunk/LayoutTests/inspector/profiler/heap-snapshot-test.js

    r110423 r112523  
    88        _nodeNameOffset: 1,
    99        _edgesCountOffset: 2,
     10        _firstEdgeIndexOffset: 2,
    1011        _firstEdgeOffset: 3,
     12        _nodeFieldCount: 3,
    1113        _edgeFieldsCount: 3,
    1214        _edgeTypeOffset: 0,
    … …  
    2123        //   (numbers in parentheses indicate node offset)
    2224        //
    23         //         A (9) --ac- C (27) -ce- E(36)
     25        //         A (3) --ac- C (9) -ce- E(15)
    2426        //       a/|         /
    2527        //  "" (0) 1      bc
    2628        //       b\v    /
    27         //         B (18) -bd- D (33)
     29        //         B (6) -bd- D (12)
    2830        //
    29         _nodes: [
    30             0, 0, 2, 1,  6,  9, 1,  7, 18,
    31             1, 1, 2, 0,  1, 18, 1,  8, 27,
    32             1, 2, 2, 1,  9, 27, 1, 10, 33,
    33             1, 3, 1, 1, 11, 36,
    34             1, 4, 0,
    35             1, 5, 0],
     31        _onlyNodes: [
     32            0, 0, 0,
     33            1, 1, 6,
     34            1, 2, 12,
     35            1, 3, 18,
     36            1, 4, 21,
     37            1, 5, 21],
     38        _containmentEdges: [
     39            1,  6, 3, 1,  7, 6,
     40            0,  1, 6, 1,  8, 9,
     41            1,  9, 9, 1, 10, 12,
     42            1, 11, 15],
    3643        _strings: ["", "A", "B", "C", "D", "E", "a", "b", "ac", "bc", "bd", "ce"]
    3744    };

  • trunk/LayoutTests/inspector/profiler/heap-snapshot.html

    r112268 r112523  
    1515            InspectorTest.assertEquals("hidden", nodeRoot.type, "root type");
    1616            InspectorTest.assertEquals(2, nodeRoot.edgesCount, "root edges");
    17             var nodeE = new WebInspector.HeapSnapshotNode(snapshot, 36);
     17            var nodeE = new WebInspector.HeapSnapshotNode(snapshot, 15);
    1818            InspectorTest.assertEquals("E", nodeE.name, "E name");
    1919            InspectorTest.assertEquals("object", nodeE.type, "E type");
    … …  
    5656                names.push(iterator.item.name);
    5757            InspectorTest.assertEquals("a,b", names.join(","), "edge iterator");
    58             var nodeE = new WebInspector.HeapSnapshotNode(snapshot, 36);
     58            var nodeE = new WebInspector.HeapSnapshotNode(snapshot, 15);
    5959            InspectorTest.assertEquals(false, nodeE.edges.hasNext(), "empty edge iterator");
    6060            next();
    … …  
    9595            next();
    9696        },
     97
     98        function testNodesAndEdgesSeparationInHeapSnapshot(next)
     99        {
     100            var snapshot = new WebInspector.HeapSnapshot(InspectorTest.createHeapSnapshotMock());
     101            function validateNewIndex()
     102            {
     103                var copiedNodeIndex = 0;
     104                for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), copiedNodeIndex += this._nodeFieldCount) {
     105                    var originalNode = nodesIter.node;
     106                    var copiedNode = this._onlyNodes[copiedNodeIndex];
     107
     108                    if (originalNode.id !== this._onlyNodes[copiedNodeIndex + this._nodeIdOffset])
     109                        throw new Error("Id mismatch: " + originalNode.id);
     110
     111                    if (originalNode._type() !== this._onlyNodes[copiedNodeIndex + this._nodeTypeOffset])
     112                        throw new Error("Node type mismatch: " + originalNode.id);
     113
     114                    // Validate containment edges.
     115                    var firstEdgeIndex = this._onlyNodes[copiedNodeIndex + this._edgesCountOffset];
     116                    var nextNodeIndex = copiedNodeIndex + this._nodeFieldCount;
     117                    var lastEdgeIndex = (nextNodeIndex < this._onlyNodes.length)
     118                                      ? this._onlyNodes[nextNodeIndex + this._edgesCountOffset]
     119                                      : this._containmentEdges.length;
     120
     121                    if (originalNode.edgesCount !== (lastEdgeIndex - firstEdgeIndex) / this._edgeFieldsCount)
     122                        throw new Error("Edges count mismatch: " + originalNode.id);
     123
     124                    for (var edgeIter = originalNode.edges, copiedEdgeIndex = firstEdgeIndex; edgeIter.hasNext(); edgeIter.next(), copiedEdgeIndex += this._edgeFieldsCount) {
     125                        if (edgeIter.edge._type() !== this._containmentEdges[copiedEdgeIndex + this._edgeTypeOffset])
     126                            throw new Error("Edge type mismatch: " + edgeIter.edge.type);
     127
     128                        var toNodeIndex = this._containmentEdges[copiedEdgeIndex + this._edgeToNodeOffset];
     129                        if (edgeIter.edge.node.id !== this._onlyNodes[toNodeIndex + this._nodeIdOffset])
     130                            throw new Error("Edge to node id mismatch: " + edgeIter.edge.node.id);
     131                    }
     132                }
     133            }
     134            try {
     135                validateNewIndex.call(snapshot);
     136            } catch (e) {
     137                InspectorTest.addResult(e);
     138                throw e;
     139            }
     140            next();
     141        },
     142
    97143
    98144        function heapSnapshotRetainersTest(next)
    … …  
    134180            }
    135181            var expectedIndexes = {
    136                "A": [14],
    137                "B": [27],
    138                "C": [40],
    139                "D": [50],
    140                "E": [57]
     182                          // Index of corresponding node in the raw snapshot:
     183               "A": [7],  // 14
     184               "B": [14], // 27
     185               "C": [21], // 40
     186               "D": [28], // 50
     187               "E": [35]  // 57
    141188            };
    142189            var indexes = snapshot.aggregates(true);

  • trunk/PerformanceTests/ChangeLog

    r112253 r112523  
     12012-03-28  Yury Semikhatsky  <yurys@chromium.org>
     2
     3        Web Inspector: switch heap profiler front-end to separate storage of nodes and edges
     4        https://bugs.webkit.org/show_bug.cgi?id=82453
     5
     6        Updated heap profiler performance test after heap profiler front-end
     7        changes.
     8
     9        Reviewed by Pavel Feldman.
     10
     11        * inspector/detailed-heapshots-smoke-test.html:
     12
    1132012-03-27  Alexis Menard  <alexis.menard@openbossa.org>
    214

  • trunk/PerformanceTests/inspector/detailed-heapshots-smoke-test.html

    r110423 r112523  
    2626            InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildAggregates");
    2727            InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_calculateObjectToWindowDistance");
    28             InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildNodeIndex");
    2928            InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markDetachedDOMTreeNodes");
    3029            InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markQueriableHeapObjects");
     30            InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_splitNodesAndContainmentEdges");
    3131
    3232            timer.finish(backendTimerCookie);

  • trunk/Source/WebCore/ChangeLog

    r112521 r112523  
     12012-03-28  Yury Semikhatsky  <yurys@chromium.org>
     2
     3        Web Inspector: switch heap profiler front-end to separate storage of nodes and edges
     4        https://bugs.webkit.org/show_bug.cgi?id=82453
     5
     6        When heap snapshot is completely loaded move nodes and containment edges
     7        into two separate arrays. This way we don't need _nodeIndex and _nodePosition
     8        maps to go from node offset inside the raw snapshot to its index and back, instead
     9        we may just divide node offset by the number of node fields to get node index. After
     10        the nodes and containment edges are separated original array (_nodes) is dropped.
     11        All front-end code was switched to the new representation.
     12
     13        Reviewed by Pavel Feldman.
     14
     15        * inspector/front-end/HeapSnapshot.js:
     16        (WebInspector.HeapSnapshotRetainerEdge):
     17        (WebInspector.HeapSnapshotRetainerEdge.prototype.clone):
     18        (WebInspector.HeapSnapshotRetainerEdge.prototype.set edgeIndex):
     19        (WebInspector.HeapSnapshotRetainerEdge.prototype.get _edge):
     20        (WebInspector.HeapSnapshotRetainerEdgeIterator.prototype.hasNext):
     21        (WebInspector.HeapSnapshotNode.prototype.get edgesCount):
     22        (WebInspector.HeapSnapshotNode.prototype.get rawEdges):
     23        (WebInspector.HeapSnapshotNode.prototype.get retainers):
     24        (WebInspector.HeapSnapshotNode.prototype.get _nodes):
     25        (WebInspector.HeapSnapshotNode.prototype._firstEdgeIndex):
     26        (WebInspector.HeapSnapshotNode.prototype._afterLastEdgeIndex):
     27        (WebInspector.HeapSnapshotNode.prototype.get _nextNodeIndex):
     28        (WebInspector.HeapSnapshot.prototype._init):
     29        (WebInspector.HeapSnapshot.prototype._splitNodesAndContainmentEdges):
     30        (WebInspector.HeapSnapshot.prototype._createOnlyNodesArray):
     31        (WebInspector.HeapSnapshot.prototype._createContainmentEdgesArray):
     32        (WebInspector.HeapSnapshot.prototype._buildRetainers):
     33        (WebInspector.HeapSnapshot.prototype.dispose):
     34        (WebInspector.HeapSnapshot.prototype.get maxNodeId):
     35        (WebInspector.HeapSnapshot.prototype._calculateObjectToWindowDistance):
     36        (WebInspector.HeapSnapshot.prototype._bfs):
     37        (WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
     38        (WebInspector.HeapSnapshot.prototype._getDominatedIndex):
     39        (WebInspector.HeapSnapshot.prototype._markInvisibleEdges):
     40        (WebInspector.HeapSnapshot.prototype._markQueriableHeapObjects):
     41
    1422012-03-29  Leo Yang  <leo.yang@torchmobile.com.cn>
    243

  • trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js

    r112271 r112523  
    391391};
    392392
    393 WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainers, retainerIndex)
     393WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainedNodeIndex, retainerIndex)
    394394{
    395395    this._snapshot = snapshot;
    396     this._retainers = retainers;
    397     this.retainerIndex = retainerIndex || 0;
     396    this._retainedNodeIndex = retainedNodeIndex;
     397
     398    var retainedNodeOrdinal = retainedNodeIndex / snapshot._nodeFieldCount;
     399    this._firstRetainer = snapshot._firstRetainerIndex[retainedNodeOrdinal];
     400    this._retainersCount = snapshot._firstRetainerIndex[retainedNodeOrdinal + 1] - this._firstRetainer;
     401
     402    this.retainerIndex = retainerIndex;
    398403}
    399404
    … …  
    401406    clone: function()
    402407    {
    403         return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainers, this.retainerIndex);
     408        return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainedNodeIndex, this.retainerIndex);
    404409    },
    405410
    … …  
    469474    set edgeIndex(edgeIndex)
    470475    {
    471         this._globalEdgeIndex = this._retainers.item(edgeIndex);
    472         this._nodeIndex = this._snapshot._findNearestNodeIndex(this._globalEdgeIndex);
     476        var retainerIndex = this._firstRetainer + edgeIndex;
     477        this._globalEdgeIndex = this._snapshot._retainingEdges[retainerIndex];
     478        this._nodeIndex = this._snapshot._retainingNodes[retainerIndex];
    473479        delete this._edgeInstance;
    474480        delete this._nodeInstance;
    … …  
    485491    {
    486492        if (!this._edgeInstance) {
    487             var edgeIndex = this._globalEdgeIndex - this._nodeIndex - this._snapshot._firstEdgeOffset;
     493            var edgeIndex = this._globalEdgeIndex - this._node._edgeIndexesStart();
    488494            this._edgeInstance = new WebInspector.HeapSnapshotEdge(this._snapshot, this._node.rawEdges, edgeIndex);
    489495        }
    … …  
    515521    hasNext: function()
    516522    {
    517         return this.retainer.retainerIndex < this.retainer._retainers.length;
     523        return this.retainer.retainerIndex < this.retainer._retainersCount;
    518524    },
    519525
    … …  
    597603    get edgesCount()
    598604    {
    599         return this._nodes[this.nodeIndex + this._snapshot._edgesCountOffset];
     605        return (this._edgeIndexesEnd() - this._edgeIndexesStart()) / this._snapshot._edgeFieldsCount;
    600606    },
    601607
    … …  
    654660    get rawEdges()
    655661    {
    656         var firstEdgeIndex = this._firstEdgeIndex();
    657         return new WebInspector.HeapSnapshotArraySlice(this._snapshot._nodes, firstEdgeIndex, firstEdgeIndex + this.edgesCount * this._snapshot._edgeFieldsCount);
     662        return new WebInspector.HeapSnapshotArraySlice(this._snapshot._containmentEdges, this._edgeIndexesStart(), this._edgeIndexesEnd());
    658663    },
    659664
    … …  
    665670    get retainers()
    666671    {
    667         return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._snapshot._retainersForNode(this)));
     672        return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this.nodeIndex, 0));
    668673    },
    669674
    … …  
    685690    get _nodes()
    686691    {
    687         return this._snapshot._nodes;
    688     },
    689 
    690     _firstEdgeIndex: function()
    691     {
    692         return this.nodeIndex + this._snapshot._firstEdgeOffset;
     692        return this._snapshot._onlyNodes;
     693    },
     694
     695    _edgeIndexesStart: function()
     696    {
     697        return this._snapshot._onlyNodes[this.nodeIndex + this._snapshot._firstEdgeIndexOffset];
     698    },
     699
     700    _edgeIndexesEnd: function()
     701    {
     702        var nextNodeIndex = this._nextNodeIndex;
     703        if (nextNodeIndex < this._snapshot._onlyNodes.length)
     704            return this._snapshot._onlyNodes[nextNodeIndex + this._snapshot._firstEdgeIndexOffset]
     705        return this._snapshot._containmentEdges.length;
    693706    },
    694707
    695708    get _nextNodeIndex()
    696709    {
    697         return this._firstEdgeIndex() + this.edgesCount * this._snapshot._edgeFieldsCount;
     710        return this.nodeIndex + this._snapshot._nodeFieldCount;
    698711    },
    699712
    … …  
    754767    _init: function()
    755768    {
    756         this._rootNodeIndex = 1;
     769        this._rootNodeIndex = 1; // First cell contained metadata, now we should skip it.
    757770        var meta = this._metaNode;
    758771        this._nodeTypeOffset = meta.fields.indexOf("type");
    … …  
    763776        this._dominatorOffset = meta.fields.indexOf("dominator");
    764777        this._edgesCountOffset = meta.fields.indexOf("children_count");
     778        // After splitting nodes and edges we store first edge index in the field
     779        // where edges count is stored in the raw snapshot. Here we create an alias
     780        // for the field.
     781        this._firstEdgeIndexOffset = this._edgesCountOffset;
    765782        this._firstEdgeOffset = meta.fields.indexOf("children");
    766783        this._nodeFieldCount = this._firstEdgeOffset;
    … …  
    790807        };
    791808
     809        this._splitNodesAndContainmentEdges();
     810        this._rootNodeIndex = 0;
     811
    792812        this._markInvisibleEdges();
    793         this._buildNodeIndex();
    794813        this._buildRetainers();
    795         this._buildDominatedNodes();
     814        if (this._dominatorOffset !== -1) // For tests where we may not have dominator field.
     815            this._buildDominatedNodes()
    796816        this._calculateFlags();
    797817        this._calculateObjectToWindowDistance();
    798818    },
    799819
    800     _buildContinuousNodeArray: function()
     820    _splitNodesAndContainmentEdges: function()
    801821    {
    802822        // Estimate number of nodes.
    … …  
    809829            index += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
    810830        }
    811         this._createOnlyNodesArray(totalNodeCount);
    812         this._createContainmentEdgesArray(totalEdgeCount);
    813         this._createRetainmentEdgesArray(totalNodeCount, totalEdgeCount);
    814         this._restoreNodeTypes();
    815     },
    816 
    817     _createOnlyNodesArray: function(totalNodeCount)
     831        this.nodeCount = totalNodeCount;
     832        this._edgeCount = totalEdgeCount;
     833        this._createOnlyNodesArray();
     834        this._createContainmentEdgesArray();
     835        delete this._nodes;
     836    },
     837
     838    _createOnlyNodesArray: function()
    818839    {
    819840        // Copy nodes to their own array.
    820         this._onlyNodes = new Uint32Array(totalNodeCount * this._nodeFieldCount);
     841        this._onlyNodes = new Uint32Array(this.nodeCount * this._nodeFieldCount);
    821842        var dstIndex = 0;
    822843        var srcIndex = this._rootNodeIndex;
    … …  
    838859    },
    839860
    840     _createContainmentEdgesArray: function(totalEdgeCount)
     861    _createContainmentEdgesArray: function()
    841862    {
    842863        // Copy edges to their own array.
    843         this._containmentEdges = new Uint32Array(totalEdgeCount * this._edgeFieldsCount);
     864        this._containmentEdges = new Uint32Array(this._edgeCount * this._edgeFieldsCount);
    844865        var edgeArrayIndex = 0;
    845866        var srcIndex = this._rootNodeIndex;
    … …  
    847868            var srcNodeNewIndex = this._nodes[srcIndex + this._nodeTypeOffset];
    848869            // Set index of first outgoing egde in the _containmentEdges array.
    849             this._onlyNodes[srcNodeNewIndex + this._edgesCountOffset] = edgeArrayIndex;
     870            this._onlyNodes[srcNodeNewIndex + this._firstEdgeIndexOffset] = edgeArrayIndex;
    850871
    851872            // Now copy all edge information.
    … …  
    866887    },
    867888
    868     _createRetainmentEdgesArray: function(totalNodeCount, totalEdgeCount)
    869     {
    870         this._retainingNodes = new Uint32Array(totalEdgeCount);
    871         // Index of the first retainer in the _retainingNodes array. Addressed by retained node index.
    872         this._firstRetainerIndex = new Uint32Array(totalNodeCount);
    873 
    874         for (var toNodeIndex = this._edgeToNodeOffset; toNodeIndex < this._containmentEdges.length; toNodeIndex += this._edgeFieldsCount)
    875             ++this._firstRetainerIndex[this._containmentEdges[toNodeIndex]];
    876         for (var i = 0, firstUnusedRetainerSlot = 0; i < this._firstRetainerIndex.length; i++) {
     889    _buildRetainers: function()
     890    {
     891        this._retainingNodes = new Uint32Array(this._edgeCount);
     892        this._retainingEdges = new Uint32Array(this._edgeCount);
     893        // Index of the first retainer in the _retainingNodes and _retainingEdges
     894        // arrays. Addressed by retained node index.
     895        this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1);
     896
     897        for (var toNodeFieldIndex = this._edgeToNodeOffset; toNodeFieldIndex < this._containmentEdges.length; toNodeFieldIndex += this._edgeFieldsCount) {
     898            var toNodeIndex = this._containmentEdges[toNodeFieldIndex];
     899            if (toNodeIndex % this._nodeFieldCount)
     900                throw new Error("Invalid toNodeIndex " + toNodeIndex);
     901            ++this._firstRetainerIndex[toNodeIndex / this._nodeFieldCount];
     902        }
     903        for (var i = 0, firstUnusedRetainerSlot = 0; i < this.nodeCount; i++) {
    877904            var retainersCount = this._firstRetainerIndex[i];
    878905            this._firstRetainerIndex[i] = firstUnusedRetainerSlot;
    … …  
    880907            firstUnusedRetainerSlot += retainersCount;
    881908        }
     909        this._firstRetainerIndex[this.nodeCount] = this._retainingNodes.length;
    882910
    883911        var srcNodeIndex = 0;
    884         var nextNodeFirstEdgeIndex = this._edgesCountOffset;
     912        var nextNodeFirstEdgeIndex = this._onlyNodes[this._firstEdgeIndexOffset];
    885913        while (srcNodeIndex < this._onlyNodes.length) {
    886914            var firstEdgeIndex = nextNodeFirstEdgeIndex;
    887915            var nextNodeIndex = srcNodeIndex + this._nodeFieldCount;
    888916            var nextNodeFirstEdgeIndex = nextNodeIndex < this._onlyNodes.length
    889                                        ? this._onlyNodes[nextNodeIndex + this._edgesCountOffset]
     917                                       ? this._onlyNodes[nextNodeIndex + this._firstEdgeIndexOffset]
    890918                                       : this._containmentEdges.length;
    891919            for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += this._edgeFieldsCount) {
    892920                var toNodeIndex = this._containmentEdges[edgeIndex + this._edgeToNodeOffset];
    893                 var firstRetainerSlotIndex = this._firstRetainerIndex[toNodeIndex];
     921                if (toNodeIndex % this._nodeFieldCount)
     922                    throw new Error("Invalid toNodeIndex " + toNodeIndex);
     923                var firstRetainerSlotIndex = this._firstRetainerIndex[toNodeIndex / this._nodeFieldCount];
    894924                var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--this._retainingNodes[firstRetainerSlotIndex]);
    895925                this._retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex;
     926                this._retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex;
    896927            }
    897928            srcNodeIndex = nextNodeIndex;
    898         }
    899     },
    900 
    901     _restoreNodeTypes: function()
    902     {
    903         var srcIndex = this._rootNodeIndex;
    904         while (srcIndex < this._nodes.length) {
    905             var srcNodeTypeIndex = srcIndex + this._nodeTypeOffset;
    906             var newNodeIndex = this._nodes[srcNodeTypeIndex];
    907             this._nodes[srcNodeTypeIndex] = this._onlyNodes[newNodeIndex + this._nodeTypeOffset];
    908             var edgesCount = this._nodes[srcIndex + this._edgesCountOffset];
    909             srcIndex += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
    910929        }
    911930    },
    … …  
    915934        delete this._nodes;
    916935        delete this._strings;
    917         delete this._retainers;
    918         delete this._retainerIndex;
    919         delete this._nodeIndex;
     936        delete this._retainingEdges;
     937        delete this._retainingNodes;
     938        delete this._firstRetainerIndex;
    920939        if (this._aggregates) {
    921940            delete this._aggregates;
    … …  
    924943        delete this._baseNodeIds;
    925944        delete this._dominatedNodes;
    926         delete this._dominatedIndex;
     945        delete this._firstDominatedNodeIndex;
    927946        delete this._flags;
    928947        delete this._distancesToWindow;
    … …  
    932951    {
    933952        return new WebInspector.HeapSnapshotNodeIterator(this.rootNode);
    934     },
    935 
    936     get nodeCount()
    937     {
    938         return this.nodeIndexes.length - 1;
    939953    },
    940954
    … …  
    960974            return this._maxNodeId;
    961975        this._maxNodeId = 0;
    962         var node = new WebInspector.HeapSnapshotNode(this, this.nodeIndexes[0]);
    963         for (var i = 0, l = this.nodeCount; i < l; ++i) {
    964             node.nodeIndex = this.nodeIndexes[i];
    965             var id = node.id;
     976        for (var nodeIdIndex = this._nodeIdOffset; nodeIdIndex < this._onlyNodes.length; nodeIdIndex += this._nodeFieldCount) {
     977            var id = this._onlyNodes[nodeIdIndex];
    966978            if ((id % 2) && id > this._maxNodeId)
    967979                this._maxNodeId = id;
    … …  
    978990    {
    979991        return this.rootNode.retainedSize;
    980     },
    981 
    982     _retainersForNode: function(node)
    983     {
    984         var retIndexFrom = this._getRetainerIndex(node.nodeIndex);
    985         var retIndexTo = this._getRetainerIndex(node._nextNodeIndex);
    986         return new WebInspector.HeapSnapshotArraySlice(this._retainers, retIndexFrom, retIndexTo);
    987992    },
    988993
    … …  
    10301035    },
    10311036
    1032     _buildRetainers: function()
    1033     {
    1034         var nodeIndexes = this.nodeIndexes;
    1035         var nodePositions = this._nodePosition;
    1036         var nodeCount = this.nodeCount;
    1037         var nodes = this._nodes;
    1038 
    1039         // Builds up two arrays:
    1040         //  - "backRefsArray" is a continuous array, where each node owns an
    1041         //    interval (can be empty) with corresponding back references.
    1042         //  - "indexArray" is an array of indexes in the "backRefsArray"
    1043         //    with the same positions as in the _nodeIndex.
    1044         var indexArray = this._retainerIndex = new Uint32Array(nodeCount + 1);
    1045         var edgesCountOffset = this._edgesCountOffset;
    1046         var firstEdgeOffset = this._firstEdgeOffset;
    1047         var edgeFieldsCount = this._edgeFieldsCount;
    1048         var edgeToNodeOffset = this._edgeToNodeOffset;
    1049         var backRefsCount = 0;
    1050         // Count the number of retainers for each node
    1051         for (var i = 0; i < nodeCount; ++i) {
    1052             var nodeIndex = nodeIndexes[i];
    1053             var edgesOffset = nodeIndex + firstEdgeOffset + edgeToNodeOffset;
    1054             var edgesCount = nodes[nodeIndex + edgesCountOffset];
    1055             backRefsCount += edgesCount;
    1056             for (var j = 0; j < edgesCount; ++j) {
    1057               var targetNodeIndex = nodes[j * edgeFieldsCount + edgesOffset];
    1058               ++indexArray[nodePositions[targetNodeIndex]];
    1059             }
    1060         }
    1061         var backRefsArray = this._retainers = new Uint32Array(backRefsCount);
    1062         // Put in the first slot of each backRefsArray slice the count of entries
    1063         // that will be filled.
    1064         var backRefsPosition = 0;
    1065         // The one extra slot in the _retainerIndex array is set to the
    1066         // end of _retainers array. It is used in the retainers iterator.
    1067         for (i = 0; i <= nodeCount; ++i) {
    1068             backRefsCount = backRefsArray[backRefsPosition] = indexArray[i];
    1069             indexArray[i] = backRefsPosition;
    1070             backRefsPosition += backRefsCount;
    1071         }
    1072         var retainerIndex = this._retainerIndex;
    1073         // Fill up the retainers array with indexes of edges.
    1074         for (var i = 0; i < nodeCount; ++i) {
    1075             var nodeIndex = nodeIndexes[i];
    1076             var edgesOffset = nodeIndex + firstEdgeOffset;
    1077             var edgesCount = nodes[nodeIndex + edgesCountOffset];
    1078             for (var j = 0; j < edgesCount; ++j) {
    1079                 var edgeIndex = j * edgeFieldsCount + edgesOffset;
    1080                 var retNode = nodePositions[nodes[edgeIndex + edgeToNodeOffset]];
    1081                 var retIndex = indexArray[retNode];
    1082                 var backRefIndex = retIndex + (--backRefsArray[retIndex]);
    1083                 backRefsArray[backRefIndex] = edgeIndex;
    1084             }
    1085         }
    1086     },
    1087 
    10881037    _calculateObjectToWindowDistance: function()
    10891038    {
    … …  
    10951044            var node = iter.edge.node;
    10961045            if (node.isWindow) {
     1046                if (node.nodeIndex % this._nodeFieldCount)
     1047                    throw new Error("Invalid nodeIndex: " + node.nodeIndex);
    10971048                list.push(node.nodeIndex);
    10981049                this._distancesToWindow[node.nodeIndex] = 0;
    … …  
    11041055        list = [];
    11051056        list.push(this._rootNodeIndex);
    1106         this._distancesToWindow[this.rootNode.nodeIndex] = 0;
     1057        this._distancesToWindow[this._rootNodeIndex] = 0;
    11071058        this._bfs(list);
    11081059    },
    … …  
    11111062    {
    11121063        var index = 0;
    1113         var nodes = this._nodes;
     1064        var node = new WebInspector.HeapSnapshotNode(this);
    11141065        while (index < list.length) {
    11151066            var nodeIndex = list[index++]; // shift generates too much garbage.
    … …  
    11191070            }
    11201071            var distance = this._distancesToWindow[nodeIndex] + 1;
    1121             var edgesCount = nodes[nodeIndex + this._edgesCountOffset];
    1122             var edgeToNodeIndex = nodeIndex + this._firstEdgeOffset + this._edgeToNodeOffset;
     1072            node.nodeIndex = nodeIndex;
     1073            var edgesCount = node.edgesCount;
     1074            var edgeToNodeIndex = node._edgeIndexesStart() + this._edgeToNodeOffset;
    11231075            for (var i = 0; i < edgesCount; ++i) {
    1124                 var childNodeIndex = nodes[edgeToNodeIndex];
     1076                var childNodeIndex = this._containmentEdges[edgeToNodeIndex];
     1077                if (childNodeIndex % this._nodeFieldCount)
     1078                    throw new Error("Invalid childNodeIndex: " + childNodeIndex);
    11251079                edgeToNodeIndex += this._edgeFieldsCount;
    11261080                if (childNodeIndex in this._distancesToWindow)
    … …  
    11451099        var aggregates = {};
    11461100        var aggregatesByClassName = {};
    1147         var node = new WebInspector.HeapSnapshotNode(this, this.nodeIndexes[0]);
    1148         for (var i = 0, l = this.nodeCount; i < l; ++i) {
    1149             node.nodeIndex = this.nodeIndexes[i];
     1101        for (var node = new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex); node.nodeIndex < this._onlyNodes.length; node.nodeIndex = node._nextNodeIndex) {
    11501102            if (shouldSkip(node))
    11511103                continue;
    … …  
    12141166    },
    12151167
    1216     get nodeIndexes()
    1217     {
    1218         return this._nodeIndex;
    1219     },
    1220 
    1221     _buildNodeIndex: function()
    1222     {
    1223         var count = 0;
    1224         for (var i = this._rootNodeIndex, l = this._nodes.length; i < l; ++count) {
    1225             var edgesCount = this._nodes[i + this._edgesCountOffset];
    1226             i += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
    1227         }
    1228         var nodeIndex = new Uint32Array(count + 1);
    1229         var nodePosition = {};
    1230         count = 0;
    1231         for (var i = this._rootNodeIndex, l = this._nodes.length; i < l; ++count) {
    1232             nodeIndex[count] = i;
    1233             nodePosition[i] = count;
    1234             var edgesCount = this._nodes[i + this._edgesCountOffset];
    1235             i += this._firstEdgeOffset + edgesCount * this._edgeFieldsCount;
    1236         }
    1237         nodeIndex[count] = this._nodes.length;
    1238         nodePosition[this._nodes.length] = count;
    1239         this._nodeIndex = nodeIndex;
    1240         this._nodePosition = nodePosition;
    1241     },
    1242 
    1243     _findNearestNodeIndex: function(index)
    1244     {
    1245         var result = binarySearch(index, this._nodeIndex, this._numbersComparator);
    1246         if (result < 0) {
    1247             result = -result - 1;
    1248             nodeIndex = this._nodeIndex[result];
    1249             // Binary search can return either maximum lower value, or minimum higher value.
    1250             if (nodeIndex > index)
    1251                 nodeIndex = this._nodeIndex[result - 1];
    1252         } else
    1253             var nodeIndex = this._nodeIndex[result];
    1254         return nodeIndex;
    1255     },
    1256 
    1257     _getRetainerIndex: function(nodeIndex)
    1258     {
    1259         var nodePosition = this._nodePosition[nodeIndex];
    1260         return this._retainerIndex[nodePosition];
    1261     },
    1262 
    12631168    _buildDominatedNodes: function()
    12641169    {
    1265         var nodeCount = this.nodeCount;
    12661170        // Builds up two arrays:
    12671171        //  - "dominatedNodes" is a continuous array, where each node owns an
    … …  
    12691173        //  - "indexArray" is an array of indexes in the "dominatedNodes"
    12701174        //    with the same positions as in the _nodeIndex.
    1271         var indexArray = this._dominatedIndex = new Uint32Array(nodeCount + 1);
    1272         // Count the number of retainers for each node
    1273         for (var i = 0; i < nodeCount; ++i) {
    1274             var nodeIndex = this.nodeIndexes[i];
    1275             var dominatorIndex = this._nodes[nodeIndex + this._dominatorOffset];
     1175        var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1);
     1176        // All nodes except the root have dominators.
     1177        var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1);
     1178
     1179        // Count the number of dominated nodes for each node
     1180        for (var nodeIndex = 0; nodeIndex < this._onlyNodes.length; nodeIndex += this._nodeFieldCount) {
     1181            var dominatorIndex = this._onlyNodes[nodeIndex + this._dominatorOffset];
     1182            if (dominatorIndex % this._nodeFieldCount)
     1183                throw new Error("Wrong dominatorIndex " + dominatorIndex + " nodeIndex = " + nodeIndex + " nodeCount = " + this.nodeCount);
     1184            // Skip root node. We may simplify this by starting iteration from second node.
    12761185            if (nodeIndex === dominatorIndex) continue;
    1277             ++indexArray[this._nodePosition[dominatorIndex]];
    1278         }
    1279         var dominatedNodes = this._dominatedNodes = new Uint32Array(nodeCount - 1);
     1186            ++indexArray[dominatorIndex / this._nodeFieldCount];
     1187        }
    12801188        // Put in the first slot of each dominatedNodes slice the count of entries
    12811189        // that will be filled.
    1282         var dominatedPosition = 0;
    1283         for (i = 0; i <= nodeCount; ++i) {
    1284             var dominatedCount = dominatedNodes[dominatedPosition] = indexArray[i];
    1285             indexArray[i] = dominatedPosition;
    1286             dominatedPosition += dominatedCount;
     1190        var firstDominatedNodeIndex = 0;
     1191        for (i = 0; i <= this.nodeCount; ++i) {
     1192            var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i];
     1193            indexArray[i] = firstDominatedNodeIndex;
     1194            firstDominatedNodeIndex += dominatedCount;
    12871195        }
    12881196        // Fill up the dominatedNodes array with indexes of dominated nodes.
    1289         for (var i = 0; i < nodeCount; ++i) {
    1290             var nodeIndex = this.nodeIndexes[i];
    1291             var dominatorIndex = this._nodes[nodeIndex + this._dominatorOffset];
     1197        for (var nodeIndex = 0; nodeIndex < this._onlyNodes.length; nodeIndex += this._nodeFieldCount) {
     1198            var dominatorIndex = this._onlyNodes[nodeIndex + this._dominatorOffset];
     1199            if (dominatorIndex % this._nodeFieldCount)
     1200                throw new Error("Wrong dominatorIndex " + dominatorIndex);
    12921201            if (nodeIndex === dominatorIndex) continue;
    1293             var dominatorPos = this._nodePosition[dominatorIndex];
     1202            var dominatorPos = dominatorIndex / this._nodeFieldCount;
    12941203            var dominatedRefIndex = indexArray[dominatorPos];
    12951204            dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
    … …  
    13001209    _getDominatedIndex: function(nodeIndex)
    13011210    {
    1302         var nodePosition = this._nodePosition[nodeIndex];
    1303         return this._dominatedIndex[nodePosition];
     1211        if (nodeIndex % this._nodeFieldCount)
     1212            throw new Error("Invalid nodeIndex: " + nodeIndex);
     1213        return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount];
    13041214    },
    13051215
    … …  
    13261236                    && globalObjEdge._hasStringName
    13271237                    && (globalObjEdge._nameOrIndex in propNames))
    1328                     this._nodes[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
     1238                    this._containmentEdges[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
    13291239            }
    13301240        }
    … …  
    13821292            this._flags[nodeIndex] |= flag;
    13831293            var edgesOffset = nodeIndex + this._firstEdgeOffset;
    1384             var edgesCount = this._nodes[nodeIndex + this._edgesCountOffset];
     1294            var edgesCount = node.edgesCount;
    13851295            edge._edges = node.rawEdges;
    13861296            for (var j = 0; j < edgesCount; ++j) {
    13871297                edge.edgeIndex = j * this._edgeFieldsCount;
    1388                 var nodeIndex = this._nodes[edgesOffset + edge.edgeIndex + this._edgeToNodeOffset];
     1298                var nodeIndex = edge.nodeIndex;
    13891299                if (this._flags[nodeIndex] & flag)
    13901300                    continue;
Note: See TracChangeset for help on using the changeset viewer.