Changeset 121106 in webkit


Ignore:
Timestamp:
Jun 23, 2012 8:13:19 PM (12 years ago)
Author:
rniwa@webkit.org
Message:

Inserting nodes is slow due to Node::notifyNodeListsAttributeChanged (20%+)
​https://bugs.webkit.org/show_bug.cgi?id=73853

Reviewed by Anders Carlsson and Ojan Vafai.

Invalidate all node lists at document level to avoid having to walk up the DOM tree in the invalidation.
In particular, this makes appending node O(1) with respect to the depth of the tree in common cases when
we have node lists somewhere in the tree scope.

We now invalidate more node lists than we used to but it shouldn't matter much in practice because
most websites don't add or remove nodes or modify relevant attributes while iterating through node lists.
The change would also register each node list to document thereby consuming one extra pointer, however,
this should not have a significant memory impact given we used to do it unintentionally until I fixed it in
r110797 three months ago.

Also, RadioNodeList and LabelsNodeList had always been invalidated at document level so this refactoring
also allows us to move calls to registerDynamicSubtreeNodeList and unregisterDynamicSubtreeNodeList in
those node lists to DynamicSubtreeNodeList, and even delete NodeListsNodeData::invalidateCaches().

In addition, removed m_numNodeListCaches from TreeScope since it was only used to avoid walking up
the ancestors in invalidateNodeListsCacheAfterAttributeChanged and invalidateNodeListsCacheAfterChildrenChanged
but we don't walk up the ancestors any more. Also note that m_listsInvalidatedAtDocument tells us exactly
how many node lists are present for each document.

  • dom/Document.cpp:

(WebCore::Document::clearNodeListCaches): Optionally takes a qualified attribute name so that we don't
have to invalidate tag node lists when only attributes are modified.

  • dom/Document.h:

(Document):

  • dom/DynamicNodeList.cpp:

(WebCore::DynamicSubtreeNodeList::~DynamicSubtreeNodeList): Calls unregisterDynamicSubtreeNodeList.

  • dom/DynamicNodeList.h:

(WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList): Calls registerDynamicSubtreeNodeList.

  • dom/Node.cpp:

(WebCore::Node::clearRareData):
(WebCore::Node::invalidateNodeListsCacheAfterAttributeChanged): No longer walks up the tree to invalidate
node list caches. All invalidations are done in Document::clearNodeListCaches.
(WebCore::Node::invalidateNodeListsCacheAfterChildrenChanged): Ditto.
(WebCore::Node::getElementsByTagName):
(WebCore::Node::getElementsByTagNameNS):
(WebCore::Node::getElementsByName):
(WebCore::Node::getElementsByClassName):
(WebCore::Node::radioNodeList):
(WebCore):
(WebCore::NodeRareData::createNodeLists):

  • dom/NodeRareData.h:

(NodeListsNodeData):
(WebCore::NodeListsNodeData::adoptTreeScope): Invalidate node list caches while registering and
unregistering node lists from old and new documents respectively now that invalidateCaches() has been
(WebCore::NodeRareData::ensureNodeLists):
(NodeRareData):

  • dom/TreeScope.cpp:

(WebCore::TreeScope::TreeScope):

  • dom/TreeScope.h:

(TreeScope):

  • dom/TreeScopeAdopter.cpp:

(WebCore::TreeScopeAdopter::moveTreeToNewScope):

  • html/LabelableElement.cpp:

(WebCore::LabelableElement::labels):

  • html/LabelsNodeList.cpp:

(WebCore::LabelsNodeList::LabelsNodeList):
(WebCore::LabelsNodeList::~LabelsNodeList):

  • html/RadioNodeList.cpp:

(WebCore::RadioNodeList::RadioNodeList):
(WebCore::RadioNodeList::~RadioNodeList):

Location:
trunk/Source/WebCore
Files:
13 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r121105 r121106  
     12012-06-23  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        Inserting nodes is slow due to Node::notifyNodeListsAttributeChanged (20%+)
     4        https://bugs.webkit.org/show_bug.cgi?id=73853
     5
     6        Reviewed by Anders Carlsson and Ojan Vafai.
     7
     8        Invalidate all node lists at document level to avoid having to walk up the DOM tree in the invalidation.
     9        In particular, this makes appending node O(1) with respect to the depth of the tree in common cases when
     10        we have node lists somewhere in the tree scope.
     11
     12        We now invalidate more node lists than we used to but it shouldn't matter much in practice because
     13        most websites don't add or remove nodes or modify relevant attributes while iterating through node lists.
     14        The change would also register each node list to document thereby consuming one extra pointer, however,
     15        this should not have a significant memory impact given we used to do it unintentionally until I fixed it in
     16        r110797 three months ago.
     17
     18        Also, RadioNodeList and LabelsNodeList had always been invalidated at document level so this refactoring
     19        also allows us to move calls to registerDynamicSubtreeNodeList and unregisterDynamicSubtreeNodeList in
     20        those node lists to DynamicSubtreeNodeList, and even delete NodeListsNodeData::invalidateCaches().
     21
     22        In addition, removed m_numNodeListCaches from TreeScope since it was only used to avoid walking up
     23        the ancestors in invalidateNodeListsCacheAfterAttributeChanged and invalidateNodeListsCacheAfterChildrenChanged
     24        but we don't walk up the ancestors any more. Also note that m_listsInvalidatedAtDocument tells us exactly
     25        how many node lists are present for each document.
     26
     27        * dom/Document.cpp:
     28        (WebCore::Document::clearNodeListCaches): Optionally takes a qualified attribute name so that we don't
     29        have to invalidate tag node lists when only attributes are modified.
     30        * dom/Document.h:
     31        (Document):
     32        * dom/DynamicNodeList.cpp:
     33        (WebCore::DynamicSubtreeNodeList::~DynamicSubtreeNodeList): Calls unregisterDynamicSubtreeNodeList.
     34        * dom/DynamicNodeList.h:
     35        (WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList): Calls registerDynamicSubtreeNodeList.
     36        * dom/Node.cpp:
     37        (WebCore::Node::clearRareData):
     38        (WebCore::Node::invalidateNodeListsCacheAfterAttributeChanged): No longer walks up the tree to invalidate
     39        node list caches. All invalidations are done in Document::clearNodeListCaches.
     40        (WebCore::Node::invalidateNodeListsCacheAfterChildrenChanged): Ditto.
     41        (WebCore::Node::getElementsByTagName):
     42        (WebCore::Node::getElementsByTagNameNS):
     43        (WebCore::Node::getElementsByName):
     44        (WebCore::Node::getElementsByClassName):
     45        (WebCore::Node::radioNodeList):
     46        (WebCore):
     47        (WebCore::NodeRareData::createNodeLists):
     48        * dom/NodeRareData.h:
     49        (NodeListsNodeData):
     50        (WebCore::NodeListsNodeData::adoptTreeScope): Invalidate node list caches while registering and
     51        unregistering node lists from old and new documents respectively now that invalidateCaches() has been
     52        (WebCore::NodeRareData::ensureNodeLists):
     53        (NodeRareData):
     54        * dom/TreeScope.cpp:
     55        (WebCore::TreeScope::TreeScope):
     56        * dom/TreeScope.h:
     57        (TreeScope):
     58        * dom/TreeScopeAdopter.cpp:
     59        (WebCore::TreeScopeAdopter::moveTreeToNewScope):
     60        * html/LabelableElement.cpp:
     61        (WebCore::LabelableElement::labels):
     62        * html/LabelsNodeList.cpp:
     63        (WebCore::LabelsNodeList::LabelsNodeList):
     64        (WebCore::LabelsNodeList::~LabelsNodeList):
     65        * html/RadioNodeList.cpp:
     66        (WebCore::RadioNodeList::RadioNodeList):
     67        (WebCore::RadioNodeList::~RadioNodeList):
     68
    1692012-06-23  Ryosuke Niwa  <rniwa@webkit.org>
    270

  • trunk/Source/WebCore/dom/Document.cpp

    r120979 r121106  
    38733873}
    38743874
    3875 void Document::clearNodeListCaches()
    3876 {
     3875void Document::clearNodeListCaches(const QualifiedName* attrName)
     3876{
     3877    // FIXME: Only invalidate caches of node lists that match attrName.
    38773878    HashSet<DynamicSubtreeNodeList*>::iterator end = m_listsInvalidatedAtDocument.end();
    3878     for (HashSet<DynamicSubtreeNodeList*>::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it)
    3879         (*it)->invalidateCache();
     3879    for (HashSet<DynamicSubtreeNodeList*>::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it) {
     3880        if (!attrName || (*it)->shouldInvalidateOnAttributeChange())
     3881            (*it)->invalidateCache();
     3882    }
    38803883}
    38813884

  • trunk/Source/WebCore/dom/Document.h

    r120979 r121106  
    715715    void registerDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
    716716    void unregisterDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
    717     void clearNodeListCaches();
     717    void clearNodeListCaches(const QualifiedName* attrName);
    718718
    719719    void attachNodeIterator(NodeIterator*);

  • trunk/Source/WebCore/dom/DynamicNodeList.cpp

    r121003 r121106  
    3131DynamicSubtreeNodeList::~DynamicSubtreeNodeList()
    3232{
     33    document()->unregisterDynamicSubtreeNodeList(this);
    3334}
    3435

  • trunk/Source/WebCore/dom/DynamicNodeList.h

    r121003 r121106  
    124124    DynamicSubtreeNodeList(PassRefPtr<Node> node, RootType rootType = RootedAtNode, InvalidationType invalidationType = AlwaysInvalidate)
    125125        : DynamicNodeList(node, rootType, invalidationType)
    126     { }
     126    {
     127        document()->registerDynamicSubtreeNodeList(this);
     128    }
    127129
    128130private:

  • trunk/Source/WebCore/dom/Node.cpp

    r121022 r121106  
    483483{
    484484    ASSERT(hasRareData());
    485     if (treeScope() && rareData()->nodeLists())
    486         treeScope()->removeNodeListCache();
    487 
    488485#if ENABLE(MUTATION_OBSERVERS)
    489486    ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
    … …  
    952949
    953950    // FIXME: Move the list of attributes each NodeList type cares about to be a static on the
    954     // appropriate NodeList class. Then use those lists here and in invalidateCachesThatDependOnAttributes
     951    // appropriate NodeList class. Then use those lists here and in clearNodeListCaches
    955952    // to only invalidate the cache types that depend on the attribute that changed.
    956953    // FIXME: Keep track of when we have no caches of a given type so that we can avoid the for-loop
    957     // below even if a related attribute changed (e.g. if we have no RadioNodeLists, we don't need
     954    // in clearNodeListCaches even if a related attribute changed (e.g. if we have no RadioNodeLists, we don't need
    958955    // to invalidate any caches when id attributes change.)
    959956    if (attrName != classAttr
    … …  
    968965        return;
    969966
    970     document()->clearNodeListCaches();
    971 
    972     if (!treeScope()->hasNodeListCaches())
    973         return;
    974 
    975     for (Node* node = this; node; node = node->parentNode()) {
    976         ASSERT(this == node || !node->isAttributeNode());
    977         if (!node->hasRareData())
    978             continue;
    979         NodeRareData* data = node->rareData();
    980         if (!data->nodeLists())
    981             continue;
    982 
    983         data->nodeLists()->invalidateCaches(&attrName);
    984     }
     967    document()->clearNodeListCaches(&attrName);
    985968}
    986969
    … …  
    990973        rareData()->clearChildNodeListCache();
    991974
    992     document()->clearNodeListCaches();
    993 
    994     if (!treeScope()->hasNodeListCaches())
    995         return;
    996 
    997     for (Node* node = this; node; node = node->parentNode()) {
    998         if (!node->hasRareData())
    999             continue;
    1000         NodeRareData* data = node->rareData();
    1001         if (!data->nodeLists())
    1002             continue;
    1003 
    1004         data->nodeLists()->invalidateCaches();
    1005     }
     975    document()->clearNodeListCaches(0);
    1006976}
    1007977
    … …  
    15491519
    15501520    if (document()->isHTMLDocument())
    1551         return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<HTMLTagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
    1552     return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<TagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
     1521        return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<HTMLTagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
     1522    return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<TagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
    15531523}
    15541524
    … …  
    15611531        return getElementsByTagName(localName);
    15621532
    1563     return ensureRareData()->ensureNodeLists(this)->addCacheWithQualifiedName(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
     1533    return ensureRareData()->ensureNodeLists()->addCacheWithQualifiedName(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
    15641534}
    15651535
    15661536PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
    15671537{
    1568     return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<NameNodeList>(this, DynamicNodeList::NameNodeListType, elementName);
     1538    return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<NameNodeList>(this, DynamicNodeList::NameNodeListType, elementName);
    15691539}
    15701540
    15711541PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
    15721542{
    1573     return ensureRareData()->ensureNodeLists(this)->addCacheWithName<ClassNodeList>(this, DynamicNodeList::ClassNodeListType, classNames);
     1543    return ensureRareData()->ensureNodeLists()->addCacheWithName<ClassNodeList>(this, DynamicNodeList::ClassNodeListType, classNames);
    15741544}
    15751545
    … …  
    15771547{
    15781548    ASSERT(hasTagName(formTag) || hasTagName(fieldsetTag));
    1579     return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<RadioNodeList>(this, DynamicNodeList::RadioNodeListType, name);
     1549    return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<RadioNodeList>(this, DynamicNodeList::RadioNodeListType, name);
    15801550}
    15811551
    … …  
    22392209// --------
    22402210
    2241 void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
    2242 {
    2243     NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
    2244     for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
    2245         if (!attrName || it->second->shouldInvalidateOnAttributeChange())
    2246             it->second->invalidateCache();
    2247     }
    2248 
    2249     NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
    2250     for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
    2251         if (!attrName || it->second->shouldInvalidateOnAttributeChange())
    2252             it->second->invalidateCache();
    2253     }
    2254 
    2255     if (!attrName)
    2256         return;
    2257 
    2258     TagNodeListCacheNS::iterator tagCacheEnd = m_tagNodeListCacheNS.end();
    2259     for (TagNodeListCacheNS::iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEnd; ++it)
    2260         it->second->invalidateCache();
    2261 }
    2262 
    22632211void Node::getSubresourceURLs(ListHashSet<KURL>& urls) const
    22642212{
    … …  
    27552703#endif
    27562704
    2757 void NodeRareData::createNodeLists(Node* node)
    2758 {
    2759     ASSERT(node);
     2705void NodeRareData::createNodeLists()
     2706{
    27602707    setNodeLists(NodeListsNodeData::create());
    2761     if (TreeScope* treeScope = node->treeScope())
    2762         treeScope->addNodeListCache();
    27632708}
    27642709

  • trunk/Source/WebCore/dom/NodeRareData.h

    r121105 r121106  
    124124    }
    125125
    126     void invalidateCaches(const QualifiedName* attrName = 0);
    127126    bool isEmpty() const
    128127    {
    … …  
    130129    }
    131130
    132     void adoptTreeScope(TreeScope* oldTreeScope, TreeScope* newTreeScope, Document* oldDocument, Document* newDocument)
    133     {
    134         invalidateCaches();
    135 
    136         if (oldDocument != newDocument) {
    137             NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
    138             for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
    139                 DynamicSubtreeNodeList* list = it->second;
    140                 if (list->isRootedAtDocument()) {
    141                     oldDocument->unregisterDynamicSubtreeNodeList(list);
    142                     newDocument->registerDynamicSubtreeNodeList(list);
    143                 }
    144             }
    145 
    146             NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
    147             for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
    148                 DynamicSubtreeNodeList* list = it->second;
    149                 if (list->isRootedAtDocument()) {
    150                     oldDocument->unregisterDynamicSubtreeNodeList(list);
    151                     newDocument->registerDynamicSubtreeNodeList(list);
    152                 }
     131    void adoptTreeScope(Document* oldDocument, Document* newDocument)
     132    {
     133        NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
     134        for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
     135            DynamicSubtreeNodeList* list = it->second;
     136            list->invalidateCache();
     137            if (oldDocument != newDocument && list->isRootedAtDocument()) {
     138                oldDocument->unregisterDynamicSubtreeNodeList(list);
     139                newDocument->registerDynamicSubtreeNodeList(list);
    153140            }
    154141        }
    155142
    156         if (oldTreeScope)
    157             oldTreeScope->removeNodeListCache();
    158         newTreeScope->addNodeListCache();
     143        NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
     144        for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
     145            DynamicSubtreeNodeList* list = it->second;
     146            list->invalidateCache();
     147            if (oldDocument != newDocument && list->isRootedAtDocument()) {
     148                oldDocument->unregisterDynamicSubtreeNodeList(list);
     149                newDocument->registerDynamicSubtreeNodeList(list);
     150            }
     151        }
     152
     153        TagNodeListCacheNS::iterator tagCacheEnd = m_tagNodeListCacheNS.end();
     154        for (TagNodeListCacheNS::iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEnd; ++it)
     155            it->second->invalidateCache();
    159156    }
    160157
    … …  
    216213    void setNodeLists(PassOwnPtr<NodeListsNodeData> lists) { m_nodeLists = lists; }
    217214    NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); }
    218     NodeListsNodeData* ensureNodeLists(Node* node)
     215    NodeListsNodeData* ensureNodeLists()
    219216    {
    220217        if (!m_nodeLists)
    221             createNodeLists(node);
     218            createNodeLists();
    222219        return m_nodeLists.get();
    223220    }
    … …  
    349346
    350347private:
    351     void createNodeLists(Node*);
     348    void createNodeLists();
    352349
    353350    TreeScope* m_treeScope;

  • trunk/Source/WebCore/dom/TreeScope.cpp

    r121079 r121106  
    5555    : m_rootNode(rootNode)
    5656    , m_parentTreeScope(0)
    57     , m_numNodeListCaches(0)
    5857{
    5958    ASSERT(rootNode);

  • trunk/Source/WebCore/dom/TreeScope.h

    r119799 r121106  
    6262    HTMLMapElement* getImageMap(const String& url) const;
    6363
    64     void addNodeListCache() { ++m_numNodeListCaches; }
    65     void removeNodeListCache() { ASSERT(m_numNodeListCaches > 0); --m_numNodeListCaches; }
    66     bool hasNodeListCaches() const { return m_numNodeListCaches; }
    67 
    6864    DOMSelection* getSelection() const;
    6965
    … …  
    9692    DocumentOrderedMap m_imageMapsByName;
    9793
    98     unsigned m_numNodeListCaches;
    99 
    10094    mutable RefPtr<DOMSelection> m_selection;
    10195};

  • trunk/Source/WebCore/dom/TreeScopeAdopter.cpp

    r121003 r121106  
    5555        NodeRareData* rareData = node->setTreeScope(newDocument == m_newScope ? 0 : m_newScope);
    5656        if (rareData && rareData->nodeLists())
    57             rareData->nodeLists()->adoptTreeScope(m_oldScope, m_newScope, oldDocument, newDocument);
     57            rareData->nodeLists()->adoptTreeScope(oldDocument, newDocument);
    5858
    5959        if (willMoveToNewDocument)

  • trunk/Source/WebCore/html/LabelableElement.cpp

    r120979 r121106  
    4848        return 0;
    4949
    50     return Node::ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<LabelsNodeList>(this, DynamicNodeList::LabelsNodeListType, starAtom);
     50    return Node::ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<LabelsNodeList>(this, DynamicNodeList::LabelsNodeListType, starAtom);
    5151}
    5252

  • trunk/Source/WebCore/html/LabelsNodeList.cpp

    r121003 r121106  
    3737    : DynamicSubtreeNodeList(forNode, RootedAtDocument)
    3838{
    39     document()->registerDynamicSubtreeNodeList(this);
    4039}
    4140
    … …  
    4342{
    4443    ownerNode()->nodeLists()->removeCacheWithAtomicName(this, DynamicNodeList::LabelsNodeListType, starAtom);
    45     document()->unregisterDynamicSubtreeNodeList(this);
    4644}
    4745   

  • trunk/Source/WebCore/html/RadioNodeList.cpp

    r121003 r121106  
    4242    , m_name(name)
    4343{
    44     document()->registerDynamicSubtreeNodeList(this);
    4544}
    4645
    … …  
    4847{
    4948    ownerNode()->nodeLists()->removeCacheWithAtomicName(this, DynamicNodeList::RadioNodeListType, m_name);
    50     document()->unregisterDynamicSubtreeNodeList(this);
    5149}
    5250
Note: See TracChangeset for help on using the changeset viewer.