Web Inspector: Heap: don't use recursion when calculating root paths
authordrousso@apple.com <drousso@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Apr 2019 23:48:57 +0000 (23:48 +0000)
committerdrousso@apple.com <drousso@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Apr 2019 23:48:57 +0000 (23:48 +0000)
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.

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

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

index cdc1ab5..41bf6ae 100644 (file)
@@ -1,3 +1,17 @@
+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>
 
         Web Inspector: SameSite parsing should be stricter
index 16b4504..7fc29c2 100644 (file)
@@ -278,7 +278,7 @@ HeapSnapshot = class HeapSnapshot
         // Internal nodes are avoided, so if the path is empty this
         // 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 [];
 
@@ -734,7 +734,7 @@ HeapSnapshot = class HeapSnapshot
             || className === "GlobalObject";
     }
 
-    _gcRootPathes(nodeIdentifier)
+    _determineGCRootPaths(nodeIdentifier)
     {
         let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
 
@@ -743,22 +743,34 @@ HeapSnapshot = class HeapSnapshot
 
         // 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;
 
             let nodeIndex = nodeOrdinal * this._nodeFieldCount;
@@ -775,18 +787,13 @@ HeapSnapshot = class HeapSnapshot
                 if (fromNodeIsInternal)
                     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;
     }
 };