104603 - [FIX]getElementsByTagName should walk the tree lazily

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect, P1)

Description

[Fabian Guisset]

From Bugzilla Helper:
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.4) Gecko/20010914
BuildID:    20011011

Doron quite rightly figured that we do _alot_ of calls to getElementsByTagName()
to only get the first item of the array. Unfortunately that function iterates
through the whole DOM tree. And that can be _very_ expensive.
So I quickly hacked up a 
getElementByTagName(in DOMString tagName, in long index).

I tested it by adding two items to the Debug menu in navigatorOverlay.xul. The
first menu item calls test1(), the second menu item calls test2().
function test1() {
  var menuitem;
  for(var i = 0; i < 2000; i++) {
    menuitem = document.getElementsByTagName("menuitem").item(0);
  }
}

function test2() {
  var menuitem;
  for(var i = 0; i < 2000; i++) {
    menuitem = document.getElementByTagName("menuitem", 0);
  }
}
Here are the results in a debug build of today on linux:
First menu item: 21 seconds during which the browser is frozen
Second menu item: 3 seconds during which the browser is frozen

No need to say more, I guess

Reproducible: Always
Steps to Reproduce:
1. Look at nsXULDocument::GetElementsByTagName()
2.
3.

Actual Results:   getElementsByTagName walks the whole DOM tree

Expected Results:  we should have a method that doesn't walk the whole DOM tree,
to stop iterating once we find the index we want

CC'ing hyatt cause it's DOM XUL, and jst because it's DOM ;-)

Comment 1

[Fabian Guisset]

Attachment: Quickly hacked up fix to nsXULDocument

Comment 2

[James Green]

Be good to see a component of moz converted to this, e.g. a skin or a window or
something, to see how much of a difference it makes. Marking perf, but if we
walk large dom trees a lot, this could potentially be topperf.

Comment 3

[Fabian Guisset]

More numbers:
Editor uses getElementsByTagName 26 times. 24 are used only to get a specific
item of the nodelist, 2 calls are used to iterate over the node list. I can see
the gain here.
Mailnews uses getElementsByTagName 20 times. 17 are used only to get a specific
item of the nodelist. 3 calls are used to iterate over the node list. Here too.
XPFE uses getElementsByTagName about 19 times. 11 are used only to get a
specific item of the nodelist (specially in tabbox.xml!), 8 calls are used to
iterate over the node list.

I also noticed that sometimes getElementsByTagName is used to check for the
existence of certain child nodes, so maybe I'll have to add some sanity checks
in getElementByTagName... we'll see

Comment 4

[Johnny Stenback (:jst)]

Hmm, if we should do anything about this we should make a per document cache
that caches the nsContentLists that are created when
document.getElementsByTagName() is called. We'd need a two-level hash, where one
level is to find the hash for the root (i.e. the document or the element) where
the search is started, and the second level is the tag name to nsContentList hash.

I don't like the idea of adding a new method to documents for finding the first
occurance of an element by tag name, if that's a common usecase that's really
slowing us down then we should make our implementation of
document.getElementsByTagName() efficient in that case by lazily walking the
tree to find all occurances only when needed, and if the first instance is the
only thing that's asked for the it could do a simple search that stops at the
fist occurance and remembers that there might be more to search for.

Very doable, but I'm not sure it's a must-have at this moment.

Comment 5

[Fabian Guisset]

>we should make our implementation of
>document.getElementsByTagName() efficient in that case by lazily walking the
>tree to find all occurances only when needed

My first intention was to figure out when clients are using getElementsByTagName
only for its first item. But obviously this is not possible. So if you care to
explain what you mean by lazily and how I can figure out when I have to activate
this lazy mode, I'll be glad to hack it in. 
If you don't have time, I say let's give those poor editor people a way to
access the first <title> tag, the first <head> tag, the first <body> tag and the
first <base> tag, and they can remove about 80% of their current calls to
getElementsByTagName.
For mailnews that won't work because they get random tags using
getElementsByTagName.

>Very doable, but I'm not sure it's a must-have at this moment.
Must-have, no. Perf improvement, yes.

Ah well, pushing back to 1.0

Comment 6

[Johnny Stenback (:jst)]

To make getElementsByTagName() efficient when it's used only to get the first
occurance of an element by tag name we'd need to create a new nsContentList
implementation that does the following:

- When created, do nothing other than remember where to start searching (i.e.
the document or the element on which getElementsByTagName() is called) and what
the tag name is that we're looking for.

- If the first item is requested, walk the tree until the first element is found
and store state that tells us that we only walked to the first element.

- If the 1+n:th (where n >= 1) item is asked for, continue walking and fill the
whole list and store state that tells us that we've searched the whole tree.

- If the length of the nodelist is asked for, walk the whole tree.

- If/when the document is mutated, if our internal state says we've only
searched for the first item, check if the mutation changes what the first item
is, or invalidate the stored first item so that we'll search again next time the
first item is asked for. If the internal state says that we've searched the
whole tree, do what we do today.

Something like this combined with cleaver caching of the content lists would
work very efficiently in 99% of the usecases.

Comment 7

[Fabian Guisset]

Changing summary. The proposed solution makes a lot of sense. I'll see what I
can do, though my skills are probably still too limited.

Comment 8

[Fabian Guisset]

Not required for mozilla 1.0

Comment 9

[Fabian Guisset]

Triaging my bug list. Severity back to normal, since I have no idea what the
actual gain of walking the tree lazily will be. Severity P4, not required for
mozilla1.0. Sending to DOM Core since it's no longer a new function.

Comment 10

[Boris Zbarsky [:bzbarsky]]

I just filed bug 140758 on the caching of content lists jst suggests at the end
of comment 6

Comment 11

[Doron Rosenberg (IBM)]

This is a top evangelism issue, have some sites that are slow because of this. 

Comment 12

[Boris Zbarsky [:bzbarsky]]

I'm working on this...  I have it working; just needs a bit of cleanup

Comment 13

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed patch

Comment 14

[Boris Zbarsky [:bzbarsky]]

The changes to nsHTMLFormElement seemed reasonable to me, but are by no means
necessary to fix this bug.  The one thing that gives me pause there is that
nsBaseContentList is a Nodelist but not an HTMLCollection.  So it has no
namedItem() method.

In real life, what this means is that given this markup:

<html><body><form name="foo">
<input type="checkbox" name="aaa" value="1">
</form></body></html>

document.foo.aaa.namedItem('aaa') will throw an error (as it does in NS4) and
document.foo.aaa['aaa'] will be |undefined| as it is in NS4.  In IE5,
document.foo.aaa['aaa'] is |object|, but it's |.value| is |undefined|.  So I
doubt anyone's using this....  but confirmation from jkeiser that this change is
OK would be nice.  ;)

Comment 15

[John Keiser (jkeiser)]

Comment on attachment 88765 [details] [diff] [review]
Proposed patch

>Index: base/src/nsContentList.h
>===================================================================
...
>-  nsresult Match(nsIContent *aContent, PRBool *aMatch);
>+  PRBool Match(nsIContent *aContent);
>   void Init(nsIDocument *aDocument);
>-  void PopulateWith(nsIContent *aContent, PRBool aIncludeRoot);
>+  void PopulateWith(nsIContent *aContent, PRBool aIncludeRoot,
>+                    PRUint32 & aElementsToAppend);
>+  void PopulateWithStartingAt(nsIContent *aStartRoot,
>+                              nsIContent *aStartChild,
>+                              PRUint32 & aElementsToAppend);
>   PRBool MatchSelf(nsIContent *aContent);
>-  void PopulateSelf();
>+  void PopulateSelf(PRUint32 aNeededLength);

I noticed you put comments on a couple of these methods below, could you do it
here instead so that it will show up in doxygen?  Especially the methods like
PopulateSelf and PopulateWith, whose purpose is not apparent from the method
name.

>   void DisconnectFromDocument();
>   PRBool IsDescendantOfRoot(nsIContent* aContainer);
>   PRBool ContainsRoot(nsIContent* aContent);
>   nsresult CheckDocumentExistence();
>   void RemoveFromHashtable();
> 
>   nsContentListMatchFunc mFunc;
>   nsString* mData;
>-  PRBool mMatchAll;
>+  PRPackedBool mMatchAll;
>+  PRUint16 mState;

Any reason this can't be PRUint8?

Also, please comment the new members to describe what they are, and comment the
new constants too.  If you know what the other two members are, feel free too
:)

>Index: base/src/nsContentList.cpp
>===================================================================
...
>+    if (mState != LIST_UP_TO_DATE)
>+      PopulateSelf(PRUint32(-1));
>+
>+    NS_ASSERTION(!mDocument || mState == LIST_UP_TO_DATE,
>+                 "If we have a document, we better be up-to-date now!");
>+

1. There *must* be a constant for max PRUint32 somewhere.
2. Assertion is unclear.  Perhaps "PopulateSelf did not bring content list up
to date!"
3. Flush, populate and assert could be moved together into a single field.

> nsContentList::ContentAppended(nsIDocument *aDocument, nsIContent* aContainer,
>                                PRInt32 aNewIndexInContainer)
...
>+    PRBool appendToList = PR_FALSE;
>+    if (ourCount == 0) {
>+      appendToList = PR_TRUE;
>+    } else {
>+      nsIContent* ourLastContent =
>+        NS_STATIC_CAST(nsIContent*, mElements.ElementAt(ourCount - 1));
>+      /*
>+       * We want to append instead of invalidating in two cases:
>+       *  1) The parent of ourLastContent is aContainer
>+       *  3) aContainer is ourLastContent or comes after it in document order
>+       */
>+      nsCOMPtr<nsIContent> parentContent;
>+      ourLastContent->GetParent(*getter_AddRefs(parentContent));
>+      if (parentContent == aContainer) {
>+        appendToList = PR_TRUE;
>+      } else {
>+        // XXX we should have a way to call CompareTreePosition on (nsIContent*)s
>+        nsCOMPtr<nsIDOM3Node> ourLastDOM3Node(do_QueryInterface(ourLastContent));
>+        nsCOMPtr<nsIDOMNode> newNodeContainer(do_QueryInterface(aContainer));
>+        if (ourLastDOM3Node && newNodeContainer) {
>+          PRUint16 comparisonFlags;
>+          nsresult rv = ourLastDOM3Node->CompareTreePosition(newNodeContainer,
>+                                                             &comparisonFlags);
>+          if (NS_SUCCEEDED(rv) && 
>+              (comparisonFlags &
>+               (nsIDOMNode::TREE_POSITION_SAME_NODE |
>+                nsIDOMNode::TREE_POSITION_FOLLOWING))) {
>+            appendToList = PR_TRUE;
>+          }
>+        }
>+      }
>+    }

As noted before, I don't think this will work in the case where ourLastNode is
a distant child of DOMNode.  This should actually happen often within the
normal course of pageload, which could explain the lack of pageload
improvement.

Also, ContentAppended could really use some more comments on when dirty will
happen, when lazy will happen, etc.

> void 
>+nsContentList::PopulateWithStartingAt(nsIContent *aStartRoot,
>+                                      nsIContent *aStartChild,
>+                                      PRUint32 & aElementsToAppend)

Perhaps a better name for this is PopulateWithStartingAfter?

... hey, you know, nsHTMLOptionCollection has this exact algorithm, maybe it
needs to use nsContentList.

>   else if (mDocument) {
>     nsCOMPtr<nsIContent> root;
>     mDocument->GetRootContent(getter_AddRefs(root));
>     if (root) {
>-      PopulateWith(root, PR_TRUE);
>+      PopulateWith(root, PR_TRUE, elementsToAppend);
>+      NS_ASSERTION(elementsToAppend + mElements.Count() == invariant,
>+                   "Something is awry in PopulateWith!");
>     }
>   }

Any reason not to just set mRootContent = mDocument when mDocument is set and
mRootContent is null?

>Index: html/content/src/nsHTMLFormElement.cpp
>===================================================================

Form element changes seem fine.

Comment 16

[John Keiser (jkeiser)]

Comment on attachment 88765 [details] [diff] [review]
Proposed patch

Ugh.  By "3. Flush, populate and assert could be moved together into a single
field." I meant:

3. Flush, populate and assert could be moved together into a single function
since they are used in multiple places.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Attachment: Better stronger comments and all that

Comments moved to header and expanded.	mState made a PRUint8.

> 1. There *must* be a constant for max PRUint32 somewhere.

Nope. :(

Assertion made clearer and moved out into an inline function.

Good catch on the fact that ourLastNode could be a descendant of aContainer. 
Fixed.

PopulateWithStartingAfter is a better name, yes.

> Any reason not to just set mRootContent = mDocument when mDocument is set and

> mRootContent is null?

document.getElementsByTagName("*") and
document.documentElement.getElementsByTagName("*") are different -- the former
includes the root element, the latter does not.  We need to differentiate the
two cases somehow...

Comment 18

[Boris Zbarsky [:bzbarsky]]

Attachment: javadoc format for comments

Comment 19

[John Keiser (jkeiser)]

Comment on attachment 89371 [details] [diff] [review]
javadoc format for comments

r=jkeiser

Might want to comment BringSelfUpToDate, but that's optional.  Wonderful patch,
commentos grandes amigo!

Comment 20

[Johnny Stenback (:jst)]

Comment on attachment 89371 [details] [diff] [review]
javadoc format for comments

- In nsContentList.h:

+  /**
+   * Please do not ever pass null pointers to this method.
...

No need to be polite here, loose the word "Please" :-)

- In nsContentList::ContentAppended()

> {
>-  PRInt32 i, count;
>+  PRInt32 count;
>+
>+  /*
>+   * If the state is LIST_DIRTY then we have no useful information in
>+   * our list and we want to put off doing work as much as possible.
>+   */
>+  if (mState == LIST_DIRTY) 
>+    return NS_OK;

This is C++, no need to declare variables at the top of the scope. Since you
don't use count if mState == LIST_DIRTY, move the if check up above the
declaration of count.

- In nsContentList::PopulateWithStartingAfter():

+  PRInt32 i;
+  if (aStartChild) {
+    aStartRoot->IndexOf(aStartChild, i);
+    NS_ASSERTION(i >= 0, "The start child must be a child of the start
root!");
+    ++i;  // move to one past
+  } else {
+    i = 0;
+  }

How about loosing the else and initializing i to 0 in stead? Maybe one more
instruction, but less code probably.

- In nsContentList::PopulateSelf():

+  PRUint32 count;
+  if (mState == LIST_DIRTY) {
+    Reset();
+    count = 0;
+  } else {
+    count = mElements.Count();
+  }

How about:

+  PRUint32 count;
+  if (mState == LIST_DIRTY) {
+    Reset();
+  }
+  count = mElements.Count();

in stead?

Seems like nsContentList::ContentIsDescendantOf() really belongs in
nsContentUtils in stead of here, want to move it now or later? :-)

- In nsContentList::IsDescendantOfRoot():

   if (!mRootContent) {
     return PR_TRUE;
   }

Is this not true only if aContainer's document == mDocument?

Other than that, sr=jst

Comment 21

[Johnny Stenback (:jst)]

... or make that:

+  if (mState == LIST_DIRTY) {
+    Reset();
+  }
+  PRUint32 count = mElements.Count();

Comment 22

[Boris Zbarsky [:bzbarsky]]

Attachment: Fix those

Moved the descendant stuff to nsContentUtils, strategically repositioned where
I set |count| and how, added an assetion that aContainer's document and
mDocument are the same -- if they are not we are in trouble...

Comment 23

[Boris Zbarsky [:bzbarsky]]

And checked in on the trunk.