481440 - Revisit our id table

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

Right now we use a single hashtable for the following things:

1) id-to-node mapping
2) name-to-nodelist mapping
3) some sort of document.all thing
4) tracking id changes.

This means that a table entry is 4 words of value (plus the atom key, of course).  This is pretty significant, so we treat the table as "non-live" until sufficiently many getElementById() calls have missed the table.

Issues:

* It might take a good bit of DOM-walking (e.g. see bug 481131) until we get
  our 63 cache misses.
* The document.all stuff actually checks table liveness, which only matters for
  IDs.  This is a bug which should be quite testable.

I propose using three separate tables: one for items 1 & 4 above, and two separate ones for items 2 and 3 above.  The ID table should always be live.  I don't have a strong preference as far as the name table goes.

Thoughts?

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase showing the document.all bustage: should alert the input

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I think we could (and should) initialize each table on first use, at least. There should be a lot of pure data documents that we never do getElementById on.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed patch

This splits things up into three hashtables: ids+callbacks, names, document.all.  The latter two are pushed back down into nsHTMLDocument; the bogus document.all dependency on the id table being live is nuked.  The ID table is initialized lazily the first time someone does a GetElementById or sets up an id observer, except for XUL, where we just init it.  I suspect having a XUL document where no one does GetElementById is kinda rare anyway.

Obvious things to watch out for, performance-wise:

1)  For HTML, we now traverse added/removed subtrees twice: once looking for
    names and once looking for IDs.  We used to only do it once.  On the other
    hand, I switched us to doing fewer virtual function calls during the
    traversal, so this might end up a wash.
2)  This does add an extra hashtable lookup to nsDocument::ResolveName in the
    case when we miss the name hashtable.  It also adds an extra flush if we
    also miss the ID hashtable.  If we care, I can eliminate the extra flush by
    tossing more args onto some of the relevant methods... Ideally we'll just
    land Henri's parser, though, and get rid of all these flushes.

I pushed this patch to the try server; will see how things look there.

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It seems to me (after discussion on IRC) that the extra code and complexity to avoid issue #1 is very low --- just shuffling a few things around and adding a few calls to UpdateIdTableEntry and RemoveIdTableEntry in nsHTMLDocument.

Comment 5

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

(In reply to comment #3)
> 2)  This does add an extra hashtable lookup to nsDocument::ResolveName in the
>     case when we miss the name hashtable.  It also adds an extra flush if we
>     also miss the ID hashtable.  If we care, I can eliminate the extra flush 
>     by tossing more args onto some of the relevant methods... Ideally we'll 
>     just land Henri's parser, though, and get rid of all these flushes.

I believe this could be an issue. Apparently nsDocument::ResolveName is called *a lot*.

jst knows the details.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Yes, it gets called a fair amount.  I don't think the extra hashtable lookup will really kill us here; we need to figure out a way to just call it less somehow...

Comment 7

[Boris Zbarsky [:bzbarsky]]

Attachment: With the change roc asked for

Comment 8

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 368265 [details] [diff] [review]
With the change roc asked for

This actually fails mochitests because of the change to not always adding the entry in GetElementByIdInternal.  The problem is that we can not add an entry, then flush, get the entry added, but if ChangeTable doesn't happen the generation doesn't change... and then we don't know that we need to look up again.

I guess I'll switch to always adding, even though we no longer need the NOT_IN_DOCUMENT thing.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Per discussion, we'll just nix all this and take a simple change to make the table live.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Attachment: For posterity, version of my original patch that should pass tests

Comment 11

[Boris Zbarsky [:bzbarsky]]

Attachment: Nice simple version

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: Even compiling

Comment 13

[Boris Zbarsky [:bzbarsky]]

Attachment: And with a test fix

We apparently never notified on attributes on <head>; the only thing that allowed <head> to be gotten by ID before was the laziness in initially populating the table... This just fixes us to notify on <head>'s attributes.

Comment 14

[Johnny Stenback (:jst)]

Comment on attachment 368510 [details] [diff] [review]
And with a test fix

Looks good.

Comment 15

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/8fddfa5d2748

in-testsuite? because I can't think of a way to test the liveness in our testsuites, though there's the test for that document.all thing...

Ideally we'd test that a bunch of getElementByID calls take the same time as another such bunch.  Or something.

Comment 16

[Boris Zbarsky [:bzbarsky]]

And backed out due to test failures: http://hg.mozilla.org/mozilla-central/rev/ee14b862af90

I hate the HTML content sink.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Filed bug 484820 on the sink issue.

Comment 18

[Boris Zbarsky [:bzbarsky]]

Pushed again as http://hg.mozilla.org/mozilla-central/rev/0adb65bca059