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:
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@104210
268f45cc-cd09-0410-ab3c-
d52691b4dbfc
+2012-01-05 Ryosuke Niwa <rniwa@webkit.org>
+
+ 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:
+
2012-01-05 Ojan Vafai <ojan@chromium.org>
IE quirk for percentage size on a table element doesn't work with orthogonal writing modes
createTextChild();
m_ignoreChildrenChanged--;
- invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
}
void Attr::setValue(const AtomicString& value, ExceptionCode&)
Node::childrenChanged(changedByParser, beforeChange, afterChange, childCountDelta);
- invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
// FIXME: We should include entity references in the value
namespace WebCore {
+DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches()
+ : m_cachedItem(0)
+ , m_isLengthCacheValid(false)
+ , m_isItemCacheValid(false)
+ , m_domTreeVersionAtTimeOfCaching(0)
+{
+}
+
+void DynamicSubtreeNodeList::SubtreeCaches::setLengthCache(Node* node, unsigned length)
+{
+ if (m_isItemCacheValid && !domVersionIsConsistent()) {
+ m_cachedItem = node;
+ m_isItemCacheValid = false;
+ }
+ m_cachedLength = length;
+ m_isLengthCacheValid = true;
+ m_domTreeVersionAtTimeOfCaching = node->document()->domTreeVersion();
+}
+
+void DynamicSubtreeNodeList::SubtreeCaches::setItemCache(Node* item, unsigned offset)
+{
+ if (m_isLengthCacheValid && !domVersionIsConsistent())
+ m_isLengthCacheValid = false;
+ m_cachedItem = item;
+ m_cachedItemOffset = offset;
+ m_isItemCacheValid = true;
+ m_domTreeVersionAtTimeOfCaching = item->document()->domTreeVersion();
+}
+
+void DynamicSubtreeNodeList::SubtreeCaches::reset()
+{
+ m_cachedItem = 0;
+ m_isLengthCacheValid = false;
+ m_isItemCacheValid = false;
+}
+
DynamicSubtreeNodeList::DynamicSubtreeNodeList(PassRefPtr<Node> node)
: DynamicNodeList(node)
- , m_caches(Caches::create())
{
rootNode()->registerDynamicSubtreeNodeList(this);
}
unsigned DynamicSubtreeNodeList::length() const
{
- if (m_caches->isLengthCacheValid)
- return m_caches->cachedLength;
+ if (m_caches.isLengthCacheValid())
+ return m_caches.cachedLength();
unsigned length = 0;
for (Node* n = node()->firstChild(); n; n = n->traverseNextNode(rootNode()))
length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
- m_caches->cachedLength = length;
- m_caches->isLengthCacheValid = true;
+ m_caches.setLengthCache(node(), length);
return length;
}
for (Node* n = start; n; n = n->traverseNextNode(rootNode())) {
if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
if (!remainingOffset) {
- m_caches->lastItem = n;
- m_caches->lastItemOffset = offset;
- m_caches->isItemCacheValid = true;
+ m_caches.setItemCache(n, offset);
return n;
}
--remainingOffset;
for (Node* n = start; n; n = n->traversePreviousNode(rootNode())) {
if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
if (!remainingOffset) {
- m_caches->lastItem = n;
- m_caches->lastItemOffset = offset;
- m_caches->isItemCacheValid = true;
+ m_caches.setItemCache(n, offset);
return n;
}
++remainingOffset;
{
int remainingOffset = offset;
Node* start = node()->firstChild();
- if (m_caches->isItemCacheValid) {
- if (offset == m_caches->lastItemOffset)
- return m_caches->lastItem;
- else if (offset > m_caches->lastItemOffset || m_caches->lastItemOffset - offset < offset) {
- start = m_caches->lastItem;
- remainingOffset -= m_caches->lastItemOffset;
+ if (m_caches.isItemCacheValid()) {
+ if (offset == m_caches.cachedItemOffset())
+ return m_caches.cachedItem();
+ if (offset > m_caches.cachedItemOffset() || m_caches.cachedItemOffset() - offset < offset) {
+ start = m_caches.cachedItem();
+ remainingOffset -= m_caches.cachedItemOffset();
}
}
void DynamicSubtreeNodeList::invalidateCache()
{
- m_caches->reset();
+ m_caches.reset();
}
DynamicSubtreeNodeList::Caches::Caches()
{
}
-PassRefPtr<DynamicSubtreeNodeList::Caches> DynamicSubtreeNodeList::Caches::create()
+PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
{
return adoptRef(new Caches());
}
-void DynamicSubtreeNodeList::Caches::reset()
+void DynamicNodeList::Caches::reset()
{
lastItem = 0;
isLengthCacheValid = false;
#ifndef DynamicNodeList_h
#define DynamicNodeList_h
+#include "Document.h"
#include "NodeList.h"
#include <wtf/RefCounted.h>
#include <wtf/Forward.h>
unsigned lastItemOffset;
bool isLengthCacheValid : 1;
bool isItemCacheValid : 1;
+
protected:
Caches();
};
+
DynamicNodeList(PassRefPtr<Node> node)
: m_node(node)
{ }
protected:
DynamicSubtreeNodeList(PassRefPtr<Node> rootNode);
- mutable RefPtr<Caches> m_caches;
private:
+
+ class SubtreeCaches {
+ public:
+ SubtreeCaches();
+
+ bool isLengthCacheValid() const { return m_isLengthCacheValid && domVersionIsConsistent(); }
+ bool isItemCacheValid() const { return m_isItemCacheValid && domVersionIsConsistent(); }
+
+ unsigned cachedLength() const { return m_cachedLength; }
+ Node* cachedItem() const { return m_cachedItem; }
+ unsigned cachedItemOffset() const { return m_cachedItemOffset; }
+
+ void setLengthCache(Node* nodeForDocumentVersion, unsigned length);
+ void setItemCache(Node*, unsigned offset);
+ void reset();
+
+ private:
+ Node* m_cachedItem;
+ unsigned m_cachedItemOffset;
+ unsigned m_cachedLength;
+ bool m_isLengthCacheValid : 1;
+ bool m_isItemCacheValid : 1;
+
+ bool domVersionIsConsistent() const
+ {
+ return m_cachedItem && m_cachedItem->document()->domTreeVersion() == m_domTreeVersionAtTimeOfCaching;
+ }
+ uint64_t m_domTreeVersionAtTimeOfCaching;
+ };
+
+ mutable SubtreeCaches m_caches;
+
virtual bool isDynamicNodeList() const;
Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
Node* itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
void Element::updateAfterAttributeChanged(Attribute* attr)
{
- invalidateNodeListsCacheAfterAttributeChanged(attr->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
if (!AXObjectCache::accessibilityEnabled())
return;
node->ensureRareData()->setTreeScope(newTreeScope);
if (node->hasRareData() && node->rareData()->nodeLists()) {
+ node->rareData()->nodeLists()->invalidateCaches();
if (currentTreeScope)
currentTreeScope->removeNodeListCache();
newTreeScope->addNodeListCache();
removeNodeListCacheIfPossible(this, data);
}
-void Node::invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName& attrName)
+void Node::invalidateNodeListsCacheAfterAttributeChanged()
{
if (hasRareData() && isAttributeNode()) {
NodeRareData* data = rareData();
ASSERT(!data->nodeLists());
data->clearChildNodeListCache();
}
-
- // This list should be sync'ed with NodeListsNodeData.
- if (attrName != classAttr
-#if ENABLE(MICRODATA)
- && attrName != itemscopeAttr
- && attrName != itempropAttr
-#endif
- && attrName != nameAttr)
- return;
-
- if (!treeScope()->hasNodeListCaches())
- return;
-
- for (Node* node = this; node; node = node->parentNode()) {
- ASSERT(this == node || !node->isAttributeNode());
- if (!node->hasRareData())
- continue;
- NodeRareData* data = node->rareData();
- if (!data->nodeLists())
- continue;
-
- data->nodeLists()->invalidateCachesThatDependOnAttributes();
- removeNodeListCacheIfPossible(node, data);
- }
}
void Node::invalidateNodeListsCacheAfterChildrenChanged()
{
if (hasRareData())
rareData()->clearChildNodeListCache();
-
- if (!treeScope()->hasNodeListCaches())
- return;
- for (Node* node = this; node; node = node->parentNode()) {
- if (!node->hasRareData())
- continue;
- NodeRareData* data = node->rareData();
- if (!data->nodeLists())
- continue;
-
- data->nodeLists()->invalidateCaches();
-
- NodeListsNodeData::NodeListSet::iterator end = data->nodeLists()->m_listsWithCaches.end();
- for (NodeListsNodeData::NodeListSet::iterator it = data->nodeLists()->m_listsWithCaches.begin(); it != end; ++it)
- (*it)->invalidateCache();
-
- removeNodeListCacheIfPossible(node, data);
- }
-}
-
-void Node::notifyLocalNodeListsLabelChanged()
-{
- if (!hasRareData())
- return;
- NodeRareData* data = rareData();
- if (!data->nodeLists())
- return;
-
- if (data->nodeLists()->m_labelsNodeListCache)
- data->nodeLists()->m_labelsNodeListCache->invalidateCache();
}
void Node::removeCachedClassNodeList(ClassNodeList* list, const String& className)
return p;
}
-#if ENABLE(MICRODATA)
-void Node::itemTypeAttributeChanged()
-{
- Node * rootNode = document();
-
- if (!rootNode->hasRareData())
- return;
-
- NodeRareData* data = rootNode->rareData();
-
- if (!data->nodeLists())
- return;
-
- data->nodeLists()->invalidateMicrodataItemListCaches();
-}
-#endif
-
#ifndef NDEBUG
static void appendAttributeDesc(const Node* node, String& string, const QualifiedName& name, const char* attrDesc)
TagNodeListCacheNS::const_iterator tagCacheNSEnd = m_tagNodeListCacheNS.end();
for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheNSEnd; ++it)
it->second->invalidateCache();
- invalidateCachesThatDependOnAttributes();
-}
-void NodeListsNodeData::invalidateCachesThatDependOnAttributes()
-{
ClassNodeListCache::iterator classCacheEnd = m_classNodeListCache.end();
for (ClassNodeListCache::iterator it = m_classNodeListCache.begin(); it != classCacheEnd; ++it)
it->second->invalidateCache();
#if ENABLE(MICRODATA)
invalidateMicrodataItemListCaches();
#endif
+
}
#if ENABLE(MICRODATA)
void registerDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
void unregisterDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
- void invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName&);
+ void invalidateNodeListsCacheAfterAttributeChanged();
void invalidateNodeListsCacheAfterChildrenChanged();
- void notifyLocalNodeListsLabelChanged();
void removeCachedClassNodeList(ClassNodeList*, const String&);
void removeCachedNameNodeList(NameNodeList*, const String&);
virtual EventTargetData* ensureEventTargetData();
#if ENABLE(MICRODATA)
- void itemTypeAttributeChanged();
-
DOMSettableTokenList* itemProp();
DOMSettableTokenList* itemRef();
DOMSettableTokenList* itemType();
}
void invalidateCaches();
- void invalidateCachesThatDependOnAttributes();
#if ENABLE(MICRODATA)
void invalidateMicrodataItemListCaches();
setItemRef(attr->value());
} else if (attr->name() == itemtypeAttr) {
setItemType(attr->value());
- itemTypeAttributeChanged();
#endif
}
// standard events
HTMLElement::accessKeyAction(sendMouseEvents);
}
-void HTMLLabelElement::parseMappedAttribute(Attribute* attribute)
-{
- if (attribute->name() == forAttr) {
- // htmlFor attribute change affects other nodes than this.
- // Clear the caches to ensure that the labels caches are cleared.
- if (document())
- document()->notifyLocalNodeListsLabelChanged();
- } else
- HTMLElement::parseMappedAttribute(attribute);
-}
-
} // namespace
virtual void defaultEventHandler(Event*);
void focus(bool restorePreviousSelection = true);
-
- virtual void parseMappedAttribute(Attribute*);
};
} //namespace