Changeset 101967 in webkit

Timestamp:

Dec 4, 2011 1:52:56 PM (12 years ago)

Author:

rniwa@webkit.org

Message:

HIERARCHY_REQUEST_ERR check in checkAcceptChild should be optimized for newChild without children
​https://bugs.webkit.org/show_bug.cgi?id=73737

Reviewed by Darin Adler.

It turned out that 50-70% of nodes inserted by DOM APIs such as insertBefore and appendChild
don't have any descendent nodes. Optimize isDescendantOf which is used by checkAcceptChild for this case.
On a test case attached on the bug, we see a 40% improvement.

Also optimize for cases where either new child or new parent but not both are in document as suggested
by Erik Arvidsson. This appears to happen about 40-70% of the time, and the symmetric difference between
the two cases is about 50% so it's worth implementing both optimizations.

Unfortunately no tests because we still have a O(n) algorithm somewhere.

• dom/Node.cpp:

(WebCore::Node::isDescendantOf):
(WebCore::Node::contains):

Location:

trunk/Source/WebCore

Files:

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

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-12-04  Ryosuke Niwa  <rniwa@webkit.org>
+
+        HIERARCHY_REQUEST_ERR check in checkAcceptChild should be optimized for newChild without children
+        https://bugs.webkit.org/show_bug.cgi?id=73737
+
+        Reviewed by Darin Adler.
+
+        It turned out that 50-70% of nodes inserted by DOM APIs such as insertBefore and appendChild
+        don't have any descendent nodes. Optimize isDescendantOf which is used by checkAcceptChild for this case.
+        On a test case attached on the bug, we see a 40% improvement.
+
+        Also optimize for cases where either new child or new parent but not both are in document as suggested
+        by Erik Arvidsson. This appears to happen about 40-70% of the time, and the symmetric difference between
+        the two cases is about 50% so it's worth implementing both optimizations.
+
+        Unfortunately no tests because we still have a O(n) algorithm somewhere.
+
+        * dom/Node.cpp:
+        (WebCore::Node::isDescendantOf):
+        (WebCore::Node::contains):
+
 2011-12-04  Andreas Kling  <kling@webkit.org>
 

trunk/Source/WebCore/dom/Node.cpp

@@ -1349 +1349 @@
 {
     // Return true if other is an ancestor of this, otherwise false
-    if (!other)
-        return false;
+    if (!other || !other->firstChild() || inDocument() != other->inDocument())
+        return false;
+    if (other == other->document())
+        return document() == other && this != document() && inDocument();
     for (const ContainerNode* n = parentNode(); n; n = n->parentNode()) {
         if (n == other)
@@ -1362 +1364 @@
     if (!node)
         return false;
-    if (document() == this)
-        return node->document() == this && node->inDocument();
     return this == node || node->isDescendantOf(this);
 }