[Patch] HTMLCollection cache (was: phpnuke 7.3 slowness)

Koos Vriezen koos.vriezen at xs4all.nl
Sat Sep 4 15:20:16 BST 2004


On Thu, Sep 02, 2004 at 07:33:14PM +0200, Koos Vriezen wrote:
> Hi,
> 
> Looking why phpnuke has become so slow, I found that it does
>         var htmlArea = new Array(20);
>         var j=0;
>         for (i=1;i<document.all.length;i++) {
>         if (document.all(i).tagName=="TEXTAREA") {
>          htmlArea[j]=document.all(i).name;
>          j=j+1;
>         }
>         }
[..]
> The 'document.all' in the 'for' and 'if' looks to be the culprit. Quite
> some time ago, before 3.1, there was some talk about speeding up these
> collection things. Is anybody working on this still?
> One idea might be that elements for document.all, and .applets, .forms,
> .whatever, should register themselves on attach (and deregister on
> detach) at document wide tables. Caching a collection, might be another
> one, though dangerous of course. Thoughts, ideas, ..

This patch creates a HTMLDocumentImpl::CollectionInfo's for all types of
collections, containing length, current node, position information.
NodeImpl::attach/detach increases the DocumentImpl::m_domtree_version
unsiged integer for if cache is valid or not (if I'm not mistaken, if
nothing attached/detached, then collections are exactly the same, no?).

Unfortunately, HTMLCollectionImpl::getItem only digs inside the tree, so
as soon as we hit a lastChild leaf, we must start again for
HTMLCollectionImpl::item. Still this give a more then five time speedup.
The length calculation is reduced to only one in the above case.

The code above is much faster now. W/o it, I even get a javascript
freeze warning. With it, it's almost as fast as the hacked
includes/wysiwyg.php version (that what produced my speedup javascript).

> Koos
-------------- next part --------------
Index: xml/dom_docimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/xml/dom_docimpl.cpp,v
retrieving revision 1.290
diff -u -3 -p -r1.290 dom_docimpl.cpp
--- xml/dom_docimpl.cpp	9 Aug 2004 08:39:47 -0000	1.290
+++ xml/dom_docimpl.cpp	4 Sep 2004 14:05:02 -0000
@@ -218,7 +218,7 @@ QPtrList<DocumentImpl> * DocumentImpl::c
 
 // KHTMLView might be 0
 DocumentImpl::DocumentImpl(DOMImplementationImpl *_implementation, KHTMLView *v)
-    : NodeBaseImpl( new DocumentPtr() )
+    : NodeBaseImpl( new DocumentPtr() ), m_domtree_version(0)
 {
     document->doc = this;
     m_paintDeviceMetrics = 0;
Index: xml/dom_docimpl.h
===================================================================
RCS file: /home/kde/kdelibs/khtml/xml/dom_docimpl.h,v
retrieving revision 1.130
diff -u -3 -p -r1.130 dom_docimpl.h
--- xml/dom_docimpl.h	18 Jun 2004 17:38:26 -0000	1.130
+++ xml/dom_docimpl.h	4 Sep 2004 14:05:03 -0000
@@ -432,6 +432,7 @@ public:
 
     DOMString toString() const;
 
+    void incDOMTreeVersion() { ++m_domtree_version; }
 signals:
     void finishedParsing();
 
@@ -471,6 +472,8 @@ protected:
     NodeImpl *m_hoverNode;
     NodeImpl *m_focusNode;
 
+    unsigned int m_domtree_version;
+
     struct IdNameMapping {
         IdNameMapping(unsigned short _start)
             : idStart(_start), count(0) {}
Index: xml/dom_nodeimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/xml/dom_nodeimpl.cpp,v
retrieving revision 1.237
diff -u -3 -p -r1.237 dom_nodeimpl.cpp
--- xml/dom_nodeimpl.cpp	28 Aug 2004 14:41:19 -0000	1.237
+++ xml/dom_nodeimpl.cpp	4 Sep 2004 14:05:03 -0000
@@ -817,6 +817,7 @@ void NodeImpl::attach()
         m_render->close();
         m_rendererNeedsClose = false;
     }
+    getDocument()->incDOMTreeVersion();
     m_attached = true;
 }
 
@@ -828,6 +829,7 @@ void NodeImpl::detach()
         m_render->detach();
 
     m_render = 0;
+    getDocument()->incDOMTreeVersion();
     m_attached = false;
 }
 
Index: html/html_documentimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/html/html_documentimpl.cpp,v
retrieving revision 1.160
diff -u -3 -p -r1.160 html_documentimpl.cpp
--- html/html_documentimpl.cpp	29 Feb 2004 22:04:32 -0000	1.160
+++ html/html_documentimpl.cpp	4 Sep 2004 14:05:03 -0000
@@ -72,6 +72,8 @@ HTMLDocumentImpl::HTMLDocumentImpl(DOMIm
 
     m_doAutoFill = false;
 
+    memset( m_collection_info, 0, sizeof( CollectionInfo ) * HTMLCollectionImpl::LAST_TYPE);
+
 /* dynamic history stuff to be fixed later (pfeiffer)
     connect( KHTMLFactory::vLinks(), SIGNAL( inserted( const QString& )),
              SLOT( slotHistoryChanged() ));
@@ -434,4 +436,13 @@ void HTMLDocumentImpl::determineParseMod
         recalcStyleSelector();
 }
 
+HTMLDocumentImpl::CollectionInfo & HTMLDocumentImpl::collectionInfo( int type )
+{
+    if (m_collection_info[type].version != m_domtree_version) {
+        memset( &m_collection_info[type], 0, sizeof( CollectionInfo ));
+        m_collection_info[type].version = m_domtree_version;
+    }
+    return m_collection_info[type];
+}
+
 #include "html_documentimpl.moc"
Index: html/html_documentimpl.h
===================================================================
RCS file: /home/kde/kdelibs/khtml/html/html_documentimpl.h,v
retrieving revision 1.71
diff -u -3 -p -r1.71 html_documentimpl.h
--- html/html_documentimpl.h	20 Feb 2004 14:34:18 -0000	1.71
+++ html/html_documentimpl.h	4 Sep 2004 14:05:03 -0000
@@ -26,6 +26,7 @@
 #define HTML_DOCUMENTIMPL_H
 
 #include "xml/dom_docimpl.h"
+#include "html/html_miscimpl.h"
 
 #include <qmap.h>
 
@@ -75,6 +76,16 @@ public:
 
     void setAutoFill() { m_doAutoFill = true; }
 
+    struct CollectionInfo {
+        unsigned int version;
+        NodeImpl *current;
+        unsigned int position;
+        unsigned int length;
+        bool haslength;
+    };
+    CollectionInfo & collectionInfo( int type );
+    CollectionInfo m_collection_info[HTMLCollectionImpl::LAST_TYPE];
+
 protected:
     HTMLElementImpl *bodyElement;
     HTMLElementImpl *htmlElement;
Index: html/html_miscimpl.cpp
===================================================================
RCS file: /home/kde/kdelibs/khtml/html/html_miscimpl.cpp,v
retrieving revision 1.39
diff -u -3 -p -r1.39 html_miscimpl.cpp
--- html/html_miscimpl.cpp	28 Jul 2004 09:02:33 -0000	1.39
+++ html/html_miscimpl.cpp	4 Sep 2004 14:05:03 -0000
@@ -145,7 +145,12 @@ unsigned long HTMLCollectionImpl::calcLe
 // calculation every time...
 unsigned long HTMLCollectionImpl::length() const
 {
-    return calcLength(base->firstChild());
+    HTMLDocumentImpl::CollectionInfo &info = static_cast<HTMLDocumentImpl*>(base->getDocument())->collectionInfo(type);
+    if (!info.haslength) {
+        info.length = calcLength(base->firstChild());
+        info.haslength = true;
+    }
+    return info.length;
 }
 
 NodeImpl *HTMLCollectionImpl::getItem(NodeImpl *current, int index, int &len) const
@@ -231,14 +236,32 @@ NodeImpl *HTMLCollectionImpl::getItem(No
 
 NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
 {
-    int pos = 0;
-    return getItem(base->firstChild(), index, pos);
+    HTMLDocumentImpl::CollectionInfo &info = static_cast<HTMLDocumentImpl*>(base->getDocument())->collectionInfo(type);
+    if (info.current && info.position == index)
+        return info.current;
+    if (info.haslength && info.length <= index)
+        return 0L;
+    if (!info.current || info.position > index) {
+        info.current = base->firstChild();
+        info.position = 0;
+    }
+    int pos = (int) info.position;
+    info.current = getItem(info.current, index, pos);
+    if (!info.current) { // at a leave in the tree
+        pos = 0;
+        info.current = getItem(base->firstChild(), index, pos);
+    }
+    info.position = index;
+    return info.current;
 }
 
 NodeImpl *HTMLCollectionImpl::firstItem() const
 {
-    int pos = 0;
-    currentItem = getItem(base->firstChild(), 0, pos);
+    HTMLDocumentImpl::CollectionInfo &info = static_cast<HTMLDocumentImpl*>(base->getDocument())->collectionInfo(type);
+    if (info.current && info.position == 0)
+        return info.current;
+    int pos = info.position = 0;
+    info.current = currentItem = getItem(base->firstChild(), 0, pos);
     return currentItem;
 }
 
Index: html/html_miscimpl.h
===================================================================
RCS file: /home/kde/kdelibs/khtml/html/html_miscimpl.h,v
retrieving revision 1.25
diff -u -3 -p -r1.25 html_miscimpl.h
--- html/html_miscimpl.h	8 Aug 2004 21:23:17 -0000	1.25
+++ html/html_miscimpl.h	4 Sep 2004 14:05:03 -0000
@@ -51,7 +51,7 @@ class HTMLCollectionImpl : public khtml:
 public:
     enum Type {
         // from HTMLDocument
-        DOC_IMAGES,    // all IMG elements in the document
+        DOC_IMAGES = 0, // all IMG elements in the document
         DOC_APPLETS,   // all OBJECT and APPLET elements
         DOC_FORMS,     // all FORMS
         DOC_LINKS,     // all A _and_ AREA elements with a value for href
@@ -66,7 +66,8 @@ public:
         // from HTMLMap
         MAP_AREAS,
         DOC_ALL,        // "all" elements (IE)
-        NODE_CHILDREN   // first-level children (IE)
+        NODE_CHILDREN,   // first-level children (IE)
+        LAST_TYPE
     };
 
     HTMLCollectionImpl(NodeImpl *_base, int _tagId);


More information about the kfm-devel mailing list