- Revision
- 117962
- Author
- [email protected]
- Date
- 2012-05-22 06:25:54 -0700 (Tue, 22 May 2012)
Log Message
Web Inspector: HeapSnapshot: speed-up calculateRetainedSize functon.
https://bugs.webkit.org/show_bug.cgi?id=87124
I found that in all dominators related functions we use nodeOrdinals.
At the moment we divide nodeIndex to nodeFieldCount and this operation too expensive for these simple algorithms.
Reviewed by Yury Semikhatsky.
Covered by existing tests.
Source/WebCore:
* inspector/front-end/HeapSnapshot.js:
(WebInspector.HeapSnapshotNode.prototype.get dominatorIndex):
(WebInspector.HeapSnapshot.prototype._init):
(WebInspector.HeapSnapshot.prototype._buildPostOrderIndex):
(WebInspector.HeapSnapshot.prototype._buildDominatorTree):
(WebInspector.HeapSnapshot.prototype._calculateRetainedSizes):
(WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
LayoutTests:
* inspector/profiler/heap-snapshot.html:
Modified Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (117961 => 117962)
--- trunk/LayoutTests/ChangeLog 2012-05-22 13:07:14 UTC (rev 117961)
+++ trunk/LayoutTests/ChangeLog 2012-05-22 13:25:54 UTC (rev 117962)
@@ -1,3 +1,17 @@
+2012-05-22 Ilya Tikhonovsky <[email protected]>
+
+ Web Inspector: HeapSnapshot: speed-up calculateRetainedSize functon.
+ https://bugs.webkit.org/show_bug.cgi?id=87124
+
+ I found that in all dominators related functions we use nodeOrdinals.
+ At the moment we divide nodeIndex to nodeFieldCount and this operation too expensive for these simple algorithms.
+
+ Reviewed by Yury Semikhatsky.
+
+ Covered by existing tests.
+
+ * inspector/profiler/heap-snapshot.html:
+
2012-05-22 Christophe Dumez <[email protected]>
[EFL] Test expectations need updating
Modified: trunk/LayoutTests/inspector/profiler/heap-snapshot.html (117961 => 117962)
--- trunk/LayoutTests/inspector/profiler/heap-snapshot.html 2012-05-22 13:07:14 UTC (rev 117961)
+++ trunk/LayoutTests/inspector/profiler/heap-snapshot.html 2012-05-22 13:25:54 UTC (rev 117962)
@@ -98,10 +98,10 @@
function heapSnapshotPostOrderIndexTest(next)
{
var snapshot = new WebInspector.HeapSnapshot(InspectorTest.createHeapSnapshotMock());
- var postOrderIndex = snapshot._buildPostOrderIndex().postOrderIndex2NodeIndex;
- var expected = [28,35,21,14,7,0];
+ var postOrderIndex2NodeOrdinal = snapshot._buildPostOrderIndex().postOrderIndex2NodeOrdinal;
+ var expected = [4,5,3,2,1,0];
for (var i = 0; i < expected.length; ++i)
- InspectorTest.assertEquals(expected[i], postOrderIndex[i], "Post ordered indexes");
+ InspectorTest.assertEquals(expected[i], postOrderIndex2NodeOrdinal[i], "Post ordered indexes");
next();
},
@@ -109,8 +109,8 @@
{
var snapshot = new WebInspector.HeapSnapshot(InspectorTest.createHeapSnapshotMock());
var result = snapshot._buildPostOrderIndex();
- var dominatorsTree = snapshot._buildDominatorTree(result.postOrderIndex2NodeIndex, result.nodeOrdinal2PostOrderIndex);
- var expected = [0, 0, 0, 0, 14, 21];
+ var dominatorsTree = snapshot._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex);
+ var expected = [0, 0, 0, 0, 2, 3];
for (var i = 0; i < expected.length; ++i)
InspectorTest.assertEquals(expected[i], dominatorsTree[i], "Dominators Tree");
next();
Modified: trunk/Source/WebCore/ChangeLog (117961 => 117962)
--- trunk/Source/WebCore/ChangeLog 2012-05-22 13:07:14 UTC (rev 117961)
+++ trunk/Source/WebCore/ChangeLog 2012-05-22 13:25:54 UTC (rev 117962)
@@ -1,3 +1,23 @@
+2012-05-22 Ilya Tikhonovsky <[email protected]>
+
+ Web Inspector: HeapSnapshot: speed-up calculateRetainedSize functon.
+ https://bugs.webkit.org/show_bug.cgi?id=87124
+
+ I found that in all dominators related functions we use nodeOrdinals.
+ At the moment we divide nodeIndex to nodeFieldCount and this operation too expensive for these simple algorithms.
+
+ Reviewed by Yury Semikhatsky.
+
+ Covered by existing tests.
+
+ * inspector/front-end/HeapSnapshot.js:
+ (WebInspector.HeapSnapshotNode.prototype.get dominatorIndex):
+ (WebInspector.HeapSnapshot.prototype._init):
+ (WebInspector.HeapSnapshot.prototype._buildPostOrderIndex):
+ (WebInspector.HeapSnapshot.prototype._buildDominatorTree):
+ (WebInspector.HeapSnapshot.prototype._calculateRetainedSizes):
+ (WebInspector.HeapSnapshot.prototype._buildDominatedNodes):
+
2012-05-22 Yury Semikhatsky <[email protected]>
Web Inspector: annotate InjectedScriptSource.js for closure compiler
Modified: trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js (117961 => 117962)
--- trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js 2012-05-22 13:07:14 UTC (rev 117961)
+++ trunk/Source/WebCore/inspector/front-end/HeapSnapshot.js 2012-05-22 13:25:54 UTC (rev 117962)
@@ -458,7 +458,8 @@
get dominatorIndex()
{
- return this._snapshot._dominatorsTree[this.nodeIndex / this._snapshot._nodeFieldCount];
+ var nodeFieldCount = this._snapshot._nodeFieldCount;
+ return this._snapshot._dominatorsTree[this.nodeIndex / this._snapshot._nodeFieldCount] * nodeFieldCount;
},
get edges()
@@ -720,7 +721,8 @@
this._calculateFlags();
this._calculateObjectToWindowDistance();
var result = this._buildPostOrderIndex();
- this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeIndex, result.nodeOrdinal2PostOrderIndex);
+ // Actually it is array that maps node ordinal number to dominator node ordinal number.
+ this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex);
this._calculateRetainedSizes();
this._buildDominatedNodes();
},
@@ -1087,7 +1089,7 @@
var flag = this._nodeFlags.pageObject;
var nodesToVisit = new Uint32Array(nodeCount);
- var postOrderIndex2NodeIndex = new Uint32Array(nodeCount);
+ var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount);
var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount);
var painted = new Uint8Array(nodeCount);
var nodesToVisitLength = 0;
@@ -1125,21 +1127,21 @@
}
} else {
nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex;
- postOrderIndex2NodeIndex[postOrderIndex++] = nodeIndex;
+ postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal;
--nodesToVisitLength;
}
}
- return {postOrderIndex2NodeIndex: postOrderIndex2NodeIndex, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
+ return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
},
// The algorithm is based on the article:
// K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
// Softw. Pract. Exper. 4 (2001), pp. 1-10.
/**
- * @param {Array.<number>} postOrderIndex2NodeIndex
+ * @param {Array.<number>} postOrderIndex2NodeOrdinal
* @param {Array.<number>} nodeOrdinal2PostOrderIndex
*/
- _buildDominatorTree: function(postOrderIndex2NodeIndex, nodeOrdinal2PostOrderIndex)
+ _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex)
{
var nodeFieldCount = this._nodeFieldCount;
var nodes = this._nodes;
@@ -1158,7 +1160,7 @@
var flags = this._flags;
var flag = this._nodeFlags.pageObject;
- var nodesCount = postOrderIndex2NodeIndex.length;
+ var nodesCount = postOrderIndex2NodeOrdinal.length;
var rootPostOrderedIndex = nodesCount - 1;
var noEntry = nodesCount;
var dominators = new Uint32Array(nodesCount);
@@ -1193,7 +1195,7 @@
// then it can't propagate any further.
if (dominators[postOrderIndex] === rootPostOrderedIndex)
continue;
- var nodeOrdinal = postOrderIndex2NodeIndex[postOrderIndex] / nodeFieldCount;
+ var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
var nodeFlag = !!(flags[nodeOrdinal] & flag);
var newDominatorIndex = noEntry;
var beginRetainerIndex = firstRetainerIndex[nodeOrdinal];
@@ -1231,8 +1233,8 @@
if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
dominators[postOrderIndex] = newDominatorIndex;
changed = true;
- nodeIndex = postOrderIndex2NodeIndex[postOrderIndex];
- nodeOrdinal = nodeIndex / nodeFieldCount;
+ nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
+ nodeIndex = nodeOrdinal * nodeFieldCount;
beginEdgeToNodeFieldIndex = nodes[nodeIndex + firstEdgeIndexOffset] + edgeToNodeOffset;
endEdgeToNodeFieldIndex = nodeOrdinal < nodesCount - 1
? nodes[nodeIndex + firstEdgeIndexOffset + nodeFieldCount]
@@ -1249,8 +1251,8 @@
var dominatorsTree = new Uint32Array(nodesCount);
for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) {
- var nodeOrdinal = postOrderIndex2NodeIndex[postOrderIndex] / nodeFieldCount;
- dominatorsTree[nodeOrdinal] = postOrderIndex2NodeIndex[dominators[postOrderIndex]];
+ var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
+ dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]];
}
return dominatorsTree;
},
@@ -1274,7 +1276,7 @@
var currentNodeOrdinal = nodeOrdinal;
retainedSizes[currentNodeOrdinal] += nodeSelfSize;
do {
- currentNodeOrdinal = dominatorsTree[currentNodeOrdinal] / nodeFieldCount;
+ currentNodeOrdinal = dominatorsTree[currentNodeOrdinal];
retainedSizes[currentNodeOrdinal] += nodeSelfSize;
} while (currentNodeOrdinal !== rootNodeOrdinal);
}
@@ -1297,7 +1299,7 @@
var nodeFieldCount = this._nodeFieldCount;
var dominatorsTree = this._dominatorsTree;
for (var nodeOrdinal = 1, l = this.nodeCount; nodeOrdinal < l; ++nodeOrdinal)
- ++indexArray[dominatorsTree[nodeOrdinal] / this._nodeFieldCount];
+ ++indexArray[dominatorsTree[nodeOrdinal]];
// Put in the first slot of each dominatedNodes slice the count of entries
// that will be filled.
var firstDominatedNodeIndex = 0;
@@ -1310,7 +1312,7 @@
// Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at
// index 0) as it is the only node that dominates itself.
for (var nodeOrdinal = 1, l = this.nodeCount; nodeOrdinal < l; ++nodeOrdinal) {
- var dominatorOrdinal = dominatorsTree[nodeOrdinal] / nodeFieldCount;
+ var dominatorOrdinal = dominatorsTree[nodeOrdinal];
var dominatedRefIndex = indexArray[dominatorOrdinal];
dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount;
