Changeset 51162 in webkit


Ignore:
Timestamp:
Nov 18, 2009 6:13:20 PM (14 years ago)
Author:
mjs@apple.com
Message:

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(N2) 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
Location:
trunk/WebCore
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/WebCore/ChangeLog

    r51161 r51162  
     12009-11-18  Maciej Stachowiak  <mjs@apple.com>
     2
     3        Reviewed by Oliver Hunt.
     4
     5        Fix REGRESSION (r47022): Performance of DocumentFragment.appendChild is 1000x slower sometimes
     6        https://bugs.webkit.org/show_bug.cgi?id=31237
     7       
     8        Also speeds up Dromaeo DOM Core tests by 1.31x.
     9
     10        * bindings/js/JSNodeCustom.cpp:
     11        (WebCore::JSNode::markChildren): Change marking algorithm to avoid O(N^2) behavior. The subtree
     12        mark bit was no longer effective; instead I changed things so only a node that has no ancestors
     13        with wrappers would do marking; there should be only one in the typical case (the root of the
     14        detached subtree).
     15        * dom/Node.cpp:
     16        (WebCore::Node::Node): Remove now useless m_inSubtreeMark bit and related functions.
     17        * dom/Node.h: ditto
     18
    1192009-11-18  Darin Adler  <darin@apple.com>
    220
  • trunk/WebCore/bindings/js/JSNodeCustom.cpp

    r50850 r51162  
    149149    }
    150150
    151     // This is a node outside the document, so find the root of the tree it is in,
    152     // and start marking from there.
     151    // This is a node outside the document.
     152    // Find the the root, and the highest ancestor with a wrapper.
    153153    Node* root = node;
    154     for (Node* current = m_impl.get(); current; current = current->parentNode())
     154    Node* outermostNodeWithWrapper = node;
     155    for (Node* current = m_impl.get(); current; current = current->parentNode()) {
    155156        root = current;
    156 
    157     // Nodes in a subtree are marked by the tree's root, so, if the root is already
    158     // marking the tree, we don't need to explicitly mark any other nodes.
    159     if (root->inSubtreeMark())
     157        if (getCachedDOMNodeWrapper(current->document(), current))
     158            outermostNodeWithWrapper = current;
     159    }
     160
     161    // Only nodes that have no ancestors with wrappers mark the subtree. In the common
     162    // case, the root of the detached subtree has a wrapper, so the tree will only
     163    // get marked once. Nodes that aren't outermost need to mark the outermost
     164    // in case it is otherwise unreachable.
     165    if (node != outermostNodeWithWrapper) {
     166        markDOMNodeWrapper(markStack, m_impl->document(), outermostNodeWithWrapper);
    160167        return;
     168    }
    161169
    162170    // Mark the whole tree subtree.
    163     root->setInSubtreeMark(true);
    164171    for (Node* nodeToMark = root; nodeToMark; nodeToMark = nodeToMark->traverseNextNode())
    165172        markDOMNodeWrapper(markStack, m_impl->document(), nodeToMark);
    166     root->setInSubtreeMark(false);
    167173}
    168174
  • trunk/WebCore/dom/Node.cpp

    r50523 r51162  
    411411    , m_inActiveChain(false)
    412412    , m_inDetach(false)
    413     , m_inSubtreeMark(false)
    414413    , m_hasRareData(false)
    415414    , m_isElement(isElement(type))
  • trunk/WebCore/dom/Node.h

    r48809 r51162  
    290290    void setIsLink(bool b = true) { m_isLink = b; }
    291291
    292     bool inSubtreeMark() const { return m_inSubtreeMark; }
    293     void setInSubtreeMark(bool b = true) { m_inSubtreeMark = b; }
    294 
    295292    void lazyAttach();
    296293    virtual bool canLazyAttach();
     
    624621    bool m_inActiveChain : 1;
    625622    bool m_inDetach : 1;
    626     bool m_inSubtreeMark : 1;
    627623    bool m_hasRareData : 1;
    628624    const bool m_isElement : 1;
Note: See TracChangeset for help on using the changeset viewer.