Web Inspector: speed up _calculateRetainedSizes function
authorloislo@chromium.org <loislo@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Jun 2012 12:38:30 +0000 (12:38 +0000)
committerloislo@chromium.org <loislo@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 4 Jun 2012 12:38:30 +0000 (12:38 +0000)
https://bugs.webkit.org/show_bug.cgi?id=87863

Patch by Alexei Filippov <alexeif@chromium.org> on 2012-06-04
Reviewed by Yury Semikhatsky.

PerformanceTests:

* inspector/heap-snapshot-advanced.html: Added.
* inspector/heap-snapshot-performance-test.js: Copied from PerformanceTests/inspector/heap-snapshot.html.
(test.performanceTest.step0):
(test.performanceTest.step1):
(test.performanceTest.step2):
(test.performanceTest.cleanup):
(test.performanceTest.done):
(test.performanceTest):
(test):
* inspector/heap-snapshot.html:

Source/WebCore:

* inspector/front-end/HeapSnapshot.js:
(WebInspector.HeapSnapshot.prototype._calculateRetainedSizes):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@119389 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/ChangeLog
PerformanceTests/inspector/heap-snapshot-advanced.html [new file with mode: 0644]
PerformanceTests/inspector/heap-snapshot-performance-test.js [new file with mode: 0644]
PerformanceTests/inspector/heap-snapshot.html
Source/WebCore/ChangeLog
Source/WebCore/inspector/front-end/HeapSnapshot.js

index 0562bdf65b2d9d2eee9420c7c953d1f5053fe33c..cf7adc7b2c1041dd1beef5faf76d16dee374a176 100644 (file)
@@ -1,3 +1,21 @@
+2012-06-04  Alexei Filippov  <alexeif@chromium.org>
+
+        Web Inspector: speed up _calculateRetainedSizes function
+        https://bugs.webkit.org/show_bug.cgi?id=87863
+
+        Reviewed by Yury Semikhatsky.
+
+        * inspector/heap-snapshot-advanced.html: Added.
+        * inspector/heap-snapshot-performance-test.js: Copied from PerformanceTests/inspector/heap-snapshot.html.
+        (test.performanceTest.step0):
+        (test.performanceTest.step1):
+        (test.performanceTest.step2):
+        (test.performanceTest.cleanup):
+        (test.performanceTest.done):
+        (test.performanceTest):
+        (test):
+        * inspector/heap-snapshot.html:
+
 2012-06-03  Kentaro Hara  <haraken@chromium.org>
 
         [perf-test] Add a benchmark of querySelector() for an element that appears in the depths in the document
diff --git a/PerformanceTests/inspector/heap-snapshot-advanced.html b/PerformanceTests/inspector/heap-snapshot-advanced.html
new file mode 100644 (file)
index 0000000..58b48f0
--- /dev/null
@@ -0,0 +1,35 @@
+<html>
+<head>
+  <script src="../../LayoutTests/http/tests/inspector/inspector-test.js"></script>
+  <script src="../../LayoutTests/inspector/profiler/heap-snapshot-test.js"></script>
+  <script src="performance-test.js"></script>
+  <script src="heap-snapshot-performance-test.js"></script>
+<script>
+
+function makeLinkedList(n)
+{
+    var node = {};
+    while (--n)
+        node = { next: node };
+    return node;
+}
+
+function makeDoubleLinkedList(n)
+{
+  var tail = {};
+  var head = tail;
+  while (--n) {
+    head = { next: head };
+    head.next.prev = head;
+  }
+  return { head: head, tail: tail };
+}
+
+var list = makeLinkedList(20000);
+var double_list = makeDoubleLinkedList(5000);
+
+</script>
+</head>
+<body onload="runTest()">
+</body>
+</html>
diff --git a/PerformanceTests/inspector/heap-snapshot-performance-test.js b/PerformanceTests/inspector/heap-snapshot-performance-test.js
new file mode 100644 (file)
index 0000000..bfbcc97
--- /dev/null
@@ -0,0 +1,72 @@
+function test()
+{
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildRetainers");
+    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, "_calculateRetainedSizes");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markDetachedDOMTreeNodes");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markQueriableHeapObjects");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markPageOwnedNodes");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_splitNodesAndContainmentEdges");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildPostOrderIndex");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildDominatorTree");
+    InspectorTest.measureFunction(WebInspector.HeapSnapshotConstructorsDataGrid.prototype, "_aggregatesReceived");
+
+    function performanceTest(timer)
+    {
+        var transferTimerCookie;
+        var showTimerCookie;
+        var changeViewTimerCookie;
+        var clearTimerCookie;
+
+        var testName = /([^\/]+)\.html$/.exec(WebInspector.inspectedPageURL)[1];
+        var fullTimerCookie = timer.start("full-summary-snapshot-time");
+        var backendTimerCookie = timer.start("take-snapshot");
+        ProfilerAgent.takeHeapSnapshot(step0);
+
+        function step0()
+        {
+            timer.finish(backendTimerCookie);
+            transferTimerCookie = timer.start("transfer-snapshot");
+            var profiles = WebInspector.panels.profiles.getProfiles("HEAP");
+            WebInspector.panels.profiles.showProfile(profiles[profiles.length - 1]);
+            InspectorTest.addSniffer(WebInspector.panels.profiles, "_finishHeapSnapshot", step1);
+        }
+
+        function step1(uid)
+        {
+            timer.finish(transferTimerCookie);
+            showTimerCookie = timer.start("show-snapshot");
+            var panel = WebInspector.panels.profiles;
+            var profile = panel._profilesIdMap[panel._makeKey(uid, WebInspector.HeapSnapshotProfileType.TypeId)];
+            profile.load(step2); // Add load callback.
+        }
+
+        function step2()
+        {
+            timer.finish(showTimerCookie);
+            changeViewTimerCookie = timer.start("switch-to-containment-view");
+            InspectorTest.switchToView("Containment", cleanup);
+        }
+
+        function cleanup()
+        {
+            timer.finish(changeViewTimerCookie);
+            timer.finish(fullTimerCookie);
+            clearTimerCookie = timer.start("clear-snapshot");
+            ProfilerAgent.clearProfiles(done);
+            WebInspector.panels.profiles._reset();
+        }
+
+        function done()
+        {
+            timer.finish(clearTimerCookie);
+            timer.done(testName);
+        }
+    }
+
+    InspectorTest.runPerformanceTest(performanceTest, 60000);
+}
index ba53874952300d77f4f70501e9f63e4da05769d4..0fabb2195b296266aa98a2916a50ef0631c62f4a 100644 (file)
@@ -3,80 +3,9 @@
   <script src="../../LayoutTests/http/tests/inspector/inspector-test.js"></script>
   <script src="../../LayoutTests/inspector/profiler/heap-snapshot-test.js"></script>
   <script src="performance-test.js"></script>
+  <script src="heap-snapshot-performance-test.js"></script>
 <script>
 
-function test()
-{
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildRetainers");
-    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, "_calculateRetainedSizes");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markDetachedDOMTreeNodes");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markQueriableHeapObjects");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_markPageOwnedNodes");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_splitNodesAndContainmentEdges");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildPostOrderIndex");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshot.prototype, "_buildDominatorTree");
-    InspectorTest.measureFunction(WebInspector.HeapSnapshotConstructorsDataGrid.prototype, "_aggregatesReceived");
-
-    function performanceTest(timer)
-    {
-        var transferTimerCookie;
-        var showTimerCookie;
-        var changeViewTimerCookie;
-        var clearTimerCookie;
-
-        var fullTimerCookie = timer.start("full-summary-snapshot-time");
-        var backendTimerCookie = timer.start("take-snapshot");
-        ProfilerAgent.takeHeapSnapshot(step0);
-
-        function step0()
-        {
-            timer.finish(backendTimerCookie);
-            transferTimerCookie = timer.start("transfer-snapshot");
-            var profiles = WebInspector.panels.profiles.getProfiles("HEAP");
-            WebInspector.panels.profiles.showProfile(profiles[profiles.length - 1]);
-            InspectorTest.addSniffer(WebInspector.panels.profiles, "_finishHeapSnapshot", step1);
-        }
-
-        function step1(uid)
-        {
-            timer.finish(transferTimerCookie);
-            showTimerCookie = timer.start("show-snapshot");
-            var panel = WebInspector.panels.profiles;
-            var profile = panel._profilesIdMap[panel._makeKey(uid, WebInspector.HeapSnapshotProfileType.TypeId)];
-            profile.load(step2); // Add load callback.
-        }
-
-        function step2()
-        {
-            timer.finish(showTimerCookie);
-            changeViewTimerCookie = timer.start("switch-to-containment-view");
-            InspectorTest.switchToView("Containment", cleanup);
-        }
-
-        function cleanup()
-        {
-            timer.finish(changeViewTimerCookie);
-            timer.finish(fullTimerCookie);
-            clearTimerCookie = timer.start("clear-snapshot");
-            ProfilerAgent.clearProfiles(done);
-            WebInspector.panels.profiles._reset();
-        }
-
-        function done()
-        {
-            timer.finish(clearTimerCookie);
-            timer.done("heap-snapshot");
-        }
-    }
-
-    InspectorTest.runPerformanceTest(performanceTest, 60000);
-}
-
 var counter = 0;
 
 function makeObjectsTree(deep)
index 99990cb480f32a143abc7be866aafd75afd4fd0a..6b65d1a903ca864afcc8cec80e01c55a9fba1c99 100644 (file)
@@ -1,3 +1,13 @@
+2012-06-04  Alexei Filippov  <alexeif@chromium.org>
+
+        Web Inspector: speed up _calculateRetainedSizes function
+        https://bugs.webkit.org/show_bug.cgi?id=87863
+
+        Reviewed by Yury Semikhatsky.
+
+        * inspector/front-end/HeapSnapshot.js:
+        (WebInspector.HeapSnapshot.prototype._calculateRetainedSizes):
+
 2012-06-04  Yury Semikhatsky  <yurys@chromium.org>
 
         Web Inspector: add unknown size to the memory pie-chart legend
index 4206cf62e8f45f3ede933ab925980c339c533898..f2702822f6f7a96faabdf264daffa7c3416feb42 100644 (file)
@@ -705,7 +705,7 @@ WebInspector.HeapSnapshot.prototype = {
         var result = this._buildPostOrderIndex();
         // 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._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal);
         this._buildDominatedNodes();
     },
 
@@ -1248,30 +1248,24 @@ WebInspector.HeapSnapshot.prototype = {
         return dominatorsTree;
     },
 
-    _calculateRetainedSizes: function()
+    _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal)
     {
-        // As for the dominators tree we only know parent nodes, not
-        // children, to sum up total sizes we "bubble" node's self size
-        // adding it to all of its parents.
+        var nodeCount = this.nodeCount;
         var nodes = this._nodes;
         var nodeSelfSizeOffset = this._nodeSelfSizeOffset;
         var nodeFieldCount = this._nodeFieldCount;
         var dominatorsTree = this._dominatorsTree;
-        var retainedSizes = new Uint32Array(this.nodeCount);
+        var retainedSizes = this._retainedSizes = new Uint32Array(nodeCount);
         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
 
-        for (var nodeOrdinal = 0, nodeSelfSizeIndex = nodeSelfSizeOffset, l = this.nodeCount;
-             nodeOrdinal < l;
-             ++nodeOrdinal, nodeSelfSizeIndex += nodeFieldCount) {
-            var nodeSelfSize = nodes[nodeSelfSizeIndex];
-            var currentNodeOrdinal = nodeOrdinal;
-            retainedSizes[currentNodeOrdinal] += nodeSelfSize;
-            do {
-                currentNodeOrdinal = dominatorsTree[currentNodeOrdinal];
-                retainedSizes[currentNodeOrdinal] += nodeSelfSize;
-            } while (currentNodeOrdinal !== rootNodeOrdinal);
+        retainedSizes[rootNodeOrdinal] = nodes[this._rootNodeIndex + nodeSelfSizeOffset];
+        // Propagate retained sizes for each node excluding root, as it refers to self.
+        for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) {
+            var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
+            var dominatorOrdinal = dominatorsTree[nodeOrdinal];
+            retainedSizes[nodeOrdinal] += nodes[nodeOrdinal * nodeFieldCount + nodeSelfSizeOffset];
+            retainedSizes[dominatorOrdinal] += retainedSizes[nodeOrdinal];
         }
-        this._retainedSizes = retainedSizes;
     },
 
     _buildDominatedNodes: function()