Changeset 104210 in webkit


Ignore:
Timestamp:
Jan 5, 2012 1:48:50 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 Antti Koivisto.

Lazily invalidate the node list caches instead of invaliding them at the time of modification. We use
the DOM tree version to detect whether caches need to be invalidated or not. We now invalidate caches more
frequently after this patch (in particular, invalidates caches that are stored on nodes not present in
the ancestry of the modified nodes); however, our study on major Web sites such as Gmail, Facebook, Twitter,
etc... indicate that about 1% of real-world usage benefits from keeping the caches alive across different
DOM tree versions.

In order to invalidate caches lazily, this patch adds replaces the type of m_caches in DynamicSubtreeNodeList
by DynamicSubtreeNodeList::SubtreeCaches which encapsulates member variables in DynamicNodeList::Caches and
invalidates values as needed. Also this change allows m_caches to be allocated as a part of
DynamicSubtreeNodeList instead of a separate ref-counted object.

  • dom/Attr.cpp:

(WebCore::Attr::setValue):
(WebCore::Attr::childrenChanged):

  • dom/DynamicNodeList.cpp:

(WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList):
(WebCore::DynamicSubtreeNodeList::length):
(WebCore::DynamicSubtreeNodeList::itemForwardsFromCurrent):
(WebCore::DynamicSubtreeNodeList::itemBackwardsFromCurrent):
(WebCore::DynamicSubtreeNodeList::item):
(WebCore::DynamicSubtreeNodeList::invalidateCache):
(WebCore::DynamicNodeList::Caches::create):
(WebCore::DynamicNodeList::Caches::reset):

  • dom/DynamicNodeList.h:

(WebCore::DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::isLengthCacheValid): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::isItemCacheValid): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedLength): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedItem): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedItemOffset): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::setLengthCache): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::setItemCache): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::reset): Added.
(WebCore::DynamicSubtreeNodeList::SubtreeCaches::domVersionIsConsistent): Added.

  • dom/Element.cpp:

(WebCore::Element::updateAfterAttributeChanged):

  • dom/Node.cpp:

(WebCore::Node::setTreeScopeRecursively): Clear caches when a node moves from one document to another.
(WebCore::Node::invalidateNodeListsCacheAfterAttributeChanged): Only clears child node list of Attr.
(WebCore::Node::invalidateNodeListsCacheAfterChildrenChanged): Only clears child node list.
(WebCore::NodeListsNodeData::invalidateCaches): Merged with invalidateCachesThatDependOnAttributes.

  • dom/Node.h:
  • dom/NodeRareData.h:
  • html/HTMLElement.cpp:

(WebCore::HTMLElement::parseMappedAttribute):

  • html/HTMLLabelElement.cpp:
  • html/HTMLLabelElement.h:
Location:
trunk/Source/WebCore
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r104208 r104210  
     12012-01-05  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 Antti Koivisto.
     7
     8        Lazily invalidate the node list caches instead of invaliding them at the time of modification. We use
     9        the DOM tree version to detect whether caches need to be invalidated or not. We now invalidate caches more
     10        frequently after this patch (in particular, invalidates caches that are stored on nodes not present in
     11        the ancestry of the modified nodes); however, our study on major Web sites such as Gmail, Facebook, Twitter,
     12        etc... indicate that about 1% of real-world usage benefits from keeping the caches alive across different
     13        DOM tree versions.
     14
     15        In order to invalidate caches lazily, this patch adds replaces the type of m_caches in DynamicSubtreeNodeList
     16        by DynamicSubtreeNodeList::SubtreeCaches which encapsulates member variables in DynamicNodeList::Caches and
     17        invalidates values as needed. Also this change allows m_caches to be allocated as a part of
     18        DynamicSubtreeNodeList instead of a separate ref-counted object.
     19
     20        * dom/Attr.cpp:
     21        (WebCore::Attr::setValue):
     22        (WebCore::Attr::childrenChanged):
     23        * dom/DynamicNodeList.cpp:
     24        (WebCore::DynamicSubtreeNodeList::DynamicSubtreeNodeList):
     25        (WebCore::DynamicSubtreeNodeList::length):
     26        (WebCore::DynamicSubtreeNodeList::itemForwardsFromCurrent):
     27        (WebCore::DynamicSubtreeNodeList::itemBackwardsFromCurrent):
     28        (WebCore::DynamicSubtreeNodeList::item):
     29        (WebCore::DynamicSubtreeNodeList::invalidateCache):
     30        (WebCore::DynamicNodeList::Caches::create):
     31        (WebCore::DynamicNodeList::Caches::reset):
     32        * dom/DynamicNodeList.h:
     33        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches): Added.
     34        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::isLengthCacheValid): Added.
     35        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::isItemCacheValid): Added.
     36        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedLength): Added.
     37        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedItem): Added.
     38        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::cachedItemOffset): Added.
     39        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::setLengthCache): Added.
     40        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::setItemCache): Added.
     41        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::reset): Added.
     42        (WebCore::DynamicSubtreeNodeList::SubtreeCaches::domVersionIsConsistent): Added.
     43        * dom/Element.cpp:
     44        (WebCore::Element::updateAfterAttributeChanged):
     45        * dom/Node.cpp:
     46        (WebCore::Node::setTreeScopeRecursively): Clear caches when a node moves from one document to another.
     47        (WebCore::Node::invalidateNodeListsCacheAfterAttributeChanged): Only clears child node list of Attr.
     48        (WebCore::Node::invalidateNodeListsCacheAfterChildrenChanged): Only clears child node list.
     49        (WebCore::NodeListsNodeData::invalidateCaches): Merged with invalidateCachesThatDependOnAttributes.
     50        * dom/Node.h:
     51        * dom/NodeRareData.h:
     52        * html/HTMLElement.cpp:
     53        (WebCore::HTMLElement::parseMappedAttribute):
     54        * html/HTMLLabelElement.cpp:
     55        * html/HTMLLabelElement.h:
     56
    1572012-01-05  Ojan Vafai  <ojan@chromium.org>
    258

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

    r104116 r104210  
    130130    m_ignoreChildrenChanged--;
    131131
    132     invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
     132    invalidateNodeListsCacheAfterAttributeChanged();
    133133}
    134134
    … …  
    175175    Node::childrenChanged(changedByParser, beforeChange, afterChange, childCountDelta);
    176176
    177     invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
     177    invalidateNodeListsCacheAfterAttributeChanged();
    178178
    179179    // FIXME: We should include entity references in the value

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

    r104116 r104210  
    2929namespace WebCore {
    3030
     31DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches()
     32    : m_cachedItem(0)
     33    , m_isLengthCacheValid(false)
     34    , m_isItemCacheValid(false)
     35    , m_domTreeVersionAtTimeOfCaching(0)
     36{
     37}
     38
     39void DynamicSubtreeNodeList::SubtreeCaches::setLengthCache(Node* node, unsigned length)
     40{
     41    if (m_isItemCacheValid && !domVersionIsConsistent()) {
     42        m_cachedItem = node;
     43        m_isItemCacheValid = false;
     44    }
     45    m_cachedLength = length;
     46    m_isLengthCacheValid = true;
     47    m_domTreeVersionAtTimeOfCaching = node->document()->domTreeVersion();
     48}
     49
     50void DynamicSubtreeNodeList::SubtreeCaches::setItemCache(Node* item, unsigned offset)
     51{
     52    if (m_isLengthCacheValid && !domVersionIsConsistent())
     53        m_isLengthCacheValid = false;
     54    m_cachedItem = item;
     55    m_cachedItemOffset = offset;
     56    m_isItemCacheValid = true;
     57    m_domTreeVersionAtTimeOfCaching = item->document()->domTreeVersion();
     58}
     59
     60void DynamicSubtreeNodeList::SubtreeCaches::reset()
     61{
     62    m_cachedItem = 0;
     63    m_isLengthCacheValid = false;
     64    m_isItemCacheValid = false;
     65}
     66
    3167DynamicSubtreeNodeList::DynamicSubtreeNodeList(PassRefPtr<Node> node)
    3268    : DynamicNodeList(node)
    33     , m_caches(Caches::create())
    3469{
    3570    rootNode()->registerDynamicSubtreeNodeList(this);
    … …  
    4378unsigned DynamicSubtreeNodeList::length() const
    4479{
    45     if (m_caches->isLengthCacheValid)
    46         return m_caches->cachedLength;
     80    if (m_caches.isLengthCacheValid())
     81        return m_caches.cachedLength();
    4782
    4883    unsigned length = 0;
    … …  
    5186        length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
    5287
    53     m_caches->cachedLength = length;
    54     m_caches->isLengthCacheValid = true;
     88    m_caches.setLengthCache(node(), length);
    5589
    5690    return length;
    … …  
    6397        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
    6498            if (!remainingOffset) {
    65                 m_caches->lastItem = n;
    66                 m_caches->lastItemOffset = offset;
    67                 m_caches->isItemCacheValid = true;
     99                m_caches.setItemCache(n, offset);
    68100                return n;
    69101            }
    … …  
    81113        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
    82114            if (!remainingOffset) {
    83                 m_caches->lastItem = n;
    84                 m_caches->lastItemOffset = offset;
    85                 m_caches->isItemCacheValid = true;
     115                m_caches.setItemCache(n, offset);
    86116                return n;
    87117            }
    … …  
    97127    int remainingOffset = offset;
    98128    Node* start = node()->firstChild();
    99     if (m_caches->isItemCacheValid) {
    100         if (offset == m_caches->lastItemOffset)
    101             return m_caches->lastItem;
    102         else if (offset > m_caches->lastItemOffset || m_caches->lastItemOffset - offset < offset) {
    103             start = m_caches->lastItem;
    104             remainingOffset -= m_caches->lastItemOffset;
     129    if (m_caches.isItemCacheValid()) {
     130        if (offset == m_caches.cachedItemOffset())
     131            return m_caches.cachedItem();
     132        if (offset > m_caches.cachedItemOffset() || m_caches.cachedItemOffset() - offset < offset) {
     133            start = m_caches.cachedItem();
     134            remainingOffset -= m_caches.cachedItemOffset();
    105135        }
    106136    }
    … …  
    140170void DynamicSubtreeNodeList::invalidateCache()
    141171{
    142     m_caches->reset();
     172    m_caches.reset();
    143173}
    144174
    … …  
    150180}
    151181
    152 PassRefPtr<DynamicSubtreeNodeList::Caches> DynamicSubtreeNodeList::Caches::create()
     182PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
    153183{
    154184    return adoptRef(new Caches());
    155185}
    156186
    157 void DynamicSubtreeNodeList::Caches::reset()
     187void DynamicNodeList::Caches::reset()
    158188{
    159189    lastItem = 0;

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

    r104116 r104210  
    2525#define DynamicNodeList_h
    2626
     27#include "Document.h"
    2728#include "NodeList.h"
    2829#include <wtf/RefCounted.h>
    … …  
    4647        bool isLengthCacheValid : 1;
    4748        bool isItemCacheValid : 1;
     49
    4850    protected:
    4951        Caches();
    5052    };
     53
    5154    DynamicNodeList(PassRefPtr<Node> node)
    5255        : m_node(node)
    … …  
    7780protected:
    7881    DynamicSubtreeNodeList(PassRefPtr<Node> rootNode);
    79     mutable RefPtr<Caches> m_caches;
    8082
    8183private:
     84
     85    class SubtreeCaches {
     86    public:
     87        SubtreeCaches();
     88
     89        bool isLengthCacheValid() const { return m_isLengthCacheValid && domVersionIsConsistent(); }
     90        bool isItemCacheValid() const { return m_isItemCacheValid && domVersionIsConsistent(); }
     91
     92        unsigned cachedLength() const { return m_cachedLength; }
     93        Node* cachedItem() const { return m_cachedItem; }
     94        unsigned cachedItemOffset() const { return m_cachedItemOffset; }
     95
     96        void setLengthCache(Node* nodeForDocumentVersion, unsigned length);
     97        void setItemCache(Node*, unsigned offset);
     98        void reset();
     99
     100    private:
     101        Node* m_cachedItem;
     102        unsigned m_cachedItemOffset;
     103        unsigned m_cachedLength;
     104        bool m_isLengthCacheValid : 1;
     105        bool m_isItemCacheValid : 1;
     106
     107        bool domVersionIsConsistent() const
     108        {
     109            return m_cachedItem && m_cachedItem->document()->domTreeVersion() == m_domTreeVersionAtTimeOfCaching;
     110        }
     111        uint64_t m_domTreeVersionAtTimeOfCaching;
     112    };
     113
     114    mutable SubtreeCaches m_caches;
     115
    82116    virtual bool isDynamicNodeList() const;
    83117    Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;

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

    r104165 r104210  
    675675void Element::updateAfterAttributeChanged(Attribute* attr)
    676676{
    677     invalidateNodeListsCacheAfterAttributeChanged(attr->name());
     677    invalidateNodeListsCacheAfterAttributeChanged();
    678678
    679679    if (!AXObjectCache::accessibilityEnabled())

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

    r104116 r104210  
    490490
    491491        if (node->hasRareData() && node->rareData()->nodeLists()) {
     492            node->rareData()->nodeLists()->invalidateCaches();
    492493            if (currentTreeScope)
    493494                currentTreeScope->removeNodeListCache();
    … …  
    10031004}
    10041005
    1005 void Node::invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName& attrName)
     1006void Node::invalidateNodeListsCacheAfterAttributeChanged()
    10061007{
    10071008    if (hasRareData() && isAttributeNode()) {
    … …  
    10101011        data->clearChildNodeListCache();
    10111012    }
    1012 
    1013     // This list should be sync'ed with NodeListsNodeData.
    1014     if (attrName != classAttr
    1015 #if ENABLE(MICRODATA)
    1016         && attrName != itemscopeAttr
    1017         && attrName != itempropAttr
    1018 #endif
    1019         && attrName != nameAttr)
    1020         return;
    1021 
    1022     if (!treeScope()->hasNodeListCaches())
    1023         return;
    1024 
    1025     for (Node* node = this; node; node = node->parentNode()) {
    1026         ASSERT(this == node || !node->isAttributeNode());
    1027         if (!node->hasRareData())
    1028             continue;
    1029         NodeRareData* data = node->rareData();
    1030         if (!data->nodeLists())
    1031             continue;
    1032 
    1033         data->nodeLists()->invalidateCachesThatDependOnAttributes();
    1034         removeNodeListCacheIfPossible(node, data);
    1035     }
    10361013}
    10371014
    … …  
    10401017    if (hasRareData())
    10411018        rareData()->clearChildNodeListCache();
    1042 
    1043     if (!treeScope()->hasNodeListCaches())
    1044         return;
    1045     for (Node* node = this; node; node = node->parentNode()) {
    1046         if (!node->hasRareData())
    1047             continue;
    1048         NodeRareData* data = node->rareData();
    1049         if (!data->nodeLists())
    1050             continue;
    1051 
    1052         data->nodeLists()->invalidateCaches();
    1053 
    1054         NodeListsNodeData::NodeListSet::iterator end = data->nodeLists()->m_listsWithCaches.end();
    1055         for (NodeListsNodeData::NodeListSet::iterator it = data->nodeLists()->m_listsWithCaches.begin(); it != end; ++it)
    1056             (*it)->invalidateCache();
    1057 
    1058         removeNodeListCacheIfPossible(node, data);
    1059     }
    1060 }
    1061 
    1062 void Node::notifyLocalNodeListsLabelChanged()
    1063 {
    1064     if (!hasRareData())
    1065         return;
    1066     NodeRareData* data = rareData();
    1067     if (!data->nodeLists())
    1068         return;
    1069 
    1070     if (data->nodeLists()->m_labelsNodeListCache)
    1071         data->nodeLists()->m_labelsNodeListCache->invalidateCache();
    10721019}
    10731020
    … …  
    22442191}
    22452192
    2246 #if ENABLE(MICRODATA)
    2247 void Node::itemTypeAttributeChanged()
    2248 {
    2249     Node * rootNode = document();
    2250 
    2251     if (!rootNode->hasRareData())
    2252         return;
    2253 
    2254     NodeRareData* data = rootNode->rareData();
    2255 
    2256     if (!data->nodeLists())
    2257         return;
    2258 
    2259     data->nodeLists()->invalidateMicrodataItemListCaches();
    2260 }
    2261 #endif
    2262 
    22632193#ifndef NDEBUG
    22642194
    … …  
    23892319    for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheNSEnd; ++it)
    23902320        it->second->invalidateCache();
    2391     invalidateCachesThatDependOnAttributes();
    2392 }
    2393 
    2394 void NodeListsNodeData::invalidateCachesThatDependOnAttributes()
    2395 {
     2321
    23962322    ClassNodeListCache::iterator classCacheEnd = m_classNodeListCache.end();
    23972323    for (ClassNodeListCache::iterator it = m_classNodeListCache.begin(); it != classCacheEnd; ++it)
    … …  
    24072333    invalidateMicrodataItemListCaches();
    24082334#endif
     2335   
    24092336}
    24102337

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

    r104116 r104210  
    522522    void registerDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
    523523    void unregisterDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
    524     void invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName&);
     524    void invalidateNodeListsCacheAfterAttributeChanged();
    525525    void invalidateNodeListsCacheAfterChildrenChanged();
    526     void notifyLocalNodeListsLabelChanged();
    527526    void removeCachedClassNodeList(ClassNodeList*, const String&);
    528527
    … …  
    592591
    593592#if ENABLE(MICRODATA)
    594     void itemTypeAttributeChanged();
    595 
    596593    DOMSettableTokenList* itemProp();
    597594    DOMSettableTokenList* itemRef();

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

    r104116 r104210  
    7979   
    8080    void invalidateCaches();
    81     void invalidateCachesThatDependOnAttributes();
    8281
    8382#if ENABLE(MICRODATA)

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

    r104116 r104210  
    238238    } else if (attr->name() == itemtypeAttr) {
    239239        setItemType(attr->value());
    240         itemTypeAttributeChanged();
    241240#endif
    242241    }

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

    r104116 r104210  
    155155}
    156156
    157 void HTMLLabelElement::parseMappedAttribute(Attribute* attribute)
    158 {
    159     if (attribute->name() == forAttr) {
    160         // htmlFor attribute change affects other nodes than this.
    161         // Clear the caches to ensure that the labels caches are cleared.
    162         if (document())
    163             document()->notifyLocalNodeListsLabelChanged();
    164     } else
    165         HTMLElement::parseMappedAttribute(attribute);
    166 }
    167                
    168157} // namespace

  • trunk/Source/WebCore/html/HTMLLabelElement.h

    r104116 r104210  
    5151
    5252    void focus(bool restorePreviousSelection = true);
    53 
    54     virtual void parseMappedAttribute(Attribute*);
    5553};
    5654
Note: See TracChangeset for help on using the changeset viewer.