Reviewed by Kevin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 13 Nov 2004 01:12:18 +0000 (01:12 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 13 Nov 2004 01:12:18 +0000 (01:12 +0000)
- fixed <rdar://problem/3878183> 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
WebCore/khtml/xml/dom_nodeimpl.cpp
WebCore/khtml/xml/dom_nodeimpl.h

index 3e4b49208052d74e4417c2596c5caf1f47e09927..fc6f71b63e556e3b5acd1806f6b1bab652b9ccca 100644 (file)
@@ -1,3 +1,39 @@
+2004-11-12  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Kevin.
+
+       - fixed <rdar://problem/3878183> 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  <darin@apple.com>
 
         Reviewed by Maciej.
index 2e909a8534cfa381d2528a538ddc2834cddd7775..4cdeeb93312836b57d4cbc83881e7d0b3bbefaf3 100644 (file)
@@ -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<NodeListImpl>;
+    }
+
+    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<NodeListImpl> 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
index 685efd5daf41ce6207f650d11bd683768207af7c..1491a2238acd669daef6f1742e7c70b03f255e7c 100644 (file)
@@ -34,6 +34,7 @@
 
 class QPainter;
 template <class type> class QPtrList;
+template <class type> 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<RegisteredEventListener> *m_regdListeners;
+    QPtrDict<NodeListImpl> *m_nodeLists;
 
     unsigned short m_tabIndex : 15;
     bool m_hasTabIndex  : 1;
@@ -546,29 +553,35 @@ class NodeImpl;
 class NodeListImpl : public khtml::Shared<NodeListImpl>
 {
 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;
 };