Reviewed by Darin.
authorap <ap@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 22 Apr 2007 08:23:55 +0000 (08:23 +0000)
committerap <ap@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 22 Apr 2007 08:23:55 +0000 (08:23 +0000)
        http://bugs.webkit.org/show_bug.cgi?id=13115
        REGRESSION: 1000% performance regression in DOM access by index, which was already slow

        * dom/NodeList.h: Move cached data into a separate class, so it can be shared.

        * dom/Node.h: Replace the set of registered NodeLists with a struct that also
        contains a shared NodeList::Caches (so the size of Node doesn't change).

        * dom/NodeList.cpp:
        (WebCore::NodeList::NodeList):
        (WebCore::NodeList::~NodeList):
        (WebCore::NodeList::recursiveLength):
        (WebCore::NodeList::itemForwardsFromCurrent):
        (WebCore::NodeList::itemBackwardsFromCurrent):
        (WebCore::NodeList::recursiveItem):
        (WebCore::NodeList::itemWithName):
        (WebCore::NodeList::rootNodeChildrenChanged):
        (WebCore::NodeList::NodeListInfo::NodeListInfo):
        (WebCore::NodeList::NodeListInfo::reset):
        * dom/ChildNodeList.cpp:
        (WebCore::ChildNodeList::ChildNodeList):
        (WebCore::ChildNodeList::length):
        (WebCore::ChildNodeList::item):
        (WebCore::ChildNodeList::nodeMatches):
        * dom/ChildNodeList.h:
        * dom/Node.cpp:
        (WebCore::Node::childNodes):
        (WebCore::Node::registerNodeList):
        (WebCore::Node::unregisterNodeList):
        (WebCore::Node::notifyLocalNodeListsAttributeChanged):
        (WebCore::Node::notifyLocalNodeListsChildrenChanged):
        Adjust for the above changes.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@21003 268f45cc-cd09-0410-ab3c-d52691b4dbfc

WebCore/ChangeLog
WebCore/dom/ChildNodeList.cpp
WebCore/dom/ChildNodeList.h
WebCore/dom/Node.cpp
WebCore/dom/Node.h
WebCore/dom/NodeList.cpp
WebCore/dom/NodeList.h

index 764a782..2437486 100644 (file)
@@ -1,3 +1,40 @@
+2007-04-22  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        http://bugs.webkit.org/show_bug.cgi?id=13115
+        REGRESSION: 1000% performance regression in DOM access by index, which was already slow
+
+        * dom/NodeList.h: Move cached data into a separate class, so it can be shared.
+
+        * dom/Node.h: Replace the set of registered NodeLists with a struct that also
+        contains a shared NodeList::Caches (so the size of Node doesn't change).
+
+        * dom/NodeList.cpp:
+        (WebCore::NodeList::NodeList):
+        (WebCore::NodeList::~NodeList):
+        (WebCore::NodeList::recursiveLength):
+        (WebCore::NodeList::itemForwardsFromCurrent):
+        (WebCore::NodeList::itemBackwardsFromCurrent):
+        (WebCore::NodeList::recursiveItem):
+        (WebCore::NodeList::itemWithName):
+        (WebCore::NodeList::rootNodeChildrenChanged):
+        (WebCore::NodeList::NodeListInfo::NodeListInfo):
+        (WebCore::NodeList::NodeListInfo::reset):
+        * dom/ChildNodeList.cpp:
+        (WebCore::ChildNodeList::ChildNodeList):
+        (WebCore::ChildNodeList::length):
+        (WebCore::ChildNodeList::item):
+        (WebCore::ChildNodeList::nodeMatches):
+        * dom/ChildNodeList.h:
+        * dom/Node.cpp:
+        (WebCore::Node::childNodes):
+        (WebCore::Node::registerNodeList):
+        (WebCore::Node::unregisterNodeList):
+        (WebCore::Node::notifyLocalNodeListsAttributeChanged):
+        (WebCore::Node::notifyLocalNodeListsChildrenChanged):
+        Adjust for the above changes.
+
 2007-04-21  Mitz Pettel  <mitz@webkit.org>
 
         Reviewed by Darin.
index 604eb99..c3fdf11 100644 (file)
@@ -30,38 +30,38 @@ using namespace WebCore;
 
 namespace WebCore {
 
-ChildNodeList::ChildNodeList( Node *n )
-    : NodeList(n)
+ChildNodeList::ChildNodeList(Node* n, NodeList::Caches* info)
+    : NodeList(n, info)
 {
 }
 
 unsigned ChildNodeList::length() const
 {
-    if (isLengthCacheValid)
-        return cachedLength;
+    if (m_caches->isLengthCacheValid)
+        return m_caches->cachedLength;
 
     unsigned len = 0;
     Node *n;
-    for(n = rootNode->firstChild(); n != 0; n = n->nextSibling())
+    for (n = m_rootNode->firstChild(); n != 0; n = n->nextSibling())
         len++;
 
-    cachedLength = len;
-    isLengthCacheValid = true;
+    m_caches->cachedLength = len;
+    m_caches->isLengthCacheValid = true;
 
     return len;
 }
 
-Node *ChildNodeList::item ( unsigned index ) const
+Node *ChildNodeList::item(unsigned index) const
 {
     unsigned int pos = 0;
-    Node *n = rootNode->firstChild();
+    Node *n = m_rootNode->firstChild();
 
-    if (isItemCacheValid) {
-        if (index == lastItemOffset) {
-            return lastItem;
-        } else if (index > lastItemOffset) {
-            n = lastItem;
-            pos = lastItemOffset;
+    if (m_caches->isItemCacheValid) {
+        if (index == m_caches->lastItemOffset)
+            return m_caches->lastItem;
+        if (index > m_caches->lastItemOffset) {
+            n = m_caches->lastItem;
+            pos = m_caches->lastItemOffset;
         }
     }
 
@@ -71,9 +71,9 @@ Node *ChildNodeList::item ( unsigned index ) const
     }
 
     if (n) {
-        lastItem = n;
-        lastItemOffset = pos;
-        isItemCacheValid = true;
+        m_caches->lastItem = n;
+        m_caches->lastItemOffset = pos;
+        m_caches->isItemCacheValid = true;
         return n;
     }
 
@@ -82,7 +82,7 @@ Node *ChildNodeList::item ( unsigned index ) const
 
 bool ChildNodeList::nodeMatches(Node *testNode) const
 {
-    return testNode->parentNode() == rootNode;
+    return testNode->parentNode() == m_rootNode;
 }
 
 }
index 56aa447..1165c85 100644 (file)
@@ -31,7 +31,7 @@ namespace WebCore {
 
 class ChildNodeList : public NodeList {
 public:
-    ChildNodeList(Node*);
+    ChildNodeList(Node*, NodeList::Caches*);
 
     virtual unsigned length() const;
     virtual Node* item(unsigned index) const;
index 52c1599..242f44d 100644 (file)
@@ -47,6 +47,13 @@ namespace WebCore {
 
 using namespace HTMLNames;
 
+typedef HashSet<NodeList*> NodeListSet;
+struct NodeListsNodeData {
+    NodeListSet m_registeredLists;
+    NodeList::Caches m_childNodeListCaches;
+};
+
+
 /**
  * NodeList which lists all Nodes in a document with a given tag name
  */
@@ -215,7 +222,10 @@ void Node::setNodeValue( const String &/*_nodeValue*/, ExceptionCode& ec)
 
 PassRefPtr<NodeList> Node::childNodes()
 {
-    return new ChildNodeList(this);
+    if (!m_nodeLists)
+        m_nodeLists = new NodeListsNodeData;
+
+    return new ChildNodeList(this, &m_nodeLists->m_childNodeListCaches);
 }
 
 Node *Node::firstChild() const
@@ -430,15 +440,15 @@ unsigned Node::nodeIndex() const
 void Node::registerNodeList(NodeList* list)
 {
     if (!m_nodeLists)
-        m_nodeLists = new NodeListSet;
-    m_nodeLists->add(list);
+        m_nodeLists = new NodeListsNodeData;
+    m_nodeLists->m_registeredLists.add(list);
 }
 
 void Node::unregisterNodeList(NodeList* list)
 {
     if (!m_nodeLists)
         return;
-    m_nodeLists->remove(list);
+    m_nodeLists->m_registeredLists.remove(list);
 }
 
 void Node::notifyLocalNodeListsAttributeChanged()
@@ -446,8 +456,8 @@ void Node::notifyLocalNodeListsAttributeChanged()
     if (!m_nodeLists)
         return;
 
-    NodeListSet::iterator end = m_nodeLists->end();
-    for (NodeListSet::iterator i = m_nodeLists->begin(); i != end; ++i)
+    NodeListSet::iterator end = m_nodeLists->m_registeredLists.end();
+    for (NodeListSet::iterator i = m_nodeLists->m_registeredLists.begin(); i != end; ++i)
         (*i)->rootNodeAttributeChanged();
 }
 
@@ -462,8 +472,8 @@ void Node::notifyLocalNodeListsChildrenChanged()
     if (!m_nodeLists)
         return;
 
-    NodeListSet::iterator end = m_nodeLists->end();
-    for (NodeListSet::iterator i = m_nodeLists->begin(); i != end; ++i)
+    NodeListSet::iterator end = m_nodeLists->m_registeredLists.end();
+    for (NodeListSet::iterator i = m_nodeLists->m_registeredLists.begin(); i != end; ++i)
         (*i)->rootNodeChildrenChanged();
 }
 
index 3dfaee4..3962dc4 100644 (file)
@@ -45,6 +45,7 @@ class IntRect;
 class KeyboardEvent;
 class NamedAttrMap;
 class NodeList;
+struct NodeListsNodeData;
 class PlatformKeyboardEvent;
 class PlatformMouseEvent;
 class PlatformWheelEvent;
@@ -456,8 +457,7 @@ private: // members
     RenderObject* m_renderer;
 
 protected:
-    typedef HashSet<NodeList*> NodeListSet;
-    NodeListSet* m_nodeLists;
+    NodeListsNodeData* m_nodeLists;
 
     short m_tabIndex;
 
index 2191dfd..9232a55 100644 (file)
 
 namespace WebCore {
 
-NodeList::NodeList(PassRefPtr<Node> _rootNode)
-    : rootNode(_rootNode),
-      isLengthCacheValid(false),
-      isItemCacheValid(false)
+NodeList::NodeList(PassRefPtr<Node> rootNode)
+    : m_rootNode(rootNode)
+    , m_caches(new Caches)
+    , m_ownsCaches(true)
 {
-    rootNode->registerNodeList(this);
+    m_rootNode->registerNodeList(this);
+}    
+
+NodeList::NodeList(PassRefPtr<Node> rootNode, NodeList::Caches* info)
+    : m_rootNode(rootNode)
+    , m_caches(info)
+    , m_ownsCaches(false)
+{
+    m_rootNode->registerNodeList(this);
 }    
 
 NodeList::~NodeList()
 {
-    rootNode->unregisterNodeList(this);
+    m_rootNode->unregisterNodeList(this);
+    if (m_ownsCaches)
+        delete m_caches;
 }
 
 unsigned NodeList::recursiveLength(Node* start) const
 {
     if (!start)
-        start = rootNode.get();
+        start = m_rootNode.get();
 
-    if (isLengthCacheValid && start == rootNode)
-        return cachedLength;
+    if (m_caches->isLengthCacheValid && start == m_rootNode)
+        return m_caches->cachedLength;
 
     unsigned len = 0;
 
@@ -60,9 +70,9 @@ unsigned NodeList::recursiveLength(Node* start) const
             len += recursiveLength(n);
         }
 
-    if (start == rootNode) {
-        cachedLength = len;
-        isLengthCacheValid = true;
+    if (start == m_rootNode) {
+        m_caches->cachedLength = len;
+        m_caches->isLengthCacheValid = true;
     }
 
     return len;
@@ -72,13 +82,13 @@ Node* NodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remain
 {
     ASSERT(remainingOffset >= 0);
 
-    for (Node *n = start; n; n = n->traverseNextNode(rootNode.get())) {
+    for (Node *n = start; n; n = n->traverseNextNode(m_rootNode.get())) {
         if (n->isElementNode()) {
             if (nodeMatches(n)) {
                 if (!remainingOffset) {
-                    lastItem = n;
-                    lastItemOffset = offset;
-                    isItemCacheValid = true;
+                    m_caches->lastItem = n;
+                    m_caches->lastItemOffset = offset;
+                    m_caches->isItemCacheValid = true;
                     return n;
                 }
                 remainingOffset--;
@@ -92,13 +102,13 @@ Node* NodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remain
 Node* NodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
 {
     ASSERT(remainingOffset < 0);
-    for (Node *n = start; n; n = n->traversePreviousNode(rootNode.get())) {
+    for (Node *n = start; n; n = n->traversePreviousNode(m_rootNode.get())) {
         if (n->isElementNode()) {
             if (nodeMatches(n)) {
                 if (!remainingOffset) {
-                    lastItem = n;
-                    lastItemOffset = offset;
-                    isItemCacheValid = true;
+                    m_caches->lastItem = n;
+                    m_caches->lastItemOffset = offset;
+                    m_caches->isItemCacheValid = true;
                     return n;
                 }
                 remainingOffset++;
@@ -113,13 +123,13 @@ Node* NodeList::recursiveItem(unsigned offset, Node* start) const
 {
     int remainingOffset = offset;
     if (!start) {
-        start = rootNode->firstChild();
-        if (isItemCacheValid) {
-            if (offset == lastItemOffset) {
-                return lastItem;
-            } else if (offset > lastItemOffset || lastItemOffset - offset < offset) {
-                start = lastItem;
-                remainingOffset -= lastItemOffset;
+        start = m_rootNode->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;
             }
         }
     }
@@ -132,14 +142,14 @@ Node* NodeList::recursiveItem(unsigned offset, Node* start) const
 
 Node* NodeList::itemWithName(const AtomicString& elementId) const
 {
-    if (rootNode->isDocumentNode() || rootNode->inDocument()) {
-        Node* node = rootNode->document()->getElementById(elementId);
+    if (m_rootNode->isDocumentNode() || m_rootNode->inDocument()) {
+        Node* node = m_rootNode->document()->getElementById(elementId);
 
         if (!node || !nodeMatches(node))
             return 0;
 
         for (Node* p = node->parentNode(); p; p = p->parentNode())
-            if (p == rootNode)
+            if (p == m_rootNode)
                 return node;
 
         return 0;
@@ -157,9 +167,22 @@ Node* NodeList::itemWithName(const AtomicString& elementId) const
 
 void NodeList::rootNodeChildrenChanged()
 {
+    m_caches->reset();
+}
+
+
+NodeList::Caches::Caches()
+    : lastItem(0)
+    , isLengthCacheValid(false)
+    , isItemCacheValid(false)
+{
+}
+
+void NodeList::Caches::reset()
+{
+    lastItem = 0;
     isLengthCacheValid = false;
     isItemCacheValid = false;     
-    lastItem = 0;
 }
 
 }
index 6c031e2..1f5362a 100644 (file)
@@ -37,7 +37,20 @@ class Node;
 
 class NodeList : public Shared<NodeList> {
 public:
+
+    struct Caches {
+        Caches();
+        void reset();
+        
+        int cachedLength;
+        Node* lastItem;
+        unsigned lastItemOffset;
+        bool isLengthCacheValid : 1;
+        bool isItemCacheValid : 1;
+    };
+
     NodeList(PassRefPtr<Node> rootNode);
+    NodeList(PassRefPtr<Node> rootNode, Caches*);
     virtual ~NodeList();
 
     // DOM methods & attributes for NodeList
@@ -55,12 +68,9 @@ protected:
     Node* recursiveItem (unsigned offset, Node* start = 0) const;
     virtual bool nodeMatches(Node* testNode) const = 0;
 
-    RefPtr<Node> rootNode;
-    mutable int cachedLength;
-    mutable Node* lastItem;
-    mutable unsigned lastItemOffset;
-    mutable bool isLengthCacheValid : 1;
-    mutable bool isItemCacheValid : 1;
+    RefPtr<Node> m_rootNode;
+    mutable Caches* m_caches;
+    bool m_ownsCaches;
 
  private:
     Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;