- Revision
- 104084
- Author
- [email protected]
- Date
- 2012-01-04 15:08:50 -0800 (Wed, 04 Jan 2012)
Log 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:
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (104083 => 104084)
--- trunk/Source/WebCore/ChangeLog 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/ChangeLog 2012-01-04 23:08:50 UTC (rev 104084)
@@ -1,3 +1,59 @@
+2011-12-30 Ryosuke Niwa <[email protected]>
+
+ 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-04 Ryosuke Niwa <[email protected]>
Revert unintentional changes to Element.cpp in r104068.
Modified: trunk/Source/WebCore/dom/Attr.cpp (104083 => 104084)
--- trunk/Source/WebCore/dom/Attr.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/Attr.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -129,7 +129,7 @@
createTextChild();
m_ignoreChildrenChanged--;
- invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
}
void Attr::setValue(const AtomicString& value, ExceptionCode&)
@@ -174,7 +174,7 @@
Node::childrenChanged(changedByParser, beforeChange, afterChange, childCountDelta);
- invalidateNodeListsCacheAfterAttributeChanged(m_attribute->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
// FIXME: We should include entity references in the value
Modified: trunk/Source/WebCore/dom/DynamicNodeList.cpp (104083 => 104084)
--- trunk/Source/WebCore/dom/DynamicNodeList.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/DynamicNodeList.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -28,9 +28,42 @@
namespace WebCore {
+DynamicSubtreeNodeList::SubtreeCaches::SubtreeCaches()
+ : m_cachedItem(0)
+ , m_isLengthCacheValid(false)
+ , m_isItemCacheValid(false)
+ , m_DOMVersionAtTimeOfCaching(0)
+{
+}
+
+inline void DynamicSubtreeNodeList::SubtreeCaches::setLengthCache(Node* node, unsigned length)
+{
+ if (m_isItemCacheValid && !domVersionIsConsistent()) {
+ m_cachedItem = node;
+ m_isItemCacheValid = false;
+ }
+ m_cachedLength = length;
+ m_isLengthCacheValid = true;
+}
+
+inline void DynamicSubtreeNodeList::SubtreeCaches::setItemCache(Node* item, unsigned offset)
+{
+ if (m_isLengthCacheValid && !domVersionIsConsistent())
+ m_isLengthCacheValid = false;
+ m_cachedItem = item;
+ m_cachedItemOffset = offset;
+ m_isLengthCacheValid = true;
+}
+
+inline 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);
}
@@ -42,16 +75,15 @@
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;
}
@@ -62,9 +94,7 @@
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;
@@ -80,9 +110,7 @@
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;
@@ -96,12 +124,12 @@
{
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();
}
}
@@ -139,7 +167,7 @@
void DynamicSubtreeNodeList::invalidateCache()
{
- m_caches->reset();
+ m_caches.reset();
}
DynamicSubtreeNodeList::Caches::Caches()
@@ -149,12 +177,12 @@
{
}
-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;
Modified: trunk/Source/WebCore/dom/DynamicNodeList.h (104083 => 104084)
--- trunk/Source/WebCore/dom/DynamicNodeList.h 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/DynamicNodeList.h 2012-01-04 23:08:50 UTC (rev 104084)
@@ -24,6 +24,7 @@
#ifndef DynamicNodeList_h
#define DynamicNodeList_h
+#include "Document.h"
#include "NodeList.h"
#include <wtf/RefCounted.h>
#include <wtf/Forward.h>
@@ -45,9 +46,11 @@
unsigned lastItemOffset;
bool isLengthCacheValid : 1;
bool isItemCacheValid : 1;
+
protected:
Caches();
};
+
DynamicNodeList(PassRefPtr<Node> node)
: m_node(node)
{ }
@@ -76,9 +79,40 @@
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* node, unsigned length);
+ void setItemCache(Node* item, unsigned offset);
+ void reset();
+
+ private:
+ Node* m_cachedItem;
+ unsigned m_cachedItemOffset;
+ unsigned m_cachedLength : 30;
+ unsigned m_isLengthCacheValid : 1;
+ unsigned m_isItemCacheValid : 1;
+
+ bool domVersionIsConsistent() const
+ {
+ return m_cachedItem && m_cachedItem->document()->domTreeVersion() == m_DOMVersionAtTimeOfCaching;
+ }
+ uint64_t m_DOMVersionAtTimeOfCaching;
+ };
+
+ 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;
Modified: trunk/Source/WebCore/dom/Element.cpp (104083 => 104084)
--- trunk/Source/WebCore/dom/Element.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/Element.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -674,7 +674,7 @@
void Element::updateAfterAttributeChanged(Attribute* attr)
{
- invalidateNodeListsCacheAfterAttributeChanged(attr->name());
+ invalidateNodeListsCacheAfterAttributeChanged();
if (!AXObjectCache::accessibilityEnabled())
return;
Modified: trunk/Source/WebCore/dom/Node.cpp (104083 => 104084)
--- trunk/Source/WebCore/dom/Node.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/Node.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -489,6 +489,7 @@
node->ensureRareData()->setTreeScope(newTreeScope);
if (node->hasRareData() && node->rareData()->nodeLists()) {
+ node->rareData()->nodeLists()->invalidateCaches();
if (currentTreeScope)
currentTreeScope->removeNodeListCache();
newTreeScope->addNodeListCache();
@@ -1002,75 +1003,21 @@
removeNodeListCacheIfPossible(this, data);
}
-void Node::invalidateNodeListsCacheAfterAttributeChanged(const QualifiedName& attrName)
+void Node::invalidateNodeListsCacheAfterAttributeChanged()
{
if (hasRareData() && isAttributeNode()) {
NodeRareData* data = ""
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 = ""
- 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 = ""
- 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 = ""
- if (!data->nodeLists())
- return;
-
- if (data->nodeLists()->m_labelsNodeListCache)
- data->nodeLists()->m_labelsNodeListCache->invalidateCache();
-}
-
void Node::removeCachedClassNodeList(ClassNodeList* list, const String& className)
{
ASSERT(rareData());
@@ -2243,23 +2190,6 @@
return p;
}
-#if ENABLE(MICRODATA)
-void Node::itemTypeAttributeChanged()
-{
- Node * rootNode = document();
-
- if (!rootNode->hasRareData())
- return;
-
- NodeRareData* data = ""
-
- if (!data->nodeLists())
- return;
-
- data->nodeLists()->invalidateMicrodataItemListCaches();
-}
-#endif
-
#ifndef NDEBUG
static void appendAttributeDesc(const Node* node, String& string, const QualifiedName& name, const char* attrDesc)
@@ -2388,11 +2318,7 @@
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();
@@ -2406,6 +2332,7 @@
#if ENABLE(MICRODATA)
invalidateMicrodataItemListCaches();
#endif
+
}
#if ENABLE(MICRODATA)
Modified: trunk/Source/WebCore/dom/Node.h (104083 => 104084)
--- trunk/Source/WebCore/dom/Node.h 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/Node.h 2012-01-04 23:08:50 UTC (rev 104084)
@@ -521,9 +521,8 @@
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&);
@@ -591,8 +590,6 @@
virtual EventTargetData* ensureEventTargetData();
#if ENABLE(MICRODATA)
- void itemTypeAttributeChanged();
-
DOMSettableTokenList* itemProp();
DOMSettableTokenList* itemRef();
DOMSettableTokenList* itemType();
Modified: trunk/Source/WebCore/dom/NodeRareData.h (104083 => 104084)
--- trunk/Source/WebCore/dom/NodeRareData.h 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/dom/NodeRareData.h 2012-01-04 23:08:50 UTC (rev 104084)
@@ -78,7 +78,6 @@
}
void invalidateCaches();
- void invalidateCachesThatDependOnAttributes();
#if ENABLE(MICRODATA)
void invalidateMicrodataItemListCaches();
Modified: trunk/Source/WebCore/html/HTMLElement.cpp (104083 => 104084)
--- trunk/Source/WebCore/html/HTMLElement.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/html/HTMLElement.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -237,7 +237,6 @@
setItemRef(attr->value());
} else if (attr->name() == itemtypeAttr) {
setItemType(attr->value());
- itemTypeAttributeChanged();
#endif
}
// standard events
Modified: trunk/Source/WebCore/html/HTMLLabelElement.cpp (104083 => 104084)
--- trunk/Source/WebCore/html/HTMLLabelElement.cpp 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/html/HTMLLabelElement.cpp 2012-01-04 23:08:50 UTC (rev 104084)
@@ -154,15 +154,4 @@
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
Modified: trunk/Source/WebCore/html/HTMLLabelElement.h (104083 => 104084)
--- trunk/Source/WebCore/html/HTMLLabelElement.h 2012-01-04 23:06:27 UTC (rev 104083)
+++ trunk/Source/WebCore/html/HTMLLabelElement.h 2012-01-04 23:08:50 UTC (rev 104084)
@@ -50,8 +50,6 @@
virtual void defaultEventHandler(Event*);
void focus(bool restorePreviousSelection = true);
-
- virtual void parseMappedAttribute(Attribute*);
};
} //namespace