From 65c4b90269de2ef42024dd337614faa894025653 Mon Sep 17 00:00:00 2001 From: mjs Date: Sat, 13 Nov 2004 01:12:18 +0000 Subject: [PATCH] Reviewed by Kevin. - fixed Safari is 77% slower than it should be on a page on an IBM website due to NodeListImpl length I fixed this by changing NodeLists to cache their length, but invalidate it whenever there is a change in the DOM subtree at which they are rooted. This makes NodeListImpl::recursiveLength() drop completely off the profile, since we were repeatedly getting a length for the same NodeList over and over. * khtml/xml/dom_nodeimpl.cpp: (NodeImpl::NodeImpl): (NodeImpl::~NodeImpl): (NodeImpl::registerNodeList): (NodeImpl::unregisterNodeList): (NodeImpl::notifyLocalNodeListsSubtreeModified): (NodeImpl::notifyNodeListsSubtreeModified): (NodeImpl::dispatchSubtreeModifiedEvent): (NodeListImpl::NodeListImpl): (NodeListImpl::~NodeListImpl): (NodeListImpl::recursiveLength): (NodeListImpl::recursiveItem): (NodeListImpl::rootNodeSubtreeModified): (ChildNodeListImpl::ChildNodeListImpl): (ChildNodeListImpl::length): (ChildNodeListImpl::item): (TagNodeListImpl::TagNodeListImpl): (TagNodeListImpl::length): (TagNodeListImpl::item): (NameNodeListImpl::NameNodeListImpl): (NameNodeListImpl::length): (NameNodeListImpl::item): * khtml/xml/dom_nodeimpl.h: git-svn-id: https://svn.webkit.org/repository/webkit/trunk@7997 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- WebCore/ChangeLog-2005-08-23 | 36 +++++++++ WebCore/khtml/xml/dom_nodeimpl.cpp | 113 ++++++++++++++++++++--------- WebCore/khtml/xml/dom_nodeimpl.h | 31 +++++--- 3 files changed, 134 insertions(+), 46 deletions(-) diff --git a/WebCore/ChangeLog-2005-08-23 b/WebCore/ChangeLog-2005-08-23 index 3e4b49208052..fc6f71b63e55 100644 --- a/WebCore/ChangeLog-2005-08-23 +++ b/WebCore/ChangeLog-2005-08-23 @@ -1,3 +1,39 @@ +2004-11-12 Maciej Stachowiak + + Reviewed by Kevin. + + - fixed Safari is 77% slower than it should be on a page on an IBM website due to NodeListImpl length + + I fixed this by changing NodeLists to cache their length, but + invalidate it whenever there is a change in the DOM subtree at + which they are rooted. This makes NodeListImpl::recursiveLength() + drop completely off the profile, since we were repeatedly getting + a length for the same NodeList over and over. + + * khtml/xml/dom_nodeimpl.cpp: + (NodeImpl::NodeImpl): + (NodeImpl::~NodeImpl): + (NodeImpl::registerNodeList): + (NodeImpl::unregisterNodeList): + (NodeImpl::notifyLocalNodeListsSubtreeModified): + (NodeImpl::notifyNodeListsSubtreeModified): + (NodeImpl::dispatchSubtreeModifiedEvent): + (NodeListImpl::NodeListImpl): + (NodeListImpl::~NodeListImpl): + (NodeListImpl::recursiveLength): + (NodeListImpl::recursiveItem): + (NodeListImpl::rootNodeSubtreeModified): + (ChildNodeListImpl::ChildNodeListImpl): + (ChildNodeListImpl::length): + (ChildNodeListImpl::item): + (TagNodeListImpl::TagNodeListImpl): + (TagNodeListImpl::length): + (TagNodeListImpl::item): + (NameNodeListImpl::NameNodeListImpl): + (NameNodeListImpl::length): + (NameNodeListImpl::item): + * khtml/xml/dom_nodeimpl.h: + 2004-11-12 Darin Adler Reviewed by Maciej. diff --git a/WebCore/khtml/xml/dom_nodeimpl.cpp b/WebCore/khtml/xml/dom_nodeimpl.cpp index 2e909a8534cf..4cdeeb933128 100644 --- a/WebCore/khtml/xml/dom_nodeimpl.cpp +++ b/WebCore/khtml/xml/dom_nodeimpl.cpp @@ -71,6 +71,7 @@ NodeImpl::NodeImpl(DocumentPtr *doc) m_next(0), m_render(0), m_regdListeners( 0 ), + m_nodeLists( 0 ), m_tabIndex( 0 ), m_hasId( false ), m_hasClass( false ), @@ -109,6 +110,7 @@ NodeImpl::~NodeImpl() if (m_render) detach(); delete m_regdListeners; + delete m_nodeLists; if (document) document->deref(); if (m_previous) @@ -831,8 +833,45 @@ bool NodeImpl::dispatchUIEvent(int _id, int detail) return dispatchEvent(evt,exceptioncode,true); } +void NodeImpl::registerNodeList(NodeListImpl *list) +{ + if (!m_nodeLists) { + m_nodeLists = new QPtrDict; + } + + m_nodeLists->insert(list, list); +} + +void NodeImpl::unregisterNodeList(NodeListImpl *list) +{ + if (!m_nodeLists) + return; + + m_nodeLists->remove(list); +} + +void NodeImpl::notifyLocalNodeListsSubtreeModified() +{ + if (!m_nodeLists) + return; + + QPtrDictIterator i(*m_nodeLists); + + while (NodeListImpl *list = i.current()) { + list->rootNodeSubtreeModified(); + } +} + +void NodeImpl::notifyNodeListsSubtreeModified() +{ + for (NodeImpl *n = this; n; n = n->parentNode()) { + n->notifyLocalNodeListsSubtreeModified(); + } +} + bool NodeImpl::dispatchSubtreeModifiedEvent() { + notifyNodeListsSubtreeModified(); childrenChanged(); if (!getDocument()->hasListenerType(DocumentImpl::DOMSUBTREEMODIFIED_LISTENER)) return false; @@ -2170,18 +2209,29 @@ void NodeBaseImpl::dispatchChildRemovalEvents( NodeImpl *child, int &exceptionco // --------------------------------------------------------------------------- -NodeImpl *NodeListImpl::item( unsigned long /*index*/ ) const + +NodeListImpl::NodeListImpl(NodeImpl *_rootNode) { - return 0; -} + rootNode = _rootNode; + rootNode->ref(); + rootNode->registerNodeList(this); +} -unsigned long NodeListImpl::length() const +NodeListImpl::~NodeListImpl() { - return 0; + rootNode->unregisterNodeList(this); + rootNode->deref(); } -unsigned long NodeListImpl::recursiveLength(NodeImpl *start) const +unsigned long NodeListImpl::recursiveLength( NodeImpl *start ) const { + if (!start) + start = rootNode; + + if (isCacheValid && start == rootNode) { + return cachedLength; + } + unsigned long len = 0; for(NodeImpl *n = start->firstChild(); n != 0; n = n->nextSibling()) { @@ -2192,18 +2242,26 @@ unsigned long NodeListImpl::recursiveLength(NodeImpl *start) const } } + if (start == rootNode) { + cachedLength = len; + isCacheValid = true; + } + return len; } -NodeImpl *NodeListImpl::recursiveItem ( NodeImpl *start, unsigned long &offset ) const +NodeImpl *NodeListImpl::recursiveItem ( unsigned long &offset, NodeImpl *start ) const { + if (!start) + start = rootNode; + for(NodeImpl *n = start->firstChild(); n != 0; n = n->nextSibling()) { if ( n->nodeType() == Node::ELEMENT_NODE ) { if (nodeMatches(n)) if (!offset--) return n; - NodeImpl *depthSearch= recursiveItem(n, offset); + NodeImpl *depthSearch= recursiveItem(offset, n); if (depthSearch) return depthSearch; } @@ -2212,22 +2270,22 @@ NodeImpl *NodeListImpl::recursiveItem ( NodeImpl *start, unsigned long &offset ) return 0; // no matching node in this subtree } -ChildNodeListImpl::ChildNodeListImpl( NodeImpl *n ) +void NodeListImpl::rootNodeSubtreeModified() { - refNode = n; - refNode->ref(); + isCacheValid = false; } -ChildNodeListImpl::~ChildNodeListImpl() + +ChildNodeListImpl::ChildNodeListImpl( NodeImpl *n ) + : NodeListImpl(n) { - refNode->deref(); } unsigned long ChildNodeListImpl::length() const { unsigned long len = 0; NodeImpl *n; - for(n = refNode->firstChild(); n != 0; n = n->nextSibling()) + for(n = rootNode->firstChild(); n != 0; n = n->nextSibling()) len++; return len; @@ -2236,7 +2294,7 @@ unsigned long ChildNodeListImpl::length() const NodeImpl *ChildNodeListImpl::item ( unsigned long index ) const { unsigned int pos = 0; - NodeImpl *n = refNode->firstChild(); + NodeImpl *n = rootNode->firstChild(); while( n != 0 && pos < index ) { @@ -2253,24 +2311,18 @@ bool ChildNodeListImpl::nodeMatches( NodeImpl */*testNode*/ ) const } TagNodeListImpl::TagNodeListImpl(NodeImpl *n, NodeImpl::Id _id, NodeImpl::Id _idMask ) - : refNode(n), m_id(_id & _idMask), m_idMask(_idMask) -{ - refNode->ref(); -} - -TagNodeListImpl::~TagNodeListImpl() + : NodeListImpl(n), m_id(_id & _idMask), m_idMask(_idMask) { - refNode->deref(); } unsigned long TagNodeListImpl::length() const { - return recursiveLength( refNode ); + return recursiveLength(); } NodeImpl *TagNodeListImpl::item ( unsigned long index ) const { - return recursiveItem( refNode, index ); + return recursiveItem( index ); } bool TagNodeListImpl::nodeMatches( NodeImpl *testNode ) const @@ -2280,25 +2332,18 @@ bool TagNodeListImpl::nodeMatches( NodeImpl *testNode ) const } NameNodeListImpl::NameNodeListImpl(NodeImpl *n, const DOMString &t ) - : nodeName(t) -{ - refNode= n; - refNode->ref(); -} - -NameNodeListImpl::~NameNodeListImpl() + : NodeListImpl(n), nodeName(t) { - refNode->deref(); } unsigned long NameNodeListImpl::length() const { - return recursiveLength( refNode ); + return recursiveLength(); } NodeImpl *NameNodeListImpl::item ( unsigned long index ) const { - return recursiveItem( refNode, index ); + return recursiveItem( index ); } bool NameNodeListImpl::nodeMatches( NodeImpl *testNode ) const diff --git a/WebCore/khtml/xml/dom_nodeimpl.h b/WebCore/khtml/xml/dom_nodeimpl.h index 685efd5daf41..1491a2238acd 100644 --- a/WebCore/khtml/xml/dom_nodeimpl.h +++ b/WebCore/khtml/xml/dom_nodeimpl.h @@ -34,6 +34,7 @@ class QPainter; template class QPtrList; +template class QPtrDict; class KHTMLView; class RenderArena; class QRect; @@ -448,6 +449,11 @@ public: virtual void formatForDebugger(char *buffer, unsigned length) const; #endif + void registerNodeList(NodeListImpl *list); + void unregisterNodeList(NodeListImpl *list); + void notifyNodeListsSubtreeModified(); + void notifyLocalNodeListsSubtreeModified(); + private: // members DocumentPtr *document; NodeImpl *m_previous; @@ -455,6 +461,7 @@ private: // members protected: khtml::RenderObject *m_render; QPtrList *m_regdListeners; + QPtrDict *m_nodeLists; unsigned short m_tabIndex : 15; bool m_hasTabIndex : 1; @@ -546,29 +553,35 @@ class NodeImpl; class NodeListImpl : public khtml::Shared { public: - virtual ~NodeListImpl() {} + NodeListImpl( NodeImpl *_rootNode ); + virtual ~NodeListImpl(); // DOM methods & attributes for NodeList - virtual unsigned long length() const; - virtual NodeImpl *item ( unsigned long index ) const; + virtual unsigned long length() const = 0; + virtual NodeImpl *item ( unsigned long index ) const = 0; // Other methods (not part of DOM) + void rootNodeSubtreeModified(); + #if APPLE_CHANGES static NodeList createInstance(NodeListImpl *impl); #endif protected: // helper functions for searching all ElementImpls in a tree - unsigned long recursiveLength(NodeImpl *start) const; - NodeImpl *recursiveItem ( NodeImpl *start, unsigned long &offset ) const; + unsigned long recursiveLength(NodeImpl *start = 0) const; + NodeImpl *recursiveItem ( unsigned long &offset, NodeImpl *start = 0 ) const; virtual bool nodeMatches( NodeImpl *testNode ) const = 0; + + NodeImpl *rootNode; + mutable int cachedLength; + mutable bool isCacheValid; }; class ChildNodeListImpl : public NodeListImpl { public: ChildNodeListImpl( NodeImpl *n); - virtual ~ChildNodeListImpl(); // DOM methods overridden from parent classes @@ -577,8 +590,6 @@ public: protected: virtual bool nodeMatches( NodeImpl *testNode ) const; - - NodeImpl *refNode; }; @@ -589,7 +600,6 @@ class TagNodeListImpl : public NodeListImpl { public: TagNodeListImpl( NodeImpl *n, NodeImpl::Id tagId, NodeImpl::Id tagIdMask ); - virtual ~TagNodeListImpl(); // DOM methods overridden from parent classes @@ -601,7 +611,6 @@ public: protected: virtual bool nodeMatches( NodeImpl *testNode ) const; - NodeImpl *refNode; NodeImpl::Id m_id; NodeImpl::Id m_idMask; }; @@ -614,7 +623,6 @@ class NameNodeListImpl : public NodeListImpl { public: NameNodeListImpl( NodeImpl *doc, const DOMString &t ); - virtual ~NameNodeListImpl(); // DOM methods overridden from parent classes @@ -626,7 +634,6 @@ public: protected: virtual bool nodeMatches( NodeImpl *testNode ) const; - NodeImpl *refNode; DOMString nodeName; }; -- 2.36.0