Closed Bug 529808 Opened 15 years ago Closed 6 years ago

[HTML5] Remove the static atom table

Categories

(Core :: DOM: HTML Parser, enhancement, P4)

enhancement

Tracking

()

RESOLVED FIXED
mozilla60
Tracking Status
firefox60 --- fixed

People

(Reporter: hsivonen, Assigned: n.nethercote)

References

(Blocks 1 open bug)

Details

(Whiteboard: [MemShrink])

Attachments

(1 file, 1 obsolete file)

Attached patch Remove the static atom table (obsolete) — Splinter Review
Bug 514661 introduced a global hashtable of static atoms.

As pointed out in http://groups.google.com/group/mozilla.dev.platform/browse_thread/thread/3a3785a83571bfeb/44d733fd112ce92e , the hashtable isn't necessary if only the strictly necessary invariants required by the HTML5 parser are held and the usual invariants are violated some more within the HTML5 parser.

As part of sorting out http://groups.google.com/group/mozilla.dev.tree-management/browse_thread/thread/b9729ca82d54e07b , I wrote a patch that removes the static atom hashtable and replaces it with a hack and documentation, so here it is for consideration even though it seems the patch wasn't necessary for addressing the tp4 (Private Bytes) regression.

Basically:
Since it's unnecessary to compare atoms between an element name and an attribute name or an attribute name and the doctype name (etc.), it's unnecessary to provide pointer-comparability between different usages of atoms within the HTML5 parser. (By the time the atoms reach the DOM, the HTML5-parser-private dynamic atoms are replaced with regular atoms anyway. If an atom starts out as a static atom inside the HTML5 parser, which is the common case, it travels as the same static atom all the way.)

Pros:
 * Less code to run.
 * Less memory to allocate.

Cons:
 * The setup relies on whoever modifies the HTML5 parser taking into account the special atom rules that differ from what one may normally assume about atoms.
Attachment #413318 - Attachment is patch: true
Attachment #413318 - Attachment mime type: application/octet-stream → text/plain
Comment on attachment 413318 [details] [diff] [review]
Remove the static atom table

This patch misses some required tricks, apparently.
Attachment #413318 - Attachment is obsolete: true
Henri: I'd like to remove gStaticAtomTable. Doing so would save 64 KiB per process on 64-bit platforms.

Here's my understanding of why gStaticAtomTable is needed: normally atom lookups are restricted to the main thread, but
the HTML5Parser thread needs to be able to look up static atoms. So we put a pointer to each static atom in both gAtomTable and gStaticAtomTable, and seal gStaticAtomTable to ensure it is read-only, and so then it's safe to access it from the HTML5Parser thread. (Given that there is no explicit locking involved I'm a little surprised that TSAN doesn't complain about this. Anyway...)

To preserve this behaviour while avoiding the duplication, one possibility would be to have gDynamicAtomTable and gStaticAtomTable. The latter would still be sealed and thus read-only. For normal atom lookups we'd have to check in both tables, which isn't ideal.

So it would be nicer if we could just have a single table. I tried resurrecting the above patch and did a try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=bc8220bf655b. There are failures in M(5), in parser/htmlparser/tests/mochitest/test_img_picture_preload.html.

Any thoughts you have would be appreciated. Thank you.
Blocks: 1257126
Flags: needinfo?(hsivonen)
This requires me to page in quite a bit of stuff that I've forgotten. To avoid mere silence until I've taken a better look:

 * Atoms being pointer-comparable within the scope of a given off-the-main-thread parser instance is assumed to be true. Otherwise stuff like prohibition of duplicate attributes breaks.

 * Atoms being pointer-comparable on the main thread is assumed to be true.

 * https://mxr.mozilla.org/mozilla-central/source/parser/html/nsHtml5AtomList.h doesn't have to be separate from the main atom list. Initially, it wasn't separate, but I made it separate on the advice I was given way back when. I think the atom lists should merge to remove the complexity of atom registration dealing with two lists.

 * The HTML parser optimizes for the rarity of having to dynamically allocate atoms over binary or heap footprint. That's probably a bad idea. The HTML parser should probably be changed to pre-declare notably fewer names.

 * Can we make static atoms actually static in the sense of putting them in the data segment of the binaries?

 * If on the main thread we want to have a single (lockless table), is there a good proposal to populate a parser instance-specific atom table with the static atoms in an efficient way?
Thank you for the info.

>  *
> https://mxr.mozilla.org/mozilla-central/source/parser/html/nsHtml5AtomList.h
> doesn't have to be separate from the main atom list. Initially, it wasn't
> separate, but I made it separate on the advice I was given way back when. I
> think the atom lists should merge to remove the complexity of atom
> registration dealing with two lists.

There are several other atom lists, though they are much smaller than nsGkAtoms and nsHtml5Atoms. There are 6 or 7 atom lists in total. Registering multiple atom lists isn't much harder than registering a single list. However, there are a non-trivial number of duplicates across the lists, and merging them would remove the duplicates which would (a) shrink the binary, and (b) speed up table creation. It's a good idea; I'll add it to my todo list.


>  * The HTML parser optimizes for the rarity of having to dynamically
> allocate atoms over binary or heap footprint. That's probably a bad idea.
> The HTML parser should probably be changed to pre-declare notably fewer
> names.

Any suggestions on how to choose which names are removed from the list? Maybe instrument table lookups to see which ones are infrequent?


>  * Can we make static atoms actually static in the sense of putting them in
> the data segment of the binaries?

There are two pieces to a "static atom": (a) the nsFakeStringBuffer containing the actual chars, and (b) the nsIAtom (implemented as a PermanentAtomImpl) that wraps the nsFakeStringBuffer. Currently (a) is static and (b) is heap-allocated. I assume you are suggesting that (b) become static as well? It would increase binary size but might make start-up faster. PermanentAtomImpl is a type with a vtable, and I don't know if there are difficulties with statically allocating those.


>  * If on the main thread we want to have a single (lockless table), is there
> a good proposal to populate a parser instance-specific atom table with the
> static atoms in an efficient way?

No. I was hoping to avoid the need, given this bug's title. My only idea w.r.t. table structure is the one in the 3rd paragraph of comment 2: have one table for static atoms and one for dynamic atoms, with no overlap. But that would require two lookups for general atom lookup.
(In reply to Nicholas Nethercote [:njn] from comment #4)
> Thank you for the info.
> 
> >  *
> > https://mxr.mozilla.org/mozilla-central/source/parser/html/nsHtml5AtomList.h
> > doesn't have to be separate from the main atom list. Initially, it wasn't
> > separate, but I made it separate on the advice I was given way back when. I
> > think the atom lists should merge to remove the complexity of atom
> > registration dealing with two lists.
> 
> There are several other atom lists, though they are much smaller than
> nsGkAtoms and nsHtml5Atoms. There are 6 or 7 atom lists in total.
> Registering multiple atom lists isn't much harder than registering a single
> list. However, there are a non-trivial number of duplicates across the
> lists, and merging them would remove the duplicates which would (a) shrink
> the binary, and (b) speed up table creation. It's a good idea; I'll add it
> to my todo list.

My concern was mainly the binary size.

> >  * The HTML parser optimizes for the rarity of having to dynamically
> > allocate atoms over binary or heap footprint. That's probably a bad idea.
> > The HTML parser should probably be changed to pre-declare notably fewer
> > names.
> 
> Any suggestions on how to choose which names are removed from the list?
> Maybe instrument table lookups to see which ones are infrequent?

The algorithm to get the minimal element and attribute tables is:
 1) Remove attributes of the form
    public static final AttributeName FOO = new AttributeName(ALL_NO_NS, SAME_LOCAL("foo"), ALL_NO_PREFIX, NCNAME_HTML | NCNAME_FOREIGN | NCNAME_LANG);
 2) Remove elements of the form
    public static final ElementName BAR = new ElementName("bar", "bar", TreeBuilder.OTHER);
 3) Add back the items that the compiler complains about.

After that, there are some obvious things to add back, such as the span element, but otherwise it's probably a matter of instrumentation.

> >  * Can we make static atoms actually static in the sense of putting them in
> > the data segment of the binaries?
> 
> There are two pieces to a "static atom": (a) the nsFakeStringBuffer
> containing the actual chars, and (b) the nsIAtom (implemented as a
> PermanentAtomImpl) that wraps the nsFakeStringBuffer. Currently (a) is
> static and (b) is heap-allocated. I assume you are suggesting that (b)
> become static as well?

Yes. Then the "static" nsHtml5AttributeNames and nsHtml5ElementNames could be baked into plain old data instead of the heap. ... Assuming vtables in POD are OK.

> It would increase binary size but might make start-up
> faster. PermanentAtomImpl is a type with a vtable, and I don't know if there
> are difficulties with statically allocating those.

I thought that was okay, but I don't actually know.

> >  * If on the main thread we want to have a single (lockless table), is there
> > a good proposal to populate a parser instance-specific atom table with the
> > static atoms in an efficient way?
> 
> No. I was hoping to avoid the need, given this bug's title. My only idea
> w.r.t. table structure is the one in the 3rd paragraph of comment 2: have
> one table for static atoms and one for dynamic atoms, with no overlap. But
> that would require two lookups for general atom lookup.

The parser assumes that there is a type that represents an interned identifier whose instances can be pointer compared and whose known-in-advance instances have memory addresses that are stable from app startup to shutdown.

Those are the constrains.

Having this type be nsIAtom and the known-in-advance instance be normal "static atoms" has the benefit  of the mapping from this type that the parser wants to the type that the DOM wants be trivial for the known-in-advance identifiers (static atomness check and pass-through).
Flags: needinfo?(hsivonen)
Depends on: 1392185
Whiteboard: [MemShrink]
Note that, per IRC discussion, this should be very straightforward to do by just reimplementing NS_GetStaticAtom on top of the regular atom table. However, Nick also wants to fix the special atom class in the HTML5 parser, and already has partial patches for it, so he's going to do both of these together.
(In reply to Bobby Holley (:bholley) from comment #7)
> Note that, per IRC discussion, this should be very straightforward to do by
> just reimplementing NS_GetStaticAtom on top of the regular atom table.
> However, Nick also wants to fix the special atom class in the HTML5 parser,
> and already has partial patches for it, so he's going to do both of these
> together.

I had thought that removing the table required the other clean-ups, but you're right, it doesn't. So I've posted the obvious patch here.
No longer depends on: 1392185
Comment on attachment 8954258 [details]
Bug 529808 - Remove the static atom table.

https://reviewboard.mozilla.org/r/223406/#review229578

I have two questions.

::: xpcom/ds/nsAtomTable.cpp:708
(Diff revision 1)
> +  return he && he->mAtom
> +       ? static_cast<nsStaticAtom*>(he->mAtom)
> +       : nullptr;

Don't we also need to check `he->mAtom->IsStaticAtom()` here?  Otherwise we risk returning a dynamic atom and treating it as a static atom.

(I'm also curious why `he->mAtom` wouldn't always be true.)
Attachment #8954258 - Flags: review?(nfroyd)
> > +  return he && he->mAtom
> > +       ? static_cast<nsStaticAtom*>(he->mAtom)
> > +       : nullptr;
> 
> Don't we also need to check `he->mAtom->IsStaticAtom()` here?  Otherwise we
> risk returning a dynamic atom and treating it as a static atom.
> 
> (I'm also curious why `he->mAtom` wouldn't always be true.)

Yikes! The condition is supposed to be:

> return he && he->mAtom->IsStaticAtom()

That should answer both questions. Thank you for catching that.

Surprisingly, I did a try push that looked good. My best guess is that NS_GetStaticAtom() is mostly/always called on atoms that really are static. I'll add some instrumentation to check that hypothesis shortly.
> My best guess is that
> NS_GetStaticAtom() is mostly/always called on atoms that really are static.

I should say: are static or unknown.
Comment on attachment 8954258 [details]
Bug 529808 - Remove the static atom table.

https://reviewboard.mozilla.org/r/223406/#review229668

This looks much better, thank you!
Attachment #8954258 - Flags: review?(nfroyd) → review+
(In reply to Nicholas Nethercote [:njn] from comment #12)
> > My best guess is that
> > NS_GetStaticAtom() is mostly/always called on atoms that really are static.
> 
> I should say: are static or unknown.

Nope. The instrumentation shows that NS_GetStaticAtom() is sometimes called on strings that belong to dynamic atoms -- about 250 times while starting the browser and opening up a few web pages. Huh.

Anyway, the updated patch fixes the problem.
https://hg.mozilla.org/mozilla-central/rev/cb5de5ee2ead
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla60
Assignee: nobody → n.nethercote
You need to log in before you can comment on or make changes to this bug.