2009-11-18 Maciej Stachowiak <mjs@apple.com>

        Reviewed by Oliver Hunt.

        Fix REGRESSION (r47022): Performance of DocumentFragment.appendChild is 1000x slower sometimes
        https://bugs.webkit.org/show_bug.cgi?id=31237

        Also speeds up Dromaeo DOM Core tests by 1.31x.

        * bindings/js/JSNodeCustom.cpp:
        (WebCore::JSNode::markChildren): Change marking algorithm to avoid O(N^2) behavior. The subtree
        mark bit was no longer effective; instead I changed things so only a node that has no ancestors
        with wrappers would do marking; there should be only one in the typical case (the root of the
        detached subtree).
        * dom/Node.cpp:
        (WebCore::Node::Node): Remove now useless m_inSubtreeMark bit and related functions.
        * dom/Node.h: ditto

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

diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
index 5ecac83ab1143211b7c84ad7aa1b4f2b4857b015..db73bf6337e8fae9ebae4b268d46871c5f49da4d 100644 (file)
--- a/WebCore/ChangeLog
+++ b/WebCore/ChangeLog
@@ -1,3 +1,21 @@
+2009-11-18  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Fix REGRESSION (r47022): Performance of DocumentFragment.appendChild is 1000x slower sometimes
+        https://bugs.webkit.org/show_bug.cgi?id=31237
+        
+        Also speeds up Dromaeo DOM Core tests by 1.31x.
+
+        * bindings/js/JSNodeCustom.cpp:
+        (WebCore::JSNode::markChildren): Change marking algorithm to avoid O(N^2) behavior. The subtree
+        mark bit was no longer effective; instead I changed things so only a node that has no ancestors
+        with wrappers would do marking; there should be only one in the typical case (the root of the
+        detached subtree).
+        * dom/Node.cpp:
+        (WebCore::Node::Node): Remove now useless m_inSubtreeMark bit and related functions.
+        * dom/Node.h: ditto
+
 2009-11-18  Darin Adler  <darin@apple.com>
 
         Reviewed by Sam Weinig.

diff --git a/WebCore/bindings/js/JSNodeCustom.cpp b/WebCore/bindings/js/JSNodeCustom.cpp
index 8f513f27e27ac513af8000189d61b56047a5cd0e..9ea244a4ad1d33ec9faa300d41ed15270ed38200 100644 (file)
--- a/WebCore/bindings/js/JSNodeCustom.cpp
+++ b/WebCore/bindings/js/JSNodeCustom.cpp
@@ -148,22 +148,28 @@ void JSNode::markChildren(MarkStack& markStack)
         return;
     }
 
-    // This is a node outside the document, so find the root of the tree it is in,
-    // and start marking from there.
+    // This is a node outside the document.
+    // Find the the root, and the highest ancestor with a wrapper.
     Node* root = node;
-    for (Node* current = m_impl.get(); current; current = current->parentNode())
+    Node* outermostNodeWithWrapper = node;
+    for (Node* current = m_impl.get(); current; current = current->parentNode()) {
         root = current;
+        if (getCachedDOMNodeWrapper(current->document(), current))
+            outermostNodeWithWrapper = current;
+    }
 
-    // Nodes in a subtree are marked by the tree's root, so, if the root is already
-    // marking the tree, we don't need to explicitly mark any other nodes.
-    if (root->inSubtreeMark())
+    // Only nodes that have no ancestors with wrappers mark the subtree. In the common
+    // case, the root of the detached subtree has a wrapper, so the tree will only
+    // get marked once. Nodes that aren't outermost need to mark the outermost
+    // in case it is otherwise unreachable.
+    if (node != outermostNodeWithWrapper) {
+        markDOMNodeWrapper(markStack, m_impl->document(), outermostNodeWithWrapper);
         return;
+    }
 
     // Mark the whole tree subtree.
-    root->setInSubtreeMark(true);
     for (Node* nodeToMark = root; nodeToMark; nodeToMark = nodeToMark->traverseNextNode())
         markDOMNodeWrapper(markStack, m_impl->document(), nodeToMark);
-    root->setInSubtreeMark(false);
 }
 
 static ALWAYS_INLINE JSValue createWrapper(ExecState* exec, JSDOMGlobalObject* globalObject, Node* node)

diff --git a/WebCore/dom/Node.cpp b/WebCore/dom/Node.cpp
index d3d501b450ceac7f2c89d3f035d00544536a87c9..a979d8ed29472183f3e7fed6a3907392da850890 100644 (file)
--- a/WebCore/dom/Node.cpp
+++ b/WebCore/dom/Node.cpp
@@ -410,7 +410,6 @@ Node::Node(Document* document, ConstructionType type)
     , m_hovered(false)
     , m_inActiveChain(false)
     , m_inDetach(false)
-    , m_inSubtreeMark(false)
     , m_hasRareData(false)
     , m_isElement(isElement(type))
     , m_isContainer(isContainer(type))

diff --git a/WebCore/dom/Node.h b/WebCore/dom/Node.h
index 35be6d301f4a1b837e57b66ff731a2fd6020b3ee..4c9985ed1b92703fd0d2af9c4b38e15c5c94b7cf 100644 (file)
--- a/WebCore/dom/Node.h
+++ b/WebCore/dom/Node.h
@@ -289,9 +289,6 @@ public:
     void setNeedsStyleRecalc(StyleChangeType changeType = FullStyleChange);
     void setIsLink(bool b = true) { m_isLink = b; }
 
-    bool inSubtreeMark() const { return m_inSubtreeMark; }
-    void setInSubtreeMark(bool b = true) { m_inSubtreeMark = b; }
-
     void lazyAttach();
     virtual bool canLazyAttach();
 
@@ -623,7 +620,6 @@ private:
     bool m_hovered : 1;
     bool m_inActiveChain : 1;
     bool m_inDetach : 1;
-    bool m_inSubtreeMark : 1;
     bool m_hasRareData : 1;
     const bool m_isElement : 1;
     const bool m_isContainer : 1;