Changeset 260762 in webkit

Timestamp:

Apr 27, 2020 9:47:24 AM (4 years ago)

Author:

Darin Adler

Message:

Improve performance of commonInclusiveAncestor for deeply nested nodes
​https://bugs.webkit.org/show_bug.cgi?id=211078

Reviewed by Antti Koivisto.

• dom/Node.cpp:

(WebCore::depth): Added.
(WebCore::commonInclusiveAncestor): Replaced implementation that walks the
parent chain of the second node repeatedly with one that walks the parent
chain of each node twice.

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• dom/Node.cpp (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2020-04-27  Darin Adler  <darin@apple.com>
+
+        Improve performance of commonInclusiveAncestor for deeply nested nodes
+        https://bugs.webkit.org/show_bug.cgi?id=211078
+
+        Reviewed by Antti Koivisto.
+
+        * dom/Node.cpp:
+        (WebCore::depth): Added.
+        (WebCore::commonInclusiveAncestor): Replaced implementation that walks the
+        parent chain of the second node repeatedly with one that walks the parent
+        chain of each node twice.
+
 2020-04-27  Daniel Bates  <dabates@apple.com>
 

trunk/Source/WebCore/dom/Node.cpp

@@ -2613 +2613 @@
 }
 
+static size_t depth(Node& node)
+{
+    size_t depth = 0;
+    auto ancestor = &node;
+    while ((ancestor = ancestor->parentNode()))
+        ++depth;
+    return depth;
+}
+
 RefPtr<Node> commonInclusiveAncestor(Node& a, Node& b)
 {
-    for (auto ancestorA = &a; ancestorA; ancestorA = ancestorA->parentNode()) {
-        for (auto ancestorB = &b; ancestorB; ancestorB = ancestorB->parentNode()) {
-            if (ancestorA == ancestorB)
-                return ancestorA;
-        }
-    }
-    return nullptr;
+    // This first check isn't needed for correctness, but it is cheap and likely to be
+    // common enough to be worth optimizing so we don't have to walk to the root.
+    if (&a == &b)
+        return &a;
+    auto [depthA, depthB] = std::make_tuple(depth(a), depth(b));
+    auto [x, y, difference] = depthA > depthB
+        ? std::make_tuple(&a, &b, depthA - depthB)
+        : std::make_tuple(&b, &a, depthB - depthA);
+    for (decltype(difference) i = 0; i < difference; ++i)
+        x = x->parentNode();
+    while (x != y) {
+        x = x->parentNode();
+        y = y->parentNode();
+    }
+    return x;
 }