DevTools: extract CPU profile independent part of CPUProfileNode.

third_party/WebKit/Source/devtools/front_end/sdk/CPUProfileDataModel.js

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+/**
+ * @constructor
+ * @extends {WebInspector.ProfileNode}
+ * @param {!ProfilerAgent.CPUProfileNode} sourceNode
+ * @param {number} sampleTime
+ */
+WebInspector.CPUProfileNode = function(sourceNode, sampleTime)
+{
+    WebInspector.ProfileNode.call(this);
+    this.functionName = sourceNode.functionName;
+    this.scriptId = sourceNode.scriptId;
+    this.url = sourceNode.url;
+    this.lineNumber = sourceNode.lineNumber;
+    this.columnNumber = sourceNode.columnNumber;
+    this.id = sourceNode.id;
+    this.self = sourceNode.hitCount * sampleTime;
+    this.callUID = sourceNode.callUID;
+    this.positionTicks = sourceNode.positionTicks;
+    this.deoptReason = sourceNode.deoptReason;

[caseq, 2016/04/13 17:21:12]

Why do we have to do this? Having to copy all fields of all nodes is quite
unfortunate. Can these be getters?

[alph, 2016/04/13 19:05:07]

This is done just once for the tree. I want to have fast access though.

+    // TODO: Remove the following field in favor of this.self
+    this.selfTime = this.self;
+}
+
+WebInspector.CPUProfileNode.prototype = {
+    __proto__: WebInspector.ProfileNode.prototype
+}
 
 /**
  * @constructor
+ * @extends {WebInspector.ProfileTreeModel}
  * @param {!ProfilerAgent.CPUProfile} profile
  */
 WebInspector.CPUProfileDataModel = function(profile)
 {
-    this.profileHead = profile.head;
     this.samples = profile.samples;
     this.timestamps = profile.timestamps;
+    // Convert times from sec to msec.
     this.profileStartTime = profile.startTime * 1000;
     this.profileEndTime = profile.endTime * 1000;
-    this._assignParentsInProfile();
+    if (!WebInspector.moduleSetting("showNativeFunctionsInJSProfile").get())
+        this._filterNativeFrames(profile.head);
+    this.profileHead = this._translateProfileTree(profile.head);
+    WebInspector.ProfileTreeModel.call(this, this.profileHead, this.profileStartTime, this.profileEndTime);
+    this._extractMetaNodes();
     if (this.samples) {
+        this._buildIdToNodeMap();
         this._sortSamples();
         this._normalizeTimestamps();
-        this._buildIdToNodeMap();
         this._fixMissingSamples();
     }
-    if (!WebInspector.moduleSetting("showNativeFunctionsInJSProfile").get())
-        this._filterNativeFrames();
-    this._assignDepthsInProfile();
-    this._calculateTimes(profile);
+    this._assignTotalTimes(this.profileHead);
 }
 
 WebInspector.CPUProfileDataModel.prototype = {
     /**
-     * @param {!ProfilerAgent.CPUProfile} profile
+     * @param {!ProfilerAgent.CPUProfileNode} head
      */
-    _calculateTimes: function(profile)
-    {
-        function totalHitCount(node) {
-            var result = node.hitCount;
-            for (var i = 0; i < node.children.length; i++)
-                result += totalHitCount(node.children[i]);
-            return result;
-        }
-        profile.totalHitCount = totalHitCount(profile.head);
-        this.totalHitCount = profile.totalHitCount;
-
-        var duration = this.profileEndTime - this.profileStartTime;
-        var samplingInterval = duration / profile.totalHitCount;
-        this.samplingInterval = samplingInterval;
-
-        function calculateTimesForNode(node) {
-            node.selfTime = node.hitCount * samplingInterval;
-            var totalHitCount = node.hitCount;
-            for (var i = 0; i < node.children.length; i++)
-                totalHitCount += calculateTimesForNode(node.children[i]);
-            node.totalTime = totalHitCount * samplingInterval;
-            return totalHitCount;
-        }
-        calculateTimesForNode(profile.head);
-    },
-
-    _filterNativeFrames: function()
+    _filterNativeFrames: function(head)
     {
         if (this.samples) {
+            var idToNode = {};

[caseq, 2016/04/13 17:21:12]

use Map()?

[alph, 2016/04/13 19:05:07]

Done.

+            var stack = [head];
+            while (stack.length) {

[caseq, 2016/04/13 17:21:12]

can this be combined with tree traversal we perform in processSubtree?

[alph, 2016/04/13 19:05:07]

Yes, building the tree along with filtering should be faster and simpler, but
I'd like to have a separate patch for that.

+                var node = stack.pop();
+                idToNode[node.id] = node;
+                for (var i = 0; i < node.children.length; i++) {
+                    node.children[i].parent = node;
+                    stack.push(node.children[i]);
+                }
+            }
             for (var i = 0; i < this.samples.length; ++i) {
-                var node = this.nodeByIndex(i);
+                var node = idToNode[this.samples[i]];
                 while (isNativeNode(node))
                     node = node.parent;

[caseq, 2016/04/13 17:21:12]

so we actually care to know nearest non-native parent for each node id? I think
you can easily factor this into the  loop you introduced above in a more
efficient manner.

[alph, 2016/04/13 19:05:07]

I'm going to get rid of this function later. Added a TODO.

                 this.samples[i] = node.id;
             }
         }
-        processSubtree(this.profileHead);
+        processSubtree(head);
 
         /**
          * @param {!ProfilerAgent.CPUProfileNode} node
          * @return {boolean}
          */
         function isNativeNode(node)
         {
             return !!node.url && node.url.startsWith("native ");
         }
 
@@ skipping 30 matching lines @@
                     mergeChildren(node, child);
                 } else {
                     node.children.push(child);
                     child.parent = node;
                     processSubtree(child);
                 }
             }
         }
     },
 
-    _assignParentsInProfile: function()
+    /**
+     * @param {!ProfilerAgent.CPUProfileNode} head
+     * @return {!WebInspector.CPUProfileNode}
+     */
+    _translateProfileTree: function(head)
     {
-        var head = this.profileHead;
-        head.parent = null;
-        var nodesToTraverse = [ head ];
+        /**
+         * @param  {!ProfilerAgent.CPUProfileNode} node
+         * @return {number}
+         */
+        function treeHitCount(node)

[caseq, 2016/04/13 17:21:12]

nit: computeHitCountForSubtree()

[alph, 2016/04/13 19:05:07]

Done.

+        {
+            return node.children.reduce((acc, node) => acc + treeHitCount(node), node.hitCount);
+        }
+        this.totalHitCount = treeHitCount(head);
+        var sampleTime = (this.profileEndTime - this.profileStartTime) / this.totalHitCount;
+        var root = new WebInspector.CPUProfileNode(head, sampleTime);
+        // The stack contains pairs: (parentNode, sourceNode.children)

[caseq, 2016/04/13 17:21:12]

Please make it an array of objects, this way it's a bit confusing.

[alph, 2016/04/13 19:05:07]

Done.

+        var nodesToTraverse = [ root, head.children ];
         while (nodesToTraverse.length) {
-            var parent = nodesToTraverse.pop();
-            var children = parent.children;
-            var length = children.length;
-            for (var i = 0; i < length; ++i) {
-                var child = children[i];
-                child.parent = parent;
-                if (child.children.length)
-                    nodesToTraverse.push(child);
+            var children = nodesToTraverse.pop();
+            var parentNode = nodesToTraverse.pop();
+            for (var i = 0; i < children.length; ++i) {
+                var sourceNode = children[i];
+                var node = new WebInspector.CPUProfileNode(sourceNode, sampleTime);
+                parentNode.children.push(node);
+                if (sourceNode.children.length)
+                    nodesToTraverse.push(node, sourceNode.children);
             }
         }
+        return root;
     },
 
-    _assignDepthsInProfile: function()
+    /**
+     * @param {!WebInspector.ProfileNode} node
+     */
+    _assignTotalTimes: function(node)
     {
-        var head = this.profileHead;
-        head.depth = -1;
-        this.maxDepth = 0;
-        var nodesToTraverse = [ head ];
-        while (nodesToTraverse.length) {
-            var parent = nodesToTraverse.pop();
-            var depth = parent.depth + 1;
-            if (depth > this.maxDepth)
-                this.maxDepth = depth;
-            var children = parent.children;
-            var length = children.length;
-            for (var i = 0; i < length; ++i) {
-                var child = children[i];
-                child.depth = depth;
-                if (child.children.length)
-                    nodesToTraverse.push(child);
-            }
-        }
+        // TODO: get rid of this field in favor of this.total
+        node.totalTime = node.total;
+        node.children.forEach(this._assignTotalTimes, this);
     },
 
     _sortSamples: function()
     {
         var timestamps = this.timestamps;
         if (!timestamps)
             return;
         var samples = this.samples;
         var indices = timestamps.map((x, index) => index);
         indices.sort((a, b) => timestamps[a] - timestamps[b]);
@@ skipping 37 matching lines @@
             timestamps[i] /= 1000;
         var averageSample = (timestamps.peekLast() - timestamps[0]) / (timestamps.length - 1);
         // Add an extra timestamp used to calculate the last sample duration.
         this.timestamps.push(timestamps.peekLast() + averageSample);
         this.profileStartTime = timestamps[0];
         this.profileEndTime = timestamps.peekLast();
     },
 
     _buildIdToNodeMap: function()
     {
-        /** @type {!Object.<number, !ProfilerAgent.CPUProfileNode>} */
+        /** @type {!Object<number, !WebInspector.CPUProfileNode>} */
         this._idToNode = {};
         var idToNode = this._idToNode;
         var stack = [this.profileHead];
         while (stack.length) {
             var node = stack.pop();
             idToNode[node.id] = node;
             for (var i = 0; i < node.children.length; i++)
                 stack.push(node.children[i]);
         }
+    },
 
+    _extractMetaNodes: function()
+    {
         var topLevelNodes = this.profileHead.children;
         for (var i = 0; i < topLevelNodes.length && !(this.gcNode && this.programNode && this.idleNode); i++) {
             var node = topLevelNodes[i];
             if (node.functionName === "(garbage collector)")
                 this.gcNode = node;
             else if (node.functionName === "(program)")
                 this.programNode = node;
             else if (node.functionName === "(idle)")
                 this.idleNode = node;
         }
@@ skipping 21 matching lines @@
             var nextNodeId = samples[sampleIndex + 1];
             if (nodeId === programNodeId && !isSystemNode(prevNodeId) && !isSystemNode(nextNodeId)
                 && bottomNode(idToNode[prevNodeId]) === bottomNode(idToNode[nextNodeId])) {
                 samples[sampleIndex] = prevNodeId;
             }
             prevNodeId = nodeId;
             nodeId = nextNodeId;
         }
 
         /**
-         * @param {!ProfilerAgent.CPUProfileNode} node
-         * @return {!ProfilerAgent.CPUProfileNode}
+         * @param {!WebInspector.ProfileNode} node
+         * @return {!WebInspector.ProfileNode}
          */
         function bottomNode(node)
         {
             while (node.parent.parent)
                 node = node.parent;
             return node;
         }
 
         /**
          * @param {number} nodeId
          * @return {boolean}
          */
         function isSystemNode(nodeId)
         {
             return nodeId === programNodeId || nodeId === gcNodeId || nodeId === idleNodeId;
         }
     },
 
     /**
-     * @param {function(number, !ProfilerAgent.CPUProfileNode, number)} openFrameCallback
-     * @param {function(number, !ProfilerAgent.CPUProfileNode, number, number, number)} closeFrameCallback
+     * @param {function(number, !WebInspector.CPUProfileNode, number)} openFrameCallback
+     * @param {function(number, !WebInspector.CPUProfileNode, number, number, number)} closeFrameCallback
      * @param {number=} startTime
      * @param {number=} stopTime
      */
     forEachFrame: function(openFrameCallback, closeFrameCallback, startTime, stopTime)
     {
         if (!this.profileHead)
             return;
 
         startTime = startTime || 0;
         stopTime = stopTime || Infinity;
@@ skipping 50 matching lines @@
             while (node.depth > prevNode.depth) {
                 stackNodes.push(node);
                 node = node.parent;
             }
 
             // Go down to the LCA and close current intervals.
             while (prevNode !== node) {
                 var start = stackStartTimes[stackTop];
                 var duration = sampleTime - start;
                 stackChildrenDuration[stackTop - 1] += duration;
-                closeFrameCallback(prevNode.depth, prevNode, start, duration, duration - stackChildrenDuration[stackTop]);
+                closeFrameCallback(prevNode.depth, /** @type {!WebInspector.CPUProfileNode} */(prevNode), start, duration, duration - stackChildrenDuration[stackTop]);
                 --stackTop;
                 if (node.depth === prevNode.depth) {
                     stackNodes.push(node);
                     node = node.parent;
                 }
                 prevNode = prevNode.parent;
             }
 
             // Go up the nodes stack and open new intervals.
             while (stackNodes.length) {
@@ skipping 11 matching lines @@
             var duration = sampleTime - start;
             stackChildrenDuration[stackTop - 1] += duration;
             closeFrameCallback(gcParentNode.depth + 1, node, start, duration, duration - stackChildrenDuration[stackTop]);
             --stackTop;
         }
 
         for (var node = idToNode[prevId]; node.parent; node = node.parent) {
             var start = stackStartTimes[stackTop];
             var duration = sampleTime - start;
             stackChildrenDuration[stackTop - 1] += duration;
-            closeFrameCallback(node.depth, node, start, duration, duration - stackChildrenDuration[stackTop]);
+            closeFrameCallback(node.depth, /** @type {!WebInspector.CPUProfileNode} */(node), start, duration, duration - stackChildrenDuration[stackTop]);
             --stackTop;
         }
     },
 
     /**
      * @param {number} index
-     * @return {!ProfilerAgent.CPUProfileNode}
+     * @return {!WebInspector.CPUProfileNode}
      */
     nodeByIndex: function(index)
     {
         return this._idToNode[this.samples[index]];
-    }
+    },
 
+    __proto__: WebInspector.ProfileTreeModel.prototype
 }