Diff
Modified: trunk/Source/WebCore/ChangeLog (121105 => 121106)
--- trunk/Source/WebCore/ChangeLog 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/ChangeLog 2012-06-24 03:13:19 UTC (rev 121106)
@@ -1,5 +1,73 @@
2012-06-23 Ryosuke Niwa <[email protected]>
+ 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):
+
+2012-06-23 Ryosuke Niwa <[email protected]>
+
Clang and cl.exe build fix after r121103. Don't inherit from WTF::PairHash<unsigned char, StringType>.
* dom/NodeRareData.h:
Modified: trunk/Source/WebCore/dom/Document.cpp (121105 => 121106)
--- trunk/Source/WebCore/dom/Document.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/Document.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -3872,11 +3872,14 @@
m_listsInvalidatedAtDocument.remove(list);
}
-void Document::clearNodeListCaches()
+void Document::clearNodeListCaches(const QualifiedName* attrName)
{
+ // FIXME: Only invalidate caches of node lists that match attrName.
HashSet<DynamicSubtreeNodeList*>::iterator end = m_listsInvalidatedAtDocument.end();
- for (HashSet<DynamicSubtreeNodeList*>::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it)
- (*it)->invalidateCache();
+ for (HashSet<DynamicSubtreeNodeList*>::iterator it = m_listsInvalidatedAtDocument.begin(); it != end; ++it) {
+ if (!attrName || (*it)->shouldInvalidateOnAttributeChange())
+ (*it)->invalidateCache();
+ }
}
void Document::attachNodeIterator(NodeIterator* ni)
Modified: trunk/Source/WebCore/dom/Document.h (121105 => 121106)
--- trunk/Source/WebCore/dom/Document.h 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/Document.h 2012-06-24 03:13:19 UTC (rev 121106)
@@ -714,7 +714,7 @@
void registerDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
void unregisterDynamicSubtreeNodeList(DynamicSubtreeNodeList*);
- void clearNodeListCaches();
+ void clearNodeListCaches(const QualifiedName* attrName);
void attachNodeIterator(NodeIterator*);
void detachNodeIterator(NodeIterator*);
Modified: trunk/Source/WebCore/dom/DynamicNodeList.cpp (121105 => 121106)
--- trunk/Source/WebCore/dom/DynamicNodeList.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/DynamicNodeList.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -30,6 +30,7 @@
DynamicSubtreeNodeList::~DynamicSubtreeNodeList()
{
+ document()->unregisterDynamicSubtreeNodeList(this);
}
unsigned DynamicSubtreeNodeList::length() const
Modified: trunk/Source/WebCore/dom/DynamicNodeList.h (121105 => 121106)
--- trunk/Source/WebCore/dom/DynamicNodeList.h 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/DynamicNodeList.h 2012-06-24 03:13:19 UTC (rev 121106)
@@ -123,7 +123,9 @@
protected:
DynamicSubtreeNodeList(PassRefPtr<Node> node, RootType rootType = RootedAtNode, InvalidationType invalidationType = AlwaysInvalidate)
: DynamicNodeList(node, rootType, invalidationType)
- { }
+ {
+ document()->registerDynamicSubtreeNodeList(this);
+ }
private:
Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
Modified: trunk/Source/WebCore/dom/Node.cpp (121105 => 121106)
--- trunk/Source/WebCore/dom/Node.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/Node.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -482,9 +482,6 @@
void Node::clearRareData()
{
ASSERT(hasRareData());
- if (treeScope() && rareData()->nodeLists())
- treeScope()->removeNodeListCache();
-
#if ENABLE(MUTATION_OBSERVERS)
ASSERT(!transientMutationObserverRegistry() || transientMutationObserverRegistry()->isEmpty());
#endif
@@ -951,10 +948,10 @@
return;
// FIXME: Move the list of attributes each NodeList type cares about to be a static on the
- // appropriate NodeList class. Then use those lists here and in invalidateCachesThatDependOnAttributes
+ // appropriate NodeList class. Then use those lists here and in clearNodeListCaches
// to only invalidate the cache types that depend on the attribute that changed.
// FIXME: Keep track of when we have no caches of a given type so that we can avoid the for-loop
- // below even if a related attribute changed (e.g. if we have no RadioNodeLists, we don't need
+ // in clearNodeListCaches even if a related attribute changed (e.g. if we have no RadioNodeLists, we don't need
// to invalidate any caches when id attributes change.)
if (attrName != classAttr
#if ENABLE(MICRODATA)
@@ -967,21 +964,7 @@
&& (attrName != idAttr || !attributeOwnerElement->isFormControlElement()))
return;
- document()->clearNodeListCaches();
-
- 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()->invalidateCaches(&attrName);
- }
+ document()->clearNodeListCaches(&attrName);
}
void Node::invalidateNodeListsCacheAfterChildrenChanged()
@@ -989,20 +972,7 @@
if (hasRareData())
rareData()->clearChildNodeListCache();
- document()->clearNodeListCaches();
-
- 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();
- }
+ document()->clearNodeListCaches(0);
}
NodeListsNodeData* Node::nodeLists()
@@ -1548,8 +1518,8 @@
return 0;
if (document()->isHTMLDocument())
- return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<HTMLTagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
- return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<TagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
+ return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<HTMLTagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
+ return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<TagNodeList>(this, DynamicNodeList::TagNodeListType, localName);
}
PassRefPtr<NodeList> Node::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
@@ -1560,23 +1530,23 @@
if (namespaceURI == starAtom)
return getElementsByTagName(localName);
- return ensureRareData()->ensureNodeLists(this)->addCacheWithQualifiedName(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
+ return ensureRareData()->ensureNodeLists()->addCacheWithQualifiedName(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localName);
}
PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
{
- return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<NameNodeList>(this, DynamicNodeList::NameNodeListType, elementName);
+ return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<NameNodeList>(this, DynamicNodeList::NameNodeListType, elementName);
}
PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
{
- return ensureRareData()->ensureNodeLists(this)->addCacheWithName<ClassNodeList>(this, DynamicNodeList::ClassNodeListType, classNames);
+ return ensureRareData()->ensureNodeLists()->addCacheWithName<ClassNodeList>(this, DynamicNodeList::ClassNodeListType, classNames);
}
PassRefPtr<RadioNodeList> Node::radioNodeList(const AtomicString& name)
{
ASSERT(hasTagName(formTag) || hasTagName(fieldsetTag));
- return ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<RadioNodeList>(this, DynamicNodeList::RadioNodeListType, name);
+ return ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<RadioNodeList>(this, DynamicNodeList::RadioNodeListType, name);
}
PassRefPtr<Element> Node::querySelector(const AtomicString& selectors, ExceptionCode& ec)
@@ -2238,28 +2208,6 @@
// --------
-void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
-{
- NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
- for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
- if (!attrName || it->second->shouldInvalidateOnAttributeChange())
- it->second->invalidateCache();
- }
-
- NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
- for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
- if (!attrName || it->second->shouldInvalidateOnAttributeChange())
- it->second->invalidateCache();
- }
-
- if (!attrName)
- return;
-
- TagNodeListCacheNS::iterator tagCacheEnd = m_tagNodeListCacheNS.end();
- for (TagNodeListCacheNS::iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEnd; ++it)
- it->second->invalidateCache();
-}
-
void Node::getSubresourceURLs(ListHashSet<KURL>& urls) const
{
addSubresourceAttributeURLs(urls);
@@ -2754,12 +2702,9 @@
}
#endif
-void NodeRareData::createNodeLists(Node* node)
+void NodeRareData::createNodeLists()
{
- ASSERT(node);
setNodeLists(NodeListsNodeData::create());
- if (TreeScope* treeScope = node->treeScope())
- treeScope->addNodeListCache();
}
void NodeRareData::clearChildNodeListCache()
Modified: trunk/Source/WebCore/dom/NodeRareData.h (121105 => 121106)
--- trunk/Source/WebCore/dom/NodeRareData.h 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/NodeRareData.h 2012-06-24 03:13:19 UTC (rev 121106)
@@ -123,39 +123,36 @@
return adoptPtr(new NodeListsNodeData);
}
- void invalidateCaches(const QualifiedName* attrName = 0);
bool isEmpty() const
{
return m_atomicNameCaches.isEmpty() && m_nameCaches.isEmpty() && m_tagNodeListCacheNS.isEmpty();
}
- void adoptTreeScope(TreeScope* oldTreeScope, TreeScope* newTreeScope, Document* oldDocument, Document* newDocument)
+ void adoptTreeScope(Document* oldDocument, Document* newDocument)
{
- invalidateCaches();
-
- if (oldDocument != newDocument) {
- NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
- for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
- DynamicSubtreeNodeList* list = it->second;
- if (list->isRootedAtDocument()) {
- oldDocument->unregisterDynamicSubtreeNodeList(list);
- newDocument->registerDynamicSubtreeNodeList(list);
- }
+ NodeListAtomicNameCacheMap::const_iterator atomicNameCacheEnd = m_atomicNameCaches.end();
+ for (NodeListAtomicNameCacheMap::const_iterator it = m_atomicNameCaches.begin(); it != atomicNameCacheEnd; ++it) {
+ DynamicSubtreeNodeList* list = it->second;
+ list->invalidateCache();
+ if (oldDocument != newDocument && list->isRootedAtDocument()) {
+ oldDocument->unregisterDynamicSubtreeNodeList(list);
+ newDocument->registerDynamicSubtreeNodeList(list);
}
+ }
- NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
- for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
- DynamicSubtreeNodeList* list = it->second;
- if (list->isRootedAtDocument()) {
- oldDocument->unregisterDynamicSubtreeNodeList(list);
- newDocument->registerDynamicSubtreeNodeList(list);
- }
+ NodeListNameCacheMap::const_iterator nameCacheEnd = m_nameCaches.end();
+ for (NodeListNameCacheMap::const_iterator it = m_nameCaches.begin(); it != nameCacheEnd; ++it) {
+ DynamicSubtreeNodeList* list = it->second;
+ list->invalidateCache();
+ if (oldDocument != newDocument && list->isRootedAtDocument()) {
+ oldDocument->unregisterDynamicSubtreeNodeList(list);
+ newDocument->registerDynamicSubtreeNodeList(list);
}
}
- if (oldTreeScope)
- oldTreeScope->removeNodeListCache();
- newTreeScope->addNodeListCache();
+ TagNodeListCacheNS::iterator tagCacheEnd = m_tagNodeListCacheNS.end();
+ for (TagNodeListCacheNS::iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEnd; ++it)
+ it->second->invalidateCache();
}
private:
@@ -215,10 +212,10 @@
void clearNodeLists() { m_nodeLists.clear(); }
void setNodeLists(PassOwnPtr<NodeListsNodeData> lists) { m_nodeLists = lists; }
NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); }
- NodeListsNodeData* ensureNodeLists(Node* node)
+ NodeListsNodeData* ensureNodeLists()
{
if (!m_nodeLists)
- createNodeLists(node);
+ createNodeLists();
return m_nodeLists.get();
}
void clearChildNodeListCache();
@@ -348,7 +345,7 @@
void setNeedsFocusAppearanceUpdateSoonAfterAttach(bool needs) { m_needsFocusAppearanceUpdateSoonAfterAttach = needs; }
private:
- void createNodeLists(Node*);
+ void createNodeLists();
TreeScope* m_treeScope;
OwnPtr<NodeListsNodeData> m_nodeLists;
Modified: trunk/Source/WebCore/dom/TreeScope.cpp (121105 => 121106)
--- trunk/Source/WebCore/dom/TreeScope.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/TreeScope.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -54,7 +54,6 @@
TreeScope::TreeScope(ContainerNode* rootNode)
: m_rootNode(rootNode)
, m_parentTreeScope(0)
- , m_numNodeListCaches(0)
{
ASSERT(rootNode);
}
Modified: trunk/Source/WebCore/dom/TreeScope.h (121105 => 121106)
--- trunk/Source/WebCore/dom/TreeScope.h 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/TreeScope.h 2012-06-24 03:13:19 UTC (rev 121106)
@@ -61,10 +61,6 @@
void removeImageMap(HTMLMapElement*);
HTMLMapElement* getImageMap(const String& url) const;
- void addNodeListCache() { ++m_numNodeListCaches; }
- void removeNodeListCache() { ASSERT(m_numNodeListCaches > 0); --m_numNodeListCaches; }
- bool hasNodeListCaches() const { return m_numNodeListCaches; }
-
DOMSelection* getSelection() const;
// Find first anchor with the given name.
@@ -95,8 +91,6 @@
DocumentOrderedMap m_elementsById;
DocumentOrderedMap m_imageMapsByName;
- unsigned m_numNodeListCaches;
-
mutable RefPtr<DOMSelection> m_selection;
};
Modified: trunk/Source/WebCore/dom/TreeScopeAdopter.cpp (121105 => 121106)
--- trunk/Source/WebCore/dom/TreeScopeAdopter.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/dom/TreeScopeAdopter.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -54,7 +54,7 @@
for (Node* node = root; node; node = node->traverseNextNode(root)) {
NodeRareData* rareData = node->setTreeScope(newDocument == m_newScope ? 0 : m_newScope);
if (rareData && rareData->nodeLists())
- rareData->nodeLists()->adoptTreeScope(m_oldScope, m_newScope, oldDocument, newDocument);
+ rareData->nodeLists()->adoptTreeScope(oldDocument, newDocument);
if (willMoveToNewDocument)
moveNodeToNewDocument(node, oldDocument, newDocument);
Modified: trunk/Source/WebCore/html/LabelableElement.cpp (121105 => 121106)
--- trunk/Source/WebCore/html/LabelableElement.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/html/LabelableElement.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -47,7 +47,7 @@
if (!document())
return 0;
- return Node::ensureRareData()->ensureNodeLists(this)->addCacheWithAtomicName<LabelsNodeList>(this, DynamicNodeList::LabelsNodeListType, starAtom);
+ return Node::ensureRareData()->ensureNodeLists()->addCacheWithAtomicName<LabelsNodeList>(this, DynamicNodeList::LabelsNodeListType, starAtom);
}
} // namespace Webcore
Modified: trunk/Source/WebCore/html/LabelsNodeList.cpp (121105 => 121106)
--- trunk/Source/WebCore/html/LabelsNodeList.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/html/LabelsNodeList.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -36,13 +36,11 @@
LabelsNodeList::LabelsNodeList(Node* forNode)
: DynamicSubtreeNodeList(forNode, RootedAtDocument)
{
- document()->registerDynamicSubtreeNodeList(this);
}
LabelsNodeList::~LabelsNodeList()
{
ownerNode()->nodeLists()->removeCacheWithAtomicName(this, DynamicNodeList::LabelsNodeListType, starAtom);
- document()->unregisterDynamicSubtreeNodeList(this);
}
bool LabelsNodeList::nodeMatches(Element* testNode) const
Modified: trunk/Source/WebCore/html/RadioNodeList.cpp (121105 => 121106)
--- trunk/Source/WebCore/html/RadioNodeList.cpp 2012-06-23 23:00:53 UTC (rev 121105)
+++ trunk/Source/WebCore/html/RadioNodeList.cpp 2012-06-24 03:13:19 UTC (rev 121106)
@@ -41,13 +41,11 @@
: DynamicSubtreeNodeList(rootNode, rootNode->hasTagName(formTag) ? RootedAtDocument : RootedAtNode)
, m_name(name)
{
- document()->registerDynamicSubtreeNodeList(this);
}
RadioNodeList::~RadioNodeList()
{
ownerNode()->nodeLists()->removeCacheWithAtomicName(this, DynamicNodeList::RadioNodeListType, m_name);
- document()->unregisterDynamicSubtreeNodeList(this);
}
static inline HTMLInputElement* toRadioButtonInputElement(Node* node)