Closed Bug 481440 Opened 16 years ago Closed 16 years ago

Revisit our id table

Categories

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

Product:
Core
Component:
DOM: Core & HTML
Platform:
x86
macOS
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: bzbarsky, Assigned: bzbarsky)

References

Details

(Keywords: memory-footprint, perf)

Attachments

(2 files, 5 obsolete files)

Testcase showing the document.all bustage: should alert the input
(deleted), text/html
Details
And with a test fix
(deleted), patch
jst
: review+
Details | Diff | Splinter Review
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?
Blocks: 481131
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.
Attached patch Proposed patch (obsolete) (deleted) — — Splinter Review
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.
Assignee: nobody → bzbarsky
Status: NEW → ASSIGNED
Attachment #368188 - Flags: superreview?(roc)
Attachment #368188 - Flags: review?(jst)
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...
Attached patch With the change roc asked for (obsolete) (deleted) — — Splinter Review
Attachment #368188 - Attachment is obsolete: true
Attachment #368265 - Flags: superreview?(roc)
Attachment #368265 - Flags: review?(jst)
Attachment #368188 - Flags: superreview?(roc)
Attachment #368188 - Flags: review?(jst)
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.
Attachment #368265 - Flags: superreview?(roc)
Attachment #368265 - Flags: superreview-
Attachment #368265 - Flags: review?(jst)
Attachment #368265 - Flags: review-
Per discussion, we'll just nix all this and take a simple change to make the table live.
Attachment #368265 - Attachment is obsolete: true
Attached patch Nice simple version (obsolete) (deleted) — — Splinter Review
Attachment #368436 - Attachment is obsolete: true
Attachment #368444 - Flags: superreview?(roc)
Attachment #368444 - Flags: review?(jst)
Attached patch Even compiling (obsolete) (deleted) — — Splinter Review
Attachment #368444 - Attachment is obsolete: true
Attachment #368446 - Flags: superreview?(roc)
Attachment #368446 - Flags: review?(jst)
Attachment #368444 - Flags: superreview?(roc)
Attachment #368444 - Flags: review?(jst)
Attachment #368446 - Flags: superreview?(roc) → superreview+
Attached patch And with a test fix (deleted) — — Splinter Review
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.
Attachment #368446 - Attachment is obsolete: true
Attachment #368510 - Flags: review?(jst)
Attachment #368446 - Flags: review?(jst)
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: 16 years ago
Flags: in-testsuite?
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 → ---
Filed bug 484820 on the sink issue.
Depends on: 484820
Pushed again as http://hg.mozilla.org/mozilla-central/rev/0adb65bca059
Status: REOPENED → RESOLVED
Closed: 16 years ago → 16 years ago
Resolution: --- → FIXED
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: