+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.
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)
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();
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;