Make the HTMLDocumentParser yield more aggressively

Make the HTMLDocumentParser yield more aggressively

Depends on:
https://codereview.chromium.org/302063002/

When the BackgroundHTMLParser finishes a chunk of tokens
it posts a task to the main thread for tree-building.
Because the Chromium MessageQueue is a FIFO,
if the BackgroundHTMLParser schedules 10
chunks in a row (which it does) the main thread will
process all 10 chunks in a row before handling other work
sitting in the message queue (like RAF callbacks) while we
happily miss (possibly many) frames.

To fix this, I've made the HTMLDocumentParser only
take the chunk from the background parser in
didReceiveParsedChunkFromBackgroundParser
and save the chunk (as it already knew how to do
for the "speculations" code path), preload all
the resources in that chunk, and then post a second
task to actually do the processing (after any scheduled
work).  This has the effect of taking 10 chunks which
came in in a row and only processing them 1 at a time.

This will incur one extra round-trip through the
MessageLoop per chunk (which should be tiny compared
to the cost of mallocing all the nodes
represented by the chunk, etc), but will make it so
that the parser never processes more than one chunk
while we're waiting on other work.

I've also lowered the max-processing time from 500ms
to 8ms (we might want to go lower) to make the parser
yield more aggressively to RAF, etc.

I anticipate that this change may slow down
page load time numbers on Desktop Chrome (by a tiny percent)
and should increase responsiveness on mobile.

I created a pathological test case:
http://jsbin.com/nitobiru/35
Which repeatedly parses 10k divs while trying to keep to
60hz with RAF.  (It uses the newly-landed async srcdoc
support to drive the parser in the background.)

That test is pathological due to crbug.com/365919, but even
working around that bug with http://jsbin.com/nitobiru/38
it still only hits 26 fps or so.  Without that workaround /35
hits only 4fps.

Sending all chunks down the deferred work code-path
brought things up to 20fps, limiting the parser to only 8ms of
work at a time brought behavior to about 35fps on my linux desktop.

I believe that the async srcdoc work from bug 308321 combined with
this patch, now provides a viable option for sites to do async HTML
parsing with much lower risk of jank.

I also expect that this may improve Speed Index scores on both
desktop and devices as we're more aggressive about feeding
the preloader after this change (previously we would not issue
preload requests if we were about to process the tokens in that call).

BUG=356292

[eseidel, 2014-04-29 00:23:12]

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
File Source/core/html/parser/BackgroundHTMLParser.cpp (left):

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
Source/core/html/parser/BackgroundHTMLParser.cpp:48: static const size_t
outstandingTokenLimit = 10000;
I didn't mean to leave these in.

[eseidel, 2014-04-29 00:24:11]

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
File Source/core/html/parser/BackgroundHTMLParser.cpp (left):

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
Source/core/html/parser/BackgroundHTMLParser.cpp:48: static const size_t
outstandingTokenLimit = 10000;
On 2014/04/29 00:23:13, eseidel wrote:
> I didn't mean to leave these in.

These aren't bad.  I think they can just be deferred to a later change with more
mobile testing.

[tonyg, 2014-04-29 00:49:51]

This is both potentially very exciting and scary. This behavior is subtle and
not well covered by our bots. I wonder if Pat has any ideas for reasonable ways
to tune these constants. I also wonder whether we could cut this change into
smaller pieces.

[eseidel, 2014-04-29 01:12:42]

This change is 3 pieces.  I only intended to include 3 (not the chunk-size
change).  BUt I'm happy to land them one at a time.

[eseidel, 2014-04-29 01:16:16]

Sorry, I meant only 2.

I only intended to change:
1. always take the speculations path (extra round-trip through the queue +
preload everything + 1 at a time)
2. max speculations-path time limit.

#1 is the scary change.  Hard to make in pieces.
#2 really doesn't matter.  Since we still don't yield within a single chunk that
limit doesn't have much effect on the minimum parse time, only on the max number
of chunks we'd do in a row.

[Pat Meenan, 2014-04-29 12:55:17]

On 2014/04/29 01:16:16, eseidel wrote:
> Sorry, I meant only 2.
> 
> I only intended to change:
> 1. always take the speculations path (extra round-trip through the queue +
> preload everything + 1 at a time)
> 2. max speculations-path time limit.
> 
> #1 is the scary change.  Hard to make in pieces.
> #2 really doesn't matter.  Since we still don't yield within a single chunk
that
> limit doesn't have much effect on the minimum parse time, only on the max
number
> of chunks we'd do in a row.

I think the current benchmarks are actually in a good place to catch any issues
this might introduce (maybe not all of the benefit but that's ok).  With the
increased yielding this might actually be better for render and speed index, the
risk is that flat-out parse/load performance will get worse but the existing
benchmarks cover that case really well.  Theoretically it shouldn't get much
worse in that case either since it doesn't have a lot of other activity
scheduled while it's doing the initial parse anyway.  The only thing that comes
to mind as a risk is cases where inline script in the head has a tight timeout
loop for polling for some DOM state where it might get to interrupt parsing a
lot more frequently now.

I can run it against the typical live sites as well for another view but my vote
is to land the change and see what happens to the perf bots (particularly the
page load tests).

[eseidel, 2014-04-29 18:24:38]

I've removed the chunk-size changes (which I had not intended to include).

I could also make the pre-loading less aggressive, by making it only preload
chunks when the queue of speculative chunks is non-empty.

Or to exactly match previous behavior I could make it only preload in the cases
where it previously used the speculative chunk queue.

TL;DR: The preloading changes can be separated if that would make speed folks
feel more comfortable.

[abarth-chromium, 2014-04-29 18:28:58]

Code change LGTM.  I'll let you negotiate with the speed team about how to do
the perf evaluation.

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
File Source/core/html/parser/BackgroundHTMLParser.cpp (right):

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
Source/core/html/parser/BackgroundHTMLParser.cpp:47: // These numbers have not
been tuned.
Can you update the math in this comment?

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/Back...
Source/core/html/parser/BackgroundHTMLParser.cpp:50: // We limit our chucks to
1000 tokens, to make sure the main
This comment is now out of date.

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/HTML...
File Source/core/html/parser/HTMLDocumentParser.cpp (right):

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/HTML...
Source/core/html/parser/HTMLDocumentParser.cpp:329:
m_speculations.append(chunk);
Should we rename m_speculations?  I'm not sure that's exactly the right name.

IMHO, we'll eventually want to integrate this logic with a global scheduler that
understands whether we're trying to rAF every 16ms or we're in a bulk processing
phase.

https://codereview.chromium.org/258013009/diff/1/Source/core/html/parser/HTML...
Source/core/html/parser/HTMLDocumentParser.cpp:480: const double parserTimeLimit
= 0.008;
Again, this seems like a value the scheduler might want to tune dynamically.

[eseidel, 2014-04-29 18:29:58]

I completely agree with the scheduler comments.  I'm working on a design doc.

[eseidel, 2014-04-29 18:32:02]

m_speculations are still speculatively decoded chunks.  We could still reject
them if a chunk happens to document.write. :)

I've removed the BackgroundHTMLParser changes.

Based on Pat's advice I will plan to land and work with the perf-sheriff as
needed.

I'll be sure to stop by Tony's desk and check with him too.

[eseidel, 2014-04-29 18:32:11]

The CQ bit was checked by eseidel@chromium.org

[commit-bot: I haz the power, 2014-04-29 18:33:12]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/eseidel@chromium.org/258013009/20001

[commit-bot: I haz the power, 2014-04-29 18:55:30]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-04-29 18:55:31]

Try jobs failed on following builders:
  mac_blink_rel on tryserver.blink

[abarth-chromium, 2014-04-29 19:33:55]

lgtm

[eseidel, 2014-04-29 19:52:46]

Looks like I will need to either remove the preloader changes, or figure out why
it's causing a ton of changes to layout tests.  Will investigate more.

[ojan, 2014-04-29 22:41:57]

FWIW, WRT scaling back the constants, I'd vote for trying the most aggressive
thing (i.e. what your patch does now) and then scaling back if we find problems
with it. Otherwise, we'll perpetually be in a state where we only make small
incremental forward progress.

[eseidel, 2014-08-22 16:31:38]

We could probably salvage this CL.  This is about making the HTMLParser be a
better yielding citizen.  I'm not going to get back to this any time soon
though. :(

[kouhei (in TOK), 2014-08-24 01:46:40]

On 2014/08/22 16:31:38, eseidel wrote:
> We could probably salvage this CL.  This is about making the HTMLParser be a
> better yielding citizen.  I'm not going to get back to this any time soon
> though. :(

Got it. Now that the XHR patch is landed, I'm going to work on making parser
Blink scheduler friendly.

[eseidel, 2014-08-24 03:53:58]

For context, we decided the preloader was not ready for prime-time.  The result
was that we would avoid the "preload always" bits of thsi change, and instead
only preload in teh cases we did before, but always queue up chunks in the
speculation queue and pump the queue only after yielding.

[kouhei (in TOK), 2014-09-02 19:09:25]

I rebased this patch on to ToT and tested on
PerformanceTests/Parser/html-parser-threaded.html. This seems to regresses
performance from 24.0s to 28.3s.

I"ll take a closer look today.

[eseidel, 2014-09-02 19:17:16]

I'm not surprised that it woudl regress pure-parser performance.

I'm not sure that's bad.  We should look to see if that regression is a
necessary part of this change, or just an accident.

I'm willing to accept regressions to the HTML parser microbenchmarks which make
pages more smooth however.

[Sami, 2014-09-03 10:43:27]

skyostil@chromium.org changed reviewers:
+ skyostil@chromium.org

[Sami, 2014-09-03 10:43:28]

https://codereview.chromium.org/258013009/diff/20001/Source/core/html/parser/...
File Source/core/html/parser/HTMLDocumentParser.cpp (right):

https://codereview.chromium.org/258013009/diff/20001/Source/core/html/parser/...
Source/core/html/parser/HTMLDocumentParser.cpp:497: while
(!m_speculations.isEmpty()) {
No need to add it into this patch, but let me just point out a function in the
scheduler which may be useful here: Scheduler::shouldYieldForHighPriorityWork().
Eventually it will get replaced with proper "idle" task support, but for the
time being checking whether we should yield in this loop might be worth trying.
It may allow you to use a higher time limit too.

[tonyg, 2015-01-14 18:09:56]

tonyg@chromium.org changed reviewers:
- tonyg@chromium.org