299689 - Getting lots of elements by ID can be slow

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

The testcase is at the URL of bug 297959, the getElementById test.  That test
gets each of the table cells by id, which makes the whole thing O(N^2) in number
of cells, since we have to keep walking over parts of the DOM that we've walked
over before.

Ian's suggestion was that after we've had some number of misses of the
getElementById hashtable we should just assume more misses will come, walk over
the whole DOM and prefill the hashtable.  In fact, I've been thinking we should
switch to a mode in which the hashtable is maintained live altogether.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed patch

This makes us switch to a live ID table once we've had 128 misses for
GetElementById in this document.

That said, perhaps it would make sense to eliminate some of this complexity and
always have a live table?

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to tip

Comment 3

[Johnny Stenback (:jst)]

Comment on attachment 194001 [details] [diff] [review]
Updated to tip

+  PRBool IdTableIsLive() {
+    // live if we've had over 127 misses
+    return (mIdMissCount & 0x80) != 0;
+  }

Make that const, and isn't 127 sortof a high number here? How about 63?

- In nsHTMLDocument::UpdateIdTableEntry():

+  PRBool liveTable = IdTableIsLive();
+  PLDHashOperator op = liveTable ? PL_DHASH_ADD : PL_DHASH_LOOKUP;
   IdAndNameMapEntry *entry =
     NS_STATIC_CAST(IdAndNameMapEntry *,
		    PL_DHashTableOperate(&mIdAndNameHashTable, &aId,
-					 PL_DHASH_LOOKUP));
+					 op));

-  if (PL_DHASH_ENTRY_IS_BUSY(entry)) {
+  if ((liveTable && entry) || PL_DHASH_ENTRY_IS_BUSY(entry)) 

PL_DHashTableOperate() can return a null entry for PL_DHASH_ADD if we're OOM,
you need to not do the PL_DHASH_ENTRY_IS_BUSY(entry) check if entry is null.

r+sr=jst

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comments

Comment 5

[Boris Zbarsky [:bzbarsky]]

Fix checked in to trunk.

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 195157 [details] [diff] [review]
Updated to comments

>+  PRBool liveTable = IdTableIsLive();
>+  PLDHashOperator op = liveTable ? PL_DHASH_ADD : PL_DHASH_LOOKUP;
>   IdAndNameMapEntry *entry =
>     NS_STATIC_CAST(IdAndNameMapEntry *,
>                    PL_DHashTableOperate(&mIdAndNameHashTable, &aId,
>-                                        PL_DHASH_LOOKUP));
>+                                        op));
> 
>-  if (PL_DHASH_ENTRY_IS_BUSY(entry)) {
>+  if (entry && (liveTable || PL_DHASH_ENTRY_IS_BUSY(entry))) {
>     entry->mIdContent = aContent;
>   }

If !entry, you should bail with OOM.

Do you really want to probe the table without adding if !liveTable?  If so, you
could simplify the logic of the || expression to just
PL_DHASH_ENTRY_IS_BUSY(entry).	If not, you don't need that || expression at
all.

/be

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> If not, you don't need that || expression at all.

By which I mean, always PL_DHASH_ADD.  It's like a LOOKUP when the entry exists
(it doesn't disturb the entry).

/be

Comment 8

[Brendan Eich [:brendan]]

(In reply to comment #7)
> (In reply to comment #6)
> > If not, you don't need that || expression at all.
> 
> By which I mean, always PL_DHASH_ADD.  It's like a LOOKUP when the entry exists
> (it doesn't disturb the entry).

So bz pointed out the obvious, that we don't want to add unconditionally.  So my
"then" clause ("you could simplify the logic of the || expression to just
PL_DHASH_ENTRY_IS_BUSY(entry)") applies, because if ADD succeeds (does not fail
with OOM and return null), it returns a busy entry pointer.

/be

Comment 9

[Boris Zbarsky [:bzbarsky]]

I just checked this in with r+sr=brendan:

-  if (entry && (liveTable || PL_DHASH_ENTRY_IS_BUSY(entry))) {
+  if (!entry) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+  
+  if (PL_DHASH_ENTRY_IS_BUSY(entry)) {

Comment 10

[Boris Zbarsky [:bzbarsky]]

Fixed on trunk.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Not exactly sure how to write a decent test for this...