Changeset 117962 in webkit

Timestamp:

May 22, 2012 6:25:54 AM (12 years ago)

Author:

loislo@chromium.org

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:

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/inspector/profiler/heap-snapshot.html (modified) (2 diffs)
• Source/WebCore/ChangeLog (modified) (1 diff)
• Source/WebCore/inspector/front-end/HeapSnapshot.js (modified) (12 diffs)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2012-05-22  Ilya Tikhonovsky  <loislo@chromium.org>
+
+        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  <christophe.dumez@intel.com>
 

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

@@ -99 +99 @@
         {
             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();
         },
@@ -110 +110 @@
             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");

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2012-05-22  Ilya Tikhonovsky  <loislo@chromium.org>
+
+        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  <yurys@chromium.org>
 

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

@@ -459 +459 @@
     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;
     },
 
@@ -721 +722 @@
         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();
@@ -1088 +1090 @@
 
         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);
@@ -1126 +1128 @@
             } else {
                 nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex;
-                postOrderIndex2NodeIndex[postOrderIndex++] = nodeIndex;
+                postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal;
                 --nodesToVisitLength;
             }
         }
-        return {postOrderIndex2NodeIndex: postOrderIndex2NodeIndex, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
+        return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
     },
 
@@ -1137 +1139 @@
     // 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;
@@ -1159 +1161 @@
         var flag = this._nodeFlags.pageObject;
 
-        var nodesCount = postOrderIndex2NodeIndex.length;
+        var nodesCount = postOrderIndex2NodeOrdinal.length;
         var rootPostOrderedIndex = nodesCount - 1;
         var noEntry = nodesCount;
@@ -1194 +1196 @@
                 if (dominators[postOrderIndex] === rootPostOrderedIndex)
                     continue;
-                var nodeOrdinal = postOrderIndex2NodeIndex[postOrderIndex] / nodeFieldCount;
+                var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
                 var nodeFlag = !!(flags[nodeOrdinal] & flag);
                 var newDominatorIndex = noEntry;
@@ -1232 +1234 @@
                     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
@@ -1250 +1252 @@
         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;
@@ -1275 +1277 @@
             retainedSizes[currentNodeOrdinal] += nodeSelfSize;
             do {
-                currentNodeOrdinal = dominatorsTree[currentNodeOrdinal] / nodeFieldCount;
+                currentNodeOrdinal = dominatorsTree[currentNodeOrdinal];
                 retainedSizes[currentNodeOrdinal] += nodeSelfSize;
             } while (currentNodeOrdinal !== rootNodeOrdinal);
@@ -1298 +1300 @@
         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.
@@ -1311 +1313 @@
         // 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]);