Changeset 244308 in webkit

Timestamp:

Apr 15, 2019 4:48:57 PM (5 years ago)

Author:

Devin Rousso

Message:

Web Inspector: Heap: don't use recursion when calculating root paths
​https://bugs.webkit.org/show_bug.cgi?id=196890
<rdar://problem/49870751>

Reviewed by Joseph Pecoraro.

• UserInterface/Workers/HeapSnapshot/HeapSnapshot.js:

(HeapSnapshot.prototype.shortestGCRootPath):
(HeapSnapshot.prototype._determineGCRootPaths):
(HeapSnapshot.prototype._gcRootPathes.visitNode): Deleted.
(HeapSnapshot.prototype._gcRootPathes): Deleted.

Location:

trunk/Source/WebInspectorUI

Files:

• ChangeLog (modified) (1 diff)
• UserInterface/Workers/HeapSnapshot/HeapSnapshot.js (modified) (4 diffs)

trunk/Source/WebInspectorUI/ChangeLog

@@ +1 @@
+2019-04-15  Devin Rousso  <drousso@apple.com>
+
+        Web Inspector: Heap: don't use recursion when calculating root paths
+        https://bugs.webkit.org/show_bug.cgi?id=196890
+        <rdar://problem/49870751>
+
+        Reviewed by Joseph Pecoraro.
+
+        * UserInterface/Workers/HeapSnapshot/HeapSnapshot.js:
+        (HeapSnapshot.prototype.shortestGCRootPath):
+        (HeapSnapshot.prototype._determineGCRootPaths):
+        (HeapSnapshot.prototype._gcRootPathes.visitNode): Deleted.
+        (HeapSnapshot.prototype._gcRootPathes): Deleted.
+
 2019-04-15  Joseph Pecoraro  <pecoraro@apple.com>
 

trunk/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshot.js

@@ -279 +279 @@
         // node is either a gcRoot or only reachable via Internal nodes.
 
-        let paths = this._gcRootPathes(nodeIdentifier);
+        let paths = this._determineGCRootPaths(nodeIdentifier);
         if (!paths.length)
             return [];
@@ -735 +735 @@
     }
 
-    _gcRootPathes(nodeIdentifier)
+    _determineGCRootPaths(nodeIdentifier)
     {
         let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
@@ -744 +744 @@
         // FIXME: Array push/pop can affect performance here, but in practice it hasn't been an issue.
 
-        let paths = [];
-        let currentPath = [];
+        let gcRootPaths = [];
         let visited = new Uint8Array(this._nodeCount);
 
-        function visitNode(nodeOrdinal)
-        {
+        let pathsBeingProcessed = [
+            {
+                currentPath: [],
+                nodeOrdinal: targetNodeOrdinal,
+            },
+        ];
+        for (let i = 0; i < pathsBeingProcessed.length; ++i) {
+            let {currentPath, nodeOrdinal} = pathsBeingProcessed[i];
+
+            // Rather than use `Array.prototype.unshift`, which may be very expensive, keep track of
+            // the "current" position as `i` and "delete" the values already processed by clearing
+            // the value at that index.
+            pathsBeingProcessed[i] = undefined;
+
             if (this._nodeOrdinalIsGCRoot[nodeOrdinal]) {
                 let fullPath = currentPath.slice();
                 let nodeIndex = nodeOrdinal * this._nodeFieldCount;
                 fullPath.push({node: nodeIndex});
-                paths.push(fullPath);
-                return;
+                gcRootPaths.push(fullPath);
+                continue;
             }
 
             if (visited[nodeOrdinal])
-                return;
+                continue;
+
             visited[nodeOrdinal] = 1;
 
@@ -776 +788 @@
                     continue;
 
-                let edgeIndex = this._incomingEdges[incomingEdgeIndex];
-                currentPath.push({edge: edgeIndex});
-                visitNode.call(this, fromNodeOrdinal);
-                currentPath.pop();
+                let newPath = currentPath.slice();
+                newPath.push({edge: this._incomingEdges[incomingEdgeIndex]});
+                pathsBeingProcessed.push({currentPath: newPath, nodeOrdinal: fromNodeOrdinal});
             }
-
-            currentPath.pop();
-        }
-
-        visitNode.call(this, targetNodeOrdinal);
-
-        return paths;
+        }
+
+        return gcRootPaths;
     }
 };