From e6656fe82bc95428a8160252ed153f61778bbcca Mon Sep 17 00:00:00 2001 From: "loislo@chromium.org" Date: Wed, 4 Apr 2012 15:49:59 +0000 Subject: [PATCH] Web Inspector: linearise aggregate's retaining size calculation. https://bugs.webkit.org/show_bug.cgi?id=83125 This version is twice as fast as the original and it is non-recursive. Reviewed by Yury Semikhatsky. PerformanceTests: * inspector/detailed-heapshots-smoke-test.html: Source/WebCore: * inspector/front-end/HeapSnapshot.js: (WebInspector.HeapSnapshot.prototype._getDominatedIndex): was moved closer to it's usage (WebInspector.HeapSnapshot.prototype._calculateClassesRetainedSize): it was _buildAggregates' inner function forDominatedNodes. it was: a) extracted from _buildAggregates; b) made non-recursive; c) many getters were inlined; d) subarray of dominating nodes were inlined too. (WebInspector.HeapSnapshot.prototype._buildAggregates): many getters were inlined. (WebInspector.HeapSnapshot.prototype.aggregates): git-svn-id: http://svn.webkit.org/repository/webkit/trunk@113194 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- PerformanceTests/ChangeLog | 11 ++ .../inspector/detailed-heapshots-smoke-test.html | 1 + Source/WebCore/ChangeLog | 20 +++ Source/WebCore/inspector/front-end/HeapSnapshot.js | 134 +++++++++++++-------- 4 files changed, 115 insertions(+), 51 deletions(-) diff --git a/PerformanceTests/ChangeLog b/PerformanceTests/ChangeLog index a74a198..ae1fb0f 100644 --- a/PerformanceTests/ChangeLog +++ b/PerformanceTests/ChangeLog @@ -1,3 +1,14 @@ +2012-04-04 Ilya Tikhonovsky + + Web Inspector: linearise aggregate's retaining size calculation. + https://bugs.webkit.org/show_bug.cgi?id=83125 + + This version is twice as fast as the original and it is non-recursive. + + Reviewed by Yury Semikhatsky. + + * inspector/detailed-heapshots-smoke-test.html: + 2012-03-30 David Barr Split up top-level .gitignore and .gitattributes diff --git a/PerformanceTests/inspector/detailed-heapshots-smoke-test.html b/PerformanceTests/inspector/detailed-heapshots-smoke-test.html index 4e7f7a3..fae4854 100644 --- a/PerformanceTests/inspector/detailed-heapshots-smoke-test.html +++ b/PerformanceTests/inspector/detailed-heapshots-smoke-test.html @@ -24,6 +24,7 @@ function test() InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildDominatedNodes"); InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_calculateFlags"); InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildAggregates"); + InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_calculateClassesRetainedSize"); InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_calculateObjectToWindowDistance"); InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markDetachedDOMTreeNodes"); InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markQueriableHeapObjects"); diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog index f5af571..255bea3 100644 --- a/Source/WebCore/ChangeLog +++ b/Source/WebCore/ChangeLog @@ -1,3 +1,23 @@ +2012-04-04 Ilya Tikhonovsky + + Web Inspector: linearise aggregate's retaining size calculation. + https://bugs.webkit.org/show_bug.cgi?id=83125 + + This version is twice as fast as the original and it is non-recursive. + + Reviewed by Yury Semikhatsky. + + * inspector/front-end/HeapSnapshot.js: + (WebInspector.HeapSnapshot.prototype._getDominatedIndex): was moved closer to it's usage + (WebInspector.HeapSnapshot.prototype._calculateClassesRetainedSize): it was _buildAggregates' inner function forDominatedNodes. + it was: + a) extracted from _buildAggregates; + b) made non-recursive; + c) many getters were inlined; + d) subarray of dominating nodes were inlined too. + (WebInspector.HeapSnapshot.prototype._buildAggregates): many getters were inlined. + (WebInspector.HeapSnapshot.prototype.aggregates): + 2012-04-04 Allan Sandfeld Jensen Best clickable node might return non "clickable" node. diff --git a/Source/WebCore/inspector/front-end/HeapSnapshot.js b/Source/WebCore/inspector/front-end/HeapSnapshot.js index e7a1213..40eccb0 100644 --- a/Source/WebCore/inspector/front-end/HeapSnapshot.js +++ b/Source/WebCore/inspector/front-end/HeapSnapshot.js @@ -1010,6 +1010,13 @@ WebInspector.HeapSnapshot.prototype = { return this.rootNode.retainedSize; }, + _getDominatedIndex: function(nodeIndex) + { + if (nodeIndex % this._nodeFieldCount) + throw new Error("Invalid nodeIndex: " + nodeIndex); + return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount]; + }, + _dominatedNodesOfNode: function(node) { var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex); @@ -1029,28 +1036,30 @@ WebInspector.HeapSnapshot.prototype = { this._aggregatesSortedFlags = {}; } - var aggregates = this._aggregates[key]; - if (aggregates) { + var aggregatesByClassName = this._aggregates[key]; + if (aggregatesByClassName) { if (sortedIndexes && !this._aggregatesSortedFlags[key]) { - this._sortAggregateIndexes(aggregates); + this._sortAggregateIndexes(aggregatesByClassName); this._aggregatesSortedFlags[key] = sortedIndexes; } - return aggregates; + return aggregatesByClassName; } var filter; if (filterString) filter = this._parseFilter(filterString); - aggregates = this._buildAggregates(filter); + var aggregates = this._buildAggregates(filter); + this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter); + aggregatesByClassName = aggregates.aggregatesByClassName; if (sortedIndexes) - this._sortAggregateIndexes(aggregates); + this._sortAggregateIndexes(aggregatesByClassName); this._aggregatesSortedFlags[key] = sortedIndexes; - this._aggregates[key] = aggregates; + this._aggregates[key] = aggregatesByClassName; - return aggregates; + return aggregatesByClassName; }, _calculateObjectToWindowDistance: function() @@ -1115,19 +1124,23 @@ WebInspector.HeapSnapshot.prototype = { _buildAggregates: function(filter) { - function shouldSkip(node) - { - if (filter && !filter(node)) - return true; - if (!node.selfSize && !node.isNative) - return true; - return false; - } - var aggregates = {}; var aggregatesByClassName = {}; - for (var node = new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex); node.nodeIndex < this._onlyNodes.length; node.nodeIndex = node._nextNodeIndex) { - if (shouldSkip(node)) + var onlyNodes = this._onlyNodes; + var onlyNodesLength = onlyNodes.length; + var nodeNativeType = this._nodeNativeType; + var nodeFieldsCount = this._nodeFieldCount; + var selfSizeOffset = this._nodeSelfSizeOffset; + var nodeTypeOffset = this._nodeTypeOffset; + var node = new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex); + var distancesToWindow = this._distancesToWindow; + + for (var nodeIndex = this._rootNodeIndex; nodeIndex < onlyNodesLength; nodeIndex += nodeFieldsCount) { + node.nodeIndex = nodeIndex; + var selfSize = onlyNodes[nodeIndex + selfSizeOffset]; + if (filter && !filter(node)) + continue; + if (!selfSize && onlyNodes[nodeIndex + nodeTypeOffset] !== nodeNativeType) continue; var classIndex = node.classIndex; if (!(classIndex in aggregates)) { @@ -1135,49 +1148,75 @@ WebInspector.HeapSnapshot.prototype = { var nameMatters = nodeType === "object" || nodeType === "native"; var value = { count: 1, - distanceToWindow: node.distanceToWindow, - self: node.selfSize, + distanceToWindow: distancesToWindow[nodeIndex], + self: selfSize, maxRet: 0, type: nodeType, name: nameMatters ? node.name : null, - idxs: [node.nodeIndex] + idxs: [nodeIndex] }; aggregates[classIndex] = value; aggregatesByClassName[node.className] = value; } else { var clss = aggregates[classIndex]; - clss.distanceToWindow = Math.min(clss.distanceToWindow, node.distanceToWindow); + clss.distanceToWindow = Math.min(clss.distanceToWindow, distancesToWindow[nodeIndex]); ++clss.count; - clss.self += node.selfSize; - clss.idxs.push(node.nodeIndex); + clss.self += selfSize; + clss.idxs.push(nodeIndex); } } - // Recursively visit dominators tree and sum up retained sizes - // of topmost objects in each class. - // This gives us retained sizes for classes. + // Shave off provisionally allocated space. + for (var classIndex in aggregates) + aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice(0); + return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates}; + }, + + _calculateClassesRetainedSize: function(aggregates, filter) + { + var rootNodeIndex = this._rootNodeIndex; + var node = new WebInspector.HeapSnapshotNode(this, rootNodeIndex); + var list = [rootNodeIndex]; + var sizes = [-1]; + var classes = []; var seenClassNameIndexes = {}; - var snapshot = this; - function forDominatedNodes(nodeIndex) - { - var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex); + var nodeFieldCount = this._nodeFieldCount; + var nodeTypeOffset = this._nodeTypeOffset; + var nodeNativeType = this._nodeNativeType; + var dominatedNodes = this._dominatedNodes; + var onlyNodes = this._onlyNodes; + var firstDominatedNodeIndex = this._firstDominatedNodeIndex; + + while (list.length) { + var nodeIndex = list.pop(); + node.nodeIndex = nodeIndex; var classIndex = node.classIndex; var seen = !!seenClassNameIndexes[classIndex]; - if (!seen && classIndex in aggregates && !shouldSkip(node)) { + var nodeOrdinal = nodeIndex / nodeFieldCount; + var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal]; + var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1]; + + if (!seen && + (!filter || filter(node)) && + (node.selfSize || onlyNodes[nodeIndex + nodeTypeOffset] === nodeNativeType) + ) { aggregates[classIndex].maxRet += node.retainedSize; - seenClassNameIndexes[classIndex] = true; + if (dominatedIndexFrom !== dominatedIndexTo) { + seenClassNameIndexes[classIndex] = true; + sizes.push(list.length); + classes.push(classIndex); + } + } + for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++) + list.push(dominatedNodes[i]); + + var l = list.length; + while (sizes[sizes.length - 1] === l) { + sizes.pop(); + classIndex = classes.pop(); + seenClassNameIndexes[classIndex] = false; } - var dominatedNodes = snapshot._dominatedNodesOfNode(node); - for (var i = 0; i < dominatedNodes.length; i++) - forDominatedNodes(dominatedNodes.item(i)); - seenClassNameIndexes[classIndex] = seen; } - forDominatedNodes(this._rootNodeIndex); - - // Shave off provisionally allocated space. - for (var classIndex in aggregates) - aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice(0); - return aggregatesByClassName; }, _sortAggregateIndexes: function(aggregates) @@ -1234,13 +1273,6 @@ WebInspector.HeapSnapshot.prototype = { } }, - _getDominatedIndex: function(nodeIndex) - { - if (nodeIndex % this._nodeFieldCount) - throw new Error("Invalid nodeIndex: " + nodeIndex); - return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount]; - }, - _markInvisibleEdges: function() { // Mark hidden edges of global objects as invisible. -- 2.7.4