Changeset 21003 in webkit

Timestamp:

Apr 22, 2007 1:23:55 AM (17 years ago)

Author:

ap

Message:

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.

Location:

trunk/WebCore

Files:

• ChangeLog (modified) (1 diff)
• dom/ChildNodeList.cpp (modified) (4 diffs)
• dom/ChildNodeList.h (modified) (1 diff)
• dom/Node.cpp (modified) (6 diffs)
• dom/Node.h (modified) (2 diffs)
• dom/NodeList.cpp (modified) (9 diffs)
• dom/NodeList.h (modified) (2 diffs)

trunk/WebCore/ChangeLog

@@ +1 @@
+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>
 

trunk/WebCore/dom/ChildNodeList.cpp

@@ -31 +31 @@
 namespace WebCore {
 
-ChildNodeList::ChildNodeList( Node *n )
-    : NodeList(n)
+ChildNodeList::ChildNodeList(Node* n, NodeList::Caches* info)
+    : NodeList(n, info)
 {
 }
@@ -38 +38 @@
 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;
         }
     }
@@ -72 +72 @@
 
     if (n) {
-        lastItem = n;
-        lastItemOffset = pos;
-        isItemCacheValid = true;
+        m_caches->lastItem = n;
+        m_caches->lastItemOffset = pos;
+        m_caches->isItemCacheValid = true;
         return n;
     }
@@ -83 +83 @@
 bool ChildNodeList::nodeMatches(Node *testNode) const
 {
-    return testNode->parentNode() == rootNode;
+    return testNode->parentNode() == m_rootNode;
 }
 

trunk/WebCore/dom/ChildNodeList.h

@@ -32 +32 @@
 class ChildNodeList : public NodeList {
 public:
-    ChildNodeList(Node*);
+    ChildNodeList(Node*, NodeList::Caches*);
 
     virtual unsigned length() const;

trunk/WebCore/dom/Node.cpp

@@ -48 +48 @@
 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
@@ -216 +223 @@
 PassRefPtr<NodeList> Node::childNodes()
 {
-    return new ChildNodeList(this);
+    if (!m_nodeLists)
+        m_nodeLists = new NodeListsNodeData;
+
+    return new ChildNodeList(this, &m_nodeLists->m_childNodeListCaches);
 }
 
@@ -431 +441 @@
 {
     if (!m_nodeLists)
-        m_nodeLists = new NodeListSet;
-    m_nodeLists->add(list);
+        m_nodeLists = new NodeListsNodeData;
+    m_nodeLists->m_registeredLists.add(list);
 }
 
@@ -439 +449 @@
     if (!m_nodeLists)
         return;
-    m_nodeLists->remove(list);
+    m_nodeLists->m_registeredLists.remove(list);
 }
 
@@ -447 +457 @@
         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();
 }
@@ -463 +473 @@
         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();
 }

trunk/WebCore/dom/Node.h

@@ -46 +46 @@
 class NamedAttrMap;
 class NodeList;
+struct NodeListsNodeData;
 class PlatformKeyboardEvent;
 class PlatformMouseEvent;
@@ -457 +458 @@
 
 protected:
-    typedef HashSet<NodeList*> NodeListSet;
-    NodeListSet* m_nodeLists;
+    NodeListsNodeData* m_nodeLists;
 
     short m_tabIndex;

trunk/WebCore/dom/NodeList.cpp

@@ -31 +31 @@
 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;
 }
 
@@ -47 +57 @@
 {
     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;
@@ -61 +71 @@
         }
 
-    if (start == rootNode) {
-        cachedLength = len;
-        isLengthCacheValid = true;
+    if (start == m_rootNode) {
+        m_caches->cachedLength = len;
+        m_caches->isLengthCacheValid = true;
     }
 
@@ -73 +83 @@
     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;
                 }
@@ -93 +103 @@
 {
     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;
                 }
@@ -114 +124 @@
     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;
             }
         }
@@ -133 +143 @@
 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))
@@ -140 +150 @@
 
         for (Node* p = node->parentNode(); p; p = p->parentNode())
-            if (p == rootNode)
+            if (p == m_rootNode)
                 return node;
 
@@ -158 +168 @@
 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;
 }
 

trunk/WebCore/dom/NodeList.h

@@ -38 +38 @@
 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();
 
@@ -56 +69 @@
     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: