Changeset 117437 in webkit


Ignore:
Timestamp:
May 17, 2012 5:48:07 AM (12 years ago)
Author:
loislo@chromium.org
Message:

Web Inspector: HeapSnapshot: speed-up calculateObjectToWindowDistance
https://bugs.webkit.org/show_bug.cgi?id=86718

The idea is to switch from nodeIndex2distance array to nodeOrdinal2distance external array.
Due to nature of nodeIndex values the original array was sparsed.

Reviewed by Yury Semikhatsky.

  • inspector/front-end/HeapSnapshot.js:

(WebInspector.HeapSnapshotNode.prototype.get distanceToWindow):
(WebInspector.HeapSnapshot.prototype._calculateObjectToWindowDistance):
(WebInspector.HeapSnapshot.prototype._bfs):
(WebInspector.HeapSnapshot.prototype._buildAggregates):

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r117432 r117437  
     12012-05-17  Ilya Tikhonovsky  <loislo@chromium.org>
     2
     3        Web Inspector: HeapSnapshot: speed-up calculateObjectToWindowDistance
     4        https://bugs.webkit.org/show_bug.cgi?id=86718
     5
     6        The idea is to switch from nodeIndex2distance array to nodeOrdinal2distance external array.
     7        Due to nature of nodeIndex values the original array was sparsed.
     8
     9        Reviewed by Yury Semikhatsky.
     10
     11        * inspector/front-end/HeapSnapshot.js:
     12        (WebInspector.HeapSnapshotNode.prototype.get distanceToWindow):
     13        (WebInspector.HeapSnapshot.prototype._calculateObjectToWindowDistance):
     14        (WebInspector.HeapSnapshot.prototype._bfs):
     15        (WebInspector.HeapSnapshot.prototype._buildAggregates):
     16
    1172012-05-11  Kinuko Yasuda  <kinuko@chromium.org>
    218
  • trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js

    r117296 r117437  
    427427    get distanceToWindow()
    428428    {
    429         return this._snapshot._distancesToWindow[this.nodeIndex];
     429        return this._snapshot._distancesToWindow[this.nodeIndex / this._snapshot._nodeFieldCount];
    430430    },
    431431
     
    896896    _calculateObjectToWindowDistance: function()
    897897    {
    898         this._distancesToWindow = new Array(this.nodeCount);
     898        var nodeFieldCount = this._nodeFieldCount;
     899        var distances = new Uint32Array(this.nodeCount);
    899900
    900901        // bfs for Window roots
     
    903904            var node = iter.edge.node;
    904905            if (node.isWindow) {
    905                 if (node.nodeIndex % this._nodeFieldCount)
    906                     throw new Error("Invalid nodeIndex: " + node.nodeIndex);
    907906                list.push(node.nodeIndex);
    908                 this._distancesToWindow[node.nodeIndex] = 0;
    909             }
    910         }
    911         this._bfs(list);
     907                distances[node.nodeIndex / nodeFieldCount] = 0;
     908            }
     909        }
     910        this._bfs(list, distances);
    912911
    913912        // bfs for root
    914913        list = [];
    915914        list.push(this._rootNodeIndex);
    916         this._distancesToWindow[this._rootNodeIndex] = 0;
    917         this._bfs(list);
    918     },
    919 
    920     _bfs: function(list)
     915        distances[this._rootNodeIndex / nodeFieldCount] = 0;
     916        this._bfs(list, distances);
     917        this._distancesToWindow = distances;
     918    },
     919
     920    _bfs: function(list, distances)
    921921    {
    922922        // Peload fields into local variables for better performance.
     
    926926        var firstEdgeIndexOffset = this._firstEdgeIndexOffset;
    927927        var edgeToNodeOffset = this._edgeToNodeOffset;
    928         var distancesToWindow = this._distancesToWindow;
    929928        var nodes = this._nodes;
     929        var nodeCount = this.nodeCount;
    930930
    931931        var index = 0;
    932932        while (index < list.length) {
    933933            var nodeIndex = list[index++]; // shift generates too much garbage.
     934            var nodeOrdinal = nodeIndex / nodeFieldCount;
    934935            if (index > 100000) {
    935936                list = list.slice(index);
    936937                index = 0;
    937938            }
    938             var distance = distancesToWindow[nodeIndex] + 1;
    939 
     939            var distance = distances[nodeOrdinal] + 1;
    940940            var firstEdgeIndex = nodes[nodeIndex + firstEdgeIndexOffset];
    941             var edgesEnd = nodeIndex < nodes.length
    942                          ? nodes[nodeIndex + nodeFieldCount + firstEdgeIndexOffset]
     941            var edgesEnd = nodeOrdinal < nodeCount - 1
     942                         ? nodes[nodeIndex + firstEdgeIndexOffset + nodeFieldCount]
    943943                         : containmentEdges.length;
    944944            for (var edgeToNodeIndex = firstEdgeIndex + edgeToNodeOffset; edgeToNodeIndex < edgesEnd; edgeToNodeIndex += edgeFieldsCount) {
    945945                var childNodeIndex = containmentEdges[edgeToNodeIndex];
    946                 if (childNodeIndex % nodeFieldCount)
    947                     throw new Error("Invalid childNodeIndex: " + childNodeIndex);
    948                 if (childNodeIndex in distancesToWindow)
     946                var childNodeOrdinal = childNodeIndex / nodeFieldCount;
     947                if (distances[childNodeOrdinal])
    949948                    continue;
    950                 distancesToWindow[childNodeIndex] = distance;
     949                distances[childNodeOrdinal] = distance;
    951950                list.push(childNodeIndex);
    952951            }
     
    968967
    969968        for (var nodeIndex = this._rootNodeIndex; nodeIndex < nodesLength; nodeIndex += nodeFieldsCount) {
     969            var nodeOrdinal = nodeIndex / nodeFieldsCount;
    970970            node.nodeIndex = nodeIndex;
    971971            var selfSize = nodes[nodeIndex + selfSizeOffset];
     
    980980                var value = {
    981981                    count: 1,
    982                     distanceToWindow: distancesToWindow[nodeIndex],
     982                    distanceToWindow: distancesToWindow[nodeOrdinal],
    983983                    self: selfSize,
    984984                    maxRet: 0,
     
    991991            } else {
    992992                var clss = aggregates[classIndex];
    993                 clss.distanceToWindow = Math.min(clss.distanceToWindow, distancesToWindow[nodeIndex]);
     993                clss.distanceToWindow = Math.min(clss.distanceToWindow, distancesToWindow[nodeOrdinal]);
    994994                ++clss.count;
    995995                clss.self += selfSize;
Note: See TracChangeset for help on using the changeset viewer.