Changeset 104084 in webkit


Ignore:
Timestamp:
Jan 4, 2012 3:08: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

    r104081 r104084  
     12011-12-30  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-04  Ryosuke Niwa  <rniwa@webkit.org>
    258

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

    r103611 r104084  
    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

    r102834 r104084  
    2929namespace WebCore {
    3030
     31DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches()
     32    : m_cachedItem(0)
     33    , m_isLengthCacheValid(false)
     34    , m_isItemCacheValid(false)
     35    , m_DOMVersionAtTimeOfCaching(0)
     36{
     37}
     38
     39inline void 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}
     48
     49inline void DynamicSubtreeNodeList::SubtreeCaches::setItemCache(Node* item, unsigned offset)
     50{
     51    if (m_isLengthCacheValid && !domVersionIsConsistent())
     52        m_isLengthCacheValid = false;
     53    m_cachedItem = item;
     54    m_cachedItemOffset = offset;
     55    m_isLengthCacheValid = true;
     56}
     57
     58inline void DynamicSubtreeNodeList::SubtreeCaches::reset()
     59{
     60    m_cachedItem = 0;
     61    m_isLengthCacheValid = false;
     62    m_isItemCacheValid = false;
     63}
     64
    3165DynamicSubtreeNodeList::DynamicSubtreeNodeList(PassRefPtr<Node> node)
    3266    : DynamicNodeList(node)
    33     , m_caches(Caches::create())
    3467{
    3568    rootNode()->registerDynamicSubtreeNodeList(this);
    … …  
    4376unsigned DynamicSubtreeNodeList::length() const
    4477{
    45     if (m_caches->isLengthCacheValid)
    46         return m_caches->cachedLength;
     78    if (m_caches.isLengthCacheValid())
     79        return m_caches.cachedLength();
    4780
    4881    unsigned length = 0;
    … …  
    5184        length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
    5285
    53     m_caches->cachedLength = length;
    54     m_caches->isLengthCacheValid = true;
     86    m_caches.setLengthCache(node(), length);
    5587
    5688    return length;
    … …  
    6395        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
    6496            if (!remainingOffset) {
    65                 m_caches->lastItem = n;
    66                 m_caches->lastItemOffset = offset;
    67                 m_caches->isItemCacheValid = true;
     97                m_caches.setItemCache(n, offset);
    6898                return n;
    6999            }
    … …  
    81111        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
    82112            if (!remainingOffset) {
    83                 m_caches->lastItem = n;
    84                 m_caches->lastItemOffset = offset;
    85                 m_caches->isItemCacheValid = true;
     113                m_caches.setItemCache(n, offset);
    86114                return n;
    87115            }
    … …  
    97125    int remainingOffset = offset;
    98126    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;
     127    if (m_caches.isItemCacheValid()) {
     128        if (offset == m_caches.cachedItemOffset())
     129            return m_caches.cachedItem();
     130        if (offset > m_caches.cachedItemOffset() || m_caches.cachedItemOffset() - offset < offset) {
     131            start = m_caches.cachedItem();
     132            remainingOffset -= m_caches.cachedItemOffset();
    105133        }
    106134    }
    … …  
    140168void DynamicSubtreeNodeList::invalidateCache()
    141169{
    142     m_caches->reset();
     170    m_caches.reset();
    143171}
    144172
    … …  
    150178}
    151179
    152 PassRefPtr<DynamicSubtreeNodeList::Caches> DynamicSubtreeNodeList::Caches::create()
     180PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
    153181{
    154182    return adoptRef(new Caches());
    155183}
    156184
    157 void DynamicSubtreeNodeList::Caches::reset()
     185void DynamicNodeList::Caches::reset()
    158186{
    159187    lastItem = 0;

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

    r102834 r104084  
    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* node, unsigned length);
     97        void setItemCache(Node* item, unsigned offset);
     98        void reset();
     99
     100    private:
     101        Node* m_cachedItem;
     102        unsigned m_cachedItemOffset;
     103        unsigned m_cachedLength : 30;
     104        unsigned m_isLengthCacheValid : 1;
     105        unsigned m_isItemCacheValid : 1;
     106
     107        bool domVersionIsConsistent() const
     108        {
     109            return m_cachedItem && m_cachedItem->document()->domTreeVersion() == m_DOMVersionAtTimeOfCaching;
     110        }
     111        uint64_t m_DOMVersionAtTimeOfCaching;
     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

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

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

    r103701 r104084  
    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

    r103701 r104084  
    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

    r102834 r104084  
    7979   
    8080    void invalidateCaches();
    81     void invalidateCachesThatDependOnAttributes();
    8281
    8382#if ENABLE(MICRODATA)

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

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

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

    r100805 r104084  
    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

    r100805 r104084  
    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.