Closed Bug 481440 Opened 11 years ago Closed 11 years ago
Revisit our id table
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?
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.
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.
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.
(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.
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 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.
Per discussion, we'll just nix all this and take a simple change to make the table live.
Attachment #368446 - Flags: superreview?(roc) → superreview+
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 on attachment 368510 [details] [diff] [review] And with a test fix Looks good.
Attachment #368510 - Flags: review?(jst) → review+
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.
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
And backed out due to test failures: http://hg.mozilla.org/mozilla-central/rev/ee14b862af90 I hate the HTML content sink.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Pushed again as http://hg.mozilla.org/mozilla-central/rev/0adb65bca059
Status: REOPENED → RESOLVED
Closed: 11 years ago → 11 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.