Inline Node::traverseNextNode
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 May 2012 19:52:05 +0000 (19:52 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 May 2012 19:52:05 +0000 (19:52 +0000)
https://bugs.webkit.org/show_bug.cgi?id=85844

Reviewed by Ryosuke Niwa.

Inline traverseNextNode and traverseNextSibling to reduce entry/exit overhead and allow better code generation
for many hot loops.

In this version only the firstChild()/nextSibling() tests are inlined and the ancestor traversal is not.

Performance bots will tell if this was worthwhile.

* dom/ContainerNode.h:
(WebCore::Node::traverseNextNode):
(WebCore):
(WebCore::Node::traverseNextSibling):
* dom/Node.cpp:
(WebCore::Node::traverseNextAncestorSibling):
* dom/Node.h:
(Node):

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

Source/WebCore/ChangeLog
Source/WebCore/WebCore.exp.in
Source/WebCore/dom/ContainerNode.h
Source/WebCore/dom/Node.cpp
Source/WebCore/dom/Node.h

index bc1ab17..1a97827 100644 (file)
@@ -1,3 +1,26 @@
+2012-05-10  Antti Koivisto  <antti@apple.com>
+
+        Inline Node::traverseNextNode
+        https://bugs.webkit.org/show_bug.cgi?id=85844
+
+        Reviewed by Ryosuke Niwa.
+        
+        Inline traverseNextNode and traverseNextSibling to reduce entry/exit overhead and allow better code generation
+        for many hot loops.
+
+        In this version only the firstChild()/nextSibling() tests are inlined and the ancestor traversal is not.
+        
+        Performance bots will tell if this was worthwhile.
+
+        * dom/ContainerNode.h:
+        (WebCore::Node::traverseNextNode):
+        (WebCore):
+        (WebCore::Node::traverseNextSibling):
+        * dom/Node.cpp:
+        (WebCore::Node::traverseNextAncestorSibling):
+        * dom/Node.h:
+        (Node):
+
 2012-05-10  Tommy Widenflycht  <tommyw@google.com>
 
         MediaStream API: Fix MediaHints parsing
index 7bcbe15..8f67701 100644 (file)
@@ -2099,7 +2099,7 @@ __ZN7WebCore8Document25setFullScreenRendererSizeERKNS_7IntSizeE
 __ZN7WebCore8Document36setFullScreenRendererBackgroundColorENS_5ColorE
 __ZN7WebCore8Document22setAnimatingFullScreenEb
 __ZNK7WebCore8Document9domWindowEv
-__ZNK7WebCore4Node16traverseNextNodeEPKS0_
+__ZNK7WebCore4Node27traverseNextAncestorSiblingEv
 #endif
 
 __ZN7WebCore16ApplicationCache18diskUsageForOriginEPNS_14SecurityOriginE
index 233e034..1439b36 100644 (file)
@@ -229,6 +229,36 @@ inline Node* Node::highestAncestor() const
     return highest;
 }
 
+inline Node* Node::traverseNextSibling() const
+{
+    if (nextSibling())
+        return nextSibling();
+    return traverseNextAncestorSibling();
+}
+
+inline Node* Node::traverseNextNode() const
+{
+    if (firstChild())
+        return firstChild();
+    return traverseNextSibling();
+}
+
+inline Node* Node::traverseNextSibling(const Node* stayWithin) const
+{
+    if (this == stayWithin)
+        return 0;
+    if (nextSibling())
+        return nextSibling();
+    return traverseNextAncestorSibling(stayWithin);
+}
+
+inline Node* Node::traverseNextNode(const Node* stayWithin) const
+{
+    if (firstChild())
+        return firstChild();
+    return traverseNextSibling(stayWithin);
+}
+
 typedef Vector<RefPtr<Node>, 11> NodeVector;
 
 inline void getChildNodes(Node* node, NodeVector& nodes)
index 0a72487..6987beb 100644 (file)
@@ -1088,33 +1088,26 @@ void Node::removeCachedChildNodeList()
     rareData()->setChildNodeList(0);
 }
 
-Node* Node::traverseNextNode(const Node* stayWithin) const
+Node* Node::traverseNextAncestorSibling() const
 {
-    if (firstChild())
-        return firstChild();
-    if (this == stayWithin)
-        return 0;
-    if (nextSibling())
-        return nextSibling();
-    const Node *n = this;
-    while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
-        n = n->parentNode();
-    if (n)
-        return n->nextSibling();
+    ASSERT(!nextSibling());
+    for (const Node* node = parentNode(); node; node = node->parentNode()) {
+        if (node->nextSibling())
+            return node->nextSibling();
+    }
     return 0;
 }
 
-Node* Node::traverseNextSibling(const Node* stayWithin) const
+Node* Node::traverseNextAncestorSibling(const Node* stayWithin) const
 {
-    if (this == stayWithin)
-        return 0;
-    if (nextSibling())
-        return nextSibling();
-    const Node *n = this;
-    while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
-        n = n->parentNode();
-    if (n)
-        return n->nextSibling();
+    ASSERT(!nextSibling());
+    ASSERT(this != stayWithin);
+    for (const Node* node = parentNode(); node; node = node->parentNode()) {
+        if (node == stayWithin)
+            return 0;
+        if (node->nextSibling())
+            return node->nextSibling();
+    }
     return 0;
 }
 
index 875c82a..328c029 100644 (file)
@@ -431,10 +431,12 @@ public:
     // This uses the same order that tags appear in the source file. If the stayWithin
     // argument is non-null, the traversal will stop once the specified node is reached.
     // This can be used to restrict traversal to a particular sub-tree.
-    Node* traverseNextNode(const Node* stayWithin = 0) const;
+    Node* traverseNextNode() const;
+    Node* traverseNextNode(const Node* stayWithin) const;
 
     // Like traverseNextNode, but skips children and starts with the next sibling.
-    Node* traverseNextSibling(const Node* stayWithin = 0) const;
+    Node* traverseNextSibling() const;
+    Node* traverseNextSibling(const Node* stayWithin) const;
 
     // Does a reverse pre-order traversal to find the node that comes before the current one in document order
     Node* traversePreviousNode(const Node* stayWithin = 0) const;
@@ -767,6 +769,9 @@ private:
 
     Element* ancestorElement() const;
 
+    Node* traverseNextAncestorSibling() const;
+    Node* traverseNextAncestorSibling(const Node* stayWithin) const;
+
     // Use Node::parentNode as the consistent way of querying a parent node.
     // This method is made private to ensure a compiler error on call sites that
     // don't follow this rule.