934607 - nsHtml5TreeBuilder::startTokenization takes significant amount time when parsing small innerHTML strings

Status: RESOLVED FIXED

(Core :: DOM: HTML Parser, defect)

Description

[Olli Pettay [:smaug][[e-mail]]]

http://mozilla.pettay.fi/moztests/innerhtmltest.html is a testcase I've taken from somewhere. That will be a lot faster once we have the don't-parse-short-none-tag-soup, but
if that data had a tag, it would be slow again.
nsHtml5TreeBuilder::startTokenization is about 10% of the time currently, 
and mostly because it allocates lots of stuff.

We should be able cache most of the data structures the method creates.

Comment 1

[(no longer active)]

Olli, is this still an issue?

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

Attachment: testcase

(This test doesn't get the fast path, since this has an element to parse.)

On linux we seem to be a lot faster than Chrome (312 vs 451), but we could also do significantly better too. 
nsHtml5TreeBuilder::startTokenization is very malloc heavy.
7% of the innerHTML in this case, all that is just malloc.
Overall of the innerHTML malloc is 18%

I was chatting today with hsivonen about reusing nsHtml5StackNodes. If we did that everywhere in parser, that should reduce malloc/free usage.
Allocating nsHtml5StackNodes show up in other profiles.

So, I guess this particular bug isn't very high priority, but I'd like to see better nsHtml5StackNodes usage.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

I guess jArray usage also causes malloc usage. Could we use AutoTArray?
Or if autoJArray is like AutoTArray, then that?

Comment 4

[Henri Sivonen (:hsivonen)]

(In reply to Olli Pettay [:smaug] (review queue closed. Please ask reviews from other DOM peers) from comment #2)
> I was chatting today with hsivonen about reusing nsHtml5StackNodes. If we
> did that everywhere in parser, that should reduce malloc/free usage.
> Allocating nsHtml5StackNodes show up in other profiles.

Let's make each tree builder allocate a chunk of memory sizeof(nsHtml5StackNode) * MAX_REFLOW_DEPTH and a free bitmap for it and allocate the stack nodes out of that. This way, the nodes can still be held behind pointers in two places, etc, and, thanks to the free bitmap, be freed out of order. It'll be mostly in order, though, so searching the the bitmap linearly when allocating shouldn't be too terrible, especially if the allocator remembers where the search ended the last time.

(In reply to Olli Pettay [:smaug] (review queue closed. Please ask reviews from other DOM peers) from comment #3)
> I guess jArray usage also causes malloc usage.

Where in the parser is this enough of a problem?

> Could we use AutoTArray?

No, it doesn't have the right semantics for passing it around. (The point of jArray is that it groups a length to a pointer so that it's almost as cheap to pass as a pointer, but unlike a bare pointer, the length comes along.)

> Or if autoJArray is like AutoTArray, then that?

Auto in autoJArray is about auto-deleting the buffer, not about stack-allocating the buffer.

Comment 5

[Henri Sivonen (:hsivonen)]

(In reply to Henri Sivonen (:hsivonen) from comment #4)
> (In reply to Olli Pettay [:smaug] (review queue closed. Please ask reviews
> from other DOM peers) from comment #2)
> > I was chatting today with hsivonen about reusing nsHtml5StackNodes. If we
> > did that everywhere in parser, that should reduce malloc/free usage.
> > Allocating nsHtml5StackNodes show up in other profiles.
> 
> Let's make each tree builder allocate a chunk of memory
> sizeof(nsHtml5StackNode) * MAX_REFLOW_DEPTH and a free bitmap for it and
> allocate the stack nodes out of that.

No need for a free bitmap. If upon free we null out a member of nsHtml5StackNode that's never null when live, we don't need a separate bitmap.

Comment 6

[Henri Sivonen (:hsivonen)]

On further thought, a fixed-size block might not work after all. Anyway, a custom allocator for these should be feasible.

Comment 7

[Henri Sivonen (:hsivonen)]

(In reply to Henri Sivonen (:hsivonen) from comment #4)
> > Could we use AutoTArray?
> 
> No, it doesn't have the right semantics for passing it around.

We could, however, use AutoTArray in the case jArray doesn't get passed around: nsHtml5HtmlAttributes doesn't really change that often, so there isn't a great benefit from keeping it in sync with Java by the means of the translator. If we moved that particular class to be untranslated, we could eliminate the most commonly-allocated multiple jArrays with a single AutoTArray whose storage would get allocated as part of the malloc for nsHtml5HtmlAttributes itself.

Let's do that.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Bug 1355441 filed about nsHtml5StackNodes

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Let's close this. If there is another testcase where we're slow in innerHTML parsing, better to file a new bug.

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

Attachment: test v2 (large innerHTML)

I was just testing something related to innerHTML and modified the test.