Changeset 116677 in webkit

Timestamp:

May 10, 2012 12:52:05 PM (12 years ago)

Author:

Antti Koivisto

Message:

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):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• WebCore.exp.in (modified) (1 diff)
• dom/ContainerNode.h (modified) (1 diff)
• dom/Node.cpp (modified) (1 diff)
• dom/Node.h (modified) (2 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/WebCore/WebCore.exp.in

@@ -2100 +2100 @@
 __ZN7WebCore8Document22setAnimatingFullScreenEb
 __ZNK7WebCore8Document9domWindowEv
-__ZNK7WebCore4Node16traverseNextNodeEPKS0_
+__ZNK7WebCore4Node27traverseNextAncestorSiblingEv
 #endif
 

trunk/Source/WebCore/dom/ContainerNode.h

@@ -230 +230 @@
 }
 
+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;
 

trunk/Source/WebCore/dom/Node.cpp

@@ -1089 +1089 @@
 }
 
-Node* Node::traverseNextNode(const Node* stayWithin) 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();
+Node* Node::traverseNextAncestorSibling() const
+{
+    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
-{
-    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();
+Node* Node::traverseNextAncestorSibling(const Node* stayWithin) const
+{
+    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;
 }

trunk/Source/WebCore/dom/Node.h

@@ -432 +432 @@
     // 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
@@ -768 +770 @@
     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