Bug 54355 - Let the parser yield for layout before running scripts
Summary: Let the parser yield for layout before running scripts
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Other OS X 10.5
: P2 Normal
Assignee: Tony Gentilcore
URL:
Keywords:
Depends on: 56049 54574 54835 54942 55392 55414 55429 56143
Blocks: 45072
  Show dependency treegraph
 
Reported: 2011-02-13 08:28 PST by Tony Gentilcore
Modified: 2011-03-11 10:29 PST (History)
10 users (show)

See Also:


Attachments
Patch (9.02 KB, patch)
2011-02-13 08:52 PST, Tony Gentilcore
no flags Details | Formatted Diff | Diff
Patch (10.76 KB, patch)
2011-02-15 15:44 PST, Tony Gentilcore
no flags Details | Formatted Diff | Diff
Patch (8.74 KB, patch)
2011-02-18 10:21 PST, Tony Gentilcore
no flags Details | Formatted Diff | Diff
Patch (7.17 KB, patch)
2011-02-18 13:13 PST, Tony Gentilcore
no flags Details | Formatted Diff | Diff
Patch for landing (6.46 KB, patch)
2011-03-09 17:20 PST, Tony Gentilcore
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Tony Gentilcore 2011-02-13 08:28:39 PST
Let the parser yield for layout before running scripts
Comment 1 Tony Gentilcore 2011-02-13 08:52:14 PST
Created attachment 82263 [details]
Patch
Comment 2 Tony Gentilcore 2011-02-13 08:54:36 PST
FYI, I've not marked this for review yet because I'm planning to test it out some more on other machines.
Comment 3 Tony Gentilcore 2011-02-15 11:28:15 PST
I'm finished testing this out and am very happy w/ the performance. First paint time dramatically improved without regressing overall page load time. This change also enables bug 45072 to improve overall page load time without it regressing first paint time.

Here's a brief explanation of the test environment:
- OSX 10.6.6, 12G, 2x2.26GHz Quad-Core Xeon
- http://code.google.com/p/web-page-replay/ used to record snapshots of Alexa's top 45 websites
- Replayed each snapshot for a variable number of iterations (min 5, max 15) until stddev was below a threshold
- Replayed set of pages at 3 network configurations simulated with dummynet: unlimited; 5Mbps down/1Mbps up/40ms RTT; 1Mbps down/200Kbps up/60ms RTT
- Measured time to first paint and time to window load event

Page load time averages (without patch, with patch):
unlimited: 486ms, 485ms (-0.21%)
5meg: 832ms, 832ms (0%)
1meg: 1191ms, 1185ms (-0.51%)

First paint time averages (without patch, with patch):
unlimited: 196ms, 194 (-1.03%) 
5meg: 479ms, 431ms (-11.14%)
1meg: 577ms, 544 (-6.07%)

The averages don't tell the full story. On the 5meg connection, for instance. 33 of the 45 pages had no statistically significant change, but pages with certain blocking patterns had big improvements: youtube painted 100ms sooner, wikipedia 242ms, ebay 138ms, sohu.com 1269ms, espn 79ms, cnn 81ms. No page had a statistically significant regression in first paint time. Please let me know if you want to see the full data sets or think more testing is warranted.

Regarding the patch itself, any ideas for layout tests that make sense here?
Comment 4 Adam Barth 2011-02-15 12:16:19 PST
Comment on attachment 82263 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=82263&action=review

Some comments below.  Eric should look at this patch too, but your numbers are very impressive.

> Source/WebCore/ChangeLog:15
> +        No new tests. (OOPS!)

You have a nice description of the performance tests you ran in the bug.  Maybe put some of that information here?

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:440
> -bool HTMLDocumentParser::isWaitingForScripts() const
> +inline bool HTMLDocumentParser::isWaitingForScripts() const

Don't you need to mark this inline in the header too?

> Source/WebCore/html/parser/HTMLParserScheduler.cpp:106
> +    bool hasEverPainted = document->view() && document->view()->hasEverPainted();
> +    if (!hasEverPainted && isLayoutTimerActive(document)) {
> +        m_continueNextChunkTimer.startOneShot(0);
> +        return false;
> +    }

In the case where there's no view, can isLayoutTimerActive return true?  If so, it seems like we'll always return false here.  It seems like we should always return true if there's no view because there's no point in trying to optimize first paint time without a view!
Comment 5 Tony Gentilcore 2011-02-15 15:44:35 PST
> You have a nice description of the performance tests you ran in the bug.  Maybe put some of that information here?

Done.

> Don't you need to mark this inline in the header too?

Oops, this is a virtual method. Even though it is less readable, I reverted back to just checking isPaused :-(

> In the case where there's no view, can isLayoutTimerActive return true?  If so, it seems like we'll always return false here.  It seems like we should always return true if there's no view because there's no point in trying to optimize first paint time without a view!

Good catch, fixed.
Comment 6 Tony Gentilcore 2011-02-15 15:44:46 PST
Created attachment 82539 [details]
Patch
Comment 7 Eric Seidel (no email) 2011-02-15 16:03:43 PST
Comment on attachment 82539 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=82539&action=review

Lets talk about this on IRC.  I like the idea, but this is scary stuff and I am not convinced this added complication is all necessary/correct.

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:201
> +    ASSERT(isWaitingForScripts());

It's unclear to me what the differnece between isWaitingForScripts and isPaused is?

> Source/WebCore/html/parser/HTMLParserScheduler.cpp:97
> +bool HTMLParserScheduler::shouldRunScriptNow()

Seems like we could come up with a better name here.

Also, its strange that this does the chunk timer stuff, especially given the name.
Comment 8 Eric Seidel (no email) 2011-02-15 16:31:20 PST
Tony and I spoke on IRC about the possibility of tweaking our existing yield logic instead of adding this new special case.  I think the adding a case to our existing yield logic for more agressive yield before first paint makes more sense than adding a one-off for pre-script-execution yielding.

http://trac.webkit.org/browser/trunk/Source/WebCore/html/parser/HTMLParserScheduler.cpp#L33

Tony said that just lowering those constants would be bad as later in loads we don't want to be laying out as much.  But we talked about the possibility of adding a special-case lower constant for pre-first layout.

I spent a lot of effort trying to make the yielding understandable as part of the parser re-write (hence the new HTMLParserScheduler class) so I'm suspicious of any further complications to this (already complicated!) subsystem. :)
Comment 9 Eric Seidel (no email) 2011-02-15 16:32:43 PST
Btw, the comment:
	// FIXME: We would like this value to be 0.2.

http://trac.webkit.org/browser/trunk/Source/WebCore/html/parser/HTMLParserScheduler.cpp#L40

is a hold-over from the old parser.  I don't know who made the comment (without looking).  It might be worth trying a lower value these days.
Comment 10 Eric Seidel (no email) 2011-02-15 16:45:21 PST
Comment on attachment 82539 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=82539&action=review

> Source/WebCore/html/parser/HTMLParserScheduler.cpp:104
> +        m_continueNextChunkTimer.startOneShot(0);

Shouldn't this reset the chunk counts as well?  Seems it would need access to the PumpSession to do that.  I'm not sure the callsite has one.
Comment 11 Tony Gentilcore 2011-02-15 16:47:13 PST
BTW, here are my full results for posterity: https://spreadsheets.google.com/ccc?key=tHdzNBp8o0kuMKg3ycud2Zw&authkey=CJz69dsE#gid=1

Those are all first paint times, there's a tab for each network configuration and each time in there represents 5-15 iterations (depending on how noisy runs were). The tool also compares load time, dom content loaded, readyState interactive, and other details if you want more info.
Comment 12 Tony Gentilcore 2011-02-15 16:52:29 PST
(In reply to comment #9)
> Btw, the comment:
>     // FIXME: We would like this value to be 0.2.
> 
> http://trac.webkit.org/browser/trunk/Source/WebCore/html/parser/HTMLParserScheduler.cpp#L40
> 
> is a hold-over from the old parser.  I don't know who made the comment (without looking).  It might be worth trying a lower value these days.

I've been doing some archeology on those. Darin Adler added the FIXME along with the original value back in 2006. I was planning to look into more optimal values for these constants as well, but they are tricky because we don't want to be overly yield-y. However, I do like your idea for a step-off function instead of constants. For instance, we could have one value until we paint and then use another value afterwards. I'd need to test it out as this is all very sensitive and interacts in odd ways. That's part of the reason I was originally attracted to keeping the yield points at just before we run scripts. There was always a potential to yield there, so it seems pretty safe to force it at the same point.
Comment 13 Eric Seidel (no email) 2011-02-15 16:58:36 PST
Comment on attachment 82539 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=82539&action=review

OK.  I think this patch is fine with some cleanup.

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:185
> +    if (isWaitingForScripts()) {

Please add a comment which explains that there are two times the parser can yield.  One between tokens, and one before running scripts.  We check here to see which.

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:189
> +        if (isStopped() || isWaitingForScripts())

Why is it OK to return in the isWaitingForScripts() case?

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:190
> +            return;

Seems if we're waiting for scripts we should ASSERT here that we're scheduled.

You might split these early returns into separate ifs since the stopped one makes more sense (and needs less asserts or explanations) than the other.

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:195
>      pumpTokenizer(AllowYield);

Isn't is possible for a <script> tag to be the last tag and for us to have waited on it?  Will there then be anything for this pump to do?

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:263
> +        runScriptsForPausedTreeBuilder();

Why did you move the paused logic inside the runScriptsForPausedTreeBuilder?  I'm unsure if it's better that way or not.  I think my previous thinking was that the loop was trying to be explicit about when it got paused vs. not.

> Source/WebCore/html/parser/HTMLDocumentParser.cpp:455
> +    ASSERT(!isWaitingForScripts());

These ASSERT changes are not clear to me.

>> Source/WebCore/html/parser/HTMLParserScheduler.cpp:97
>> +bool HTMLParserScheduler::shouldRunScriptNow()
> 
> Seems like we could come up with a better name here.
> 
> Also, its strange that this does the chunk timer stuff, especially given the name.

I think it's importnat that the paralells between this and shouldContinueParsing be obvious.  We should probably put them right next to one antoher in the header.

I think this one shoudl also take a PumpSession and should clear it like shouldContinueParsing does.  Probably using some shared code (a helper method?) for yielding.

Maybe we should reverse the name?  shouldYieldBeforeRunningScripts()?  I'm not sure.  It's slightly confusing that the shouldContinueParsing() bit does the yielding, I agree.
Comment 14 Eric Seidel (no email) 2011-02-15 17:00:34 PST
I really like the idea of changing our yielding as we parse more.  Maybe that's overengineering.  But as you note, starting with an agressive value and then stepping bakc after first paint and maybe again after some amount of the page loads or whatever.  donno.
Comment 15 Tony Gentilcore 2011-02-15 18:14:59 PST
I have an idea for taking care of this comment in pumpTokenizer():
// FIXME: This loop body has is now too long and needs cleanup.
without making the loop more expensive per token. That will also allow this change to be cleaner. I'll explore that in another patch then get back to this.
Comment 16 Tony Gentilcore 2011-02-18 10:21:55 PST
Created attachment 82976 [details]
Patch
Comment 17 Tony Gentilcore 2011-02-18 10:27:20 PST
> > Source/WebCore/html/parser/HTMLDocumentParser.cpp:185
> > +    if (isWaitingForScripts()) {
> 
> Please add a comment which explains that there are two times the parser can yield.  One between tokens, and one before running scripts.  We check here to see which.

I'm hoping the new method names make that much more clear. Let me know if you think we still need a comment.

> Isn't is possible for a <script> tag to be the last tag and for us to have waited on it?  Will there then be anything for this pump to do?

That is possible and okay. The while-loop will break when it gets a NULL token.

> I think it's importnat that the paralells between this and shouldContinueParsing be obvious.  We should probably put them right next to one antoher in the header.

Hopefully the names tie them together more strongly now. I don't want to have to include FrameView.h from HTMLParserScheduler.h.

> I think this one shoudl also take a PumpSession and should clear it like shouldContinueParsing does.  Probably using some shared code (a helper method?) for yielding.

Done.
Comment 18 Eric Seidel (no email) 2011-02-18 10:55:47 PST
Comment on attachment 82976 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=82976&action=review

> Source/WebCore/html/parser/HTMLParserScheduler.cpp:101
> +    Document* document = m_parser->document();

So it's not clear to me why this one doesn't check the chunk stuff on session as well.   Maybe doing so doesn't add much?  I'm not sure if that needs a comment or not.

> Source/WebCore/html/parser/HTMLParserScheduler.cpp:104
> +        session.needsYield = true;

It seems this isn't used anymore. :)  We should just remove it again.
Comment 19 Tony Gentilcore 2011-02-18 11:01:37 PST
(In reply to comment #18)
> (From update of attachment 82976 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=82976&action=review
> 
> > Source/WebCore/html/parser/HTMLParserScheduler.cpp:101
> > +    Document* document = m_parser->document();
> 
> So it's not clear to me why this one doesn't check the chunk stuff on session as well.   Maybe doing so doesn't add much?  I'm not sure if that needs a comment or not.

They are different rules about when to yield. Respecting the #chunks and time limit from this check would negate its purpose. I'll add brief comment on each method.

> 
> > Source/WebCore/html/parser/HTMLParserScheduler.cpp:104
> > +        session.needsYield = true;
> 
> It seems this isn't used anymore. :)  We should just remove it again.

It is still used as the condition to schedule the resume in pumpTokenizer. I'll try to think of a cleaner way that avoid the return val + boolean weirdness (maybe you have ideas?).
Comment 20 Eric Seidel (no email) 2011-02-18 11:08:31 PST
(In reply to comment #19)
> (In reply to comment #18)
> > (From update of attachment 82976 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=82976&action=review
> > 
> > > Source/WebCore/html/parser/HTMLParserScheduler.cpp:101
> > > +    Document* document = m_parser->document();
> > 
> > So it's not clear to me why this one doesn't check the chunk stuff on session as well.   Maybe doing so doesn't add much?  I'm not sure if that needs a comment or not.
> 
> They are different rules about when to yield. Respecting the #chunks and time limit from this check would negate its purpose. I'll add brief comment on each method.

I meant more the other way.  Not preventing it from yielding, but that yielding coudl also be caused by the chujnk counters.  But I'm not sure it really matters.

> > 
> > > Source/WebCore/html/parser/HTMLParserScheduler.cpp:104
> > > +        session.needsYield = true;
> > 
> > It seems this isn't used anymore. :)  We should just remove it again.
> 
> It is still used as the condition to schedule the resume in pumpTokenizer. I'll try to think of a cleaner way that avoid the return val + boolean weirdness (maybe you have ideas?).
Comment 21 Tony Gentilcore 2011-02-18 11:20:10 PST
> I meant more the other way.  Not preventing it from yielding, but that yielding coudl also be caused by the chujnk counters.  But I'm not sure it really matters.

We the chunk number should not be able to change since we are guaranteed to check that after every chunk (token). I guess we could exceed the timer here under the same chunk count, but I don't think that really matters as we'd just get to that after the next token.


Anyway, will ping back when I straighten out the return vals.
Comment 22 Tony Gentilcore 2011-02-18 13:13:57 PST
Created attachment 83001 [details]
Patch
Comment 23 Eric Seidel (no email) 2011-02-18 13:17:34 PST
Comment on attachment 83001 [details]
Patch

What a gorgeous patch!  Thanks for all your hard work here!
Comment 24 WebKit Commit Bot 2011-02-18 23:57:24 PST
Comment on attachment 83001 [details]
Patch

Clearing flags on attachment: 83001

Committed r79104: <http://trac.webkit.org/changeset/79104>
Comment 25 WebKit Commit Bot 2011-02-18 23:57:31 PST
All reviewed patches have been landed.  Closing bug.
Comment 26 WebKit Commit Bot 2011-02-19 00:06:41 PST
The commit-queue encountered the following flaky tests while processing attachment 83001 [details]:

http/tests/xmlhttprequest/simple-cross-origin-progress-events.html bug 54798 (authors: ap@webkit.org and levin@chromium.org)
The commit-queue is continuing to process your patch.
Comment 27 Antti Koivisto 2011-02-22 01:14:16 PST
Would it hurt to always yield before script execution (that is remove the first paint test)?  In some cases the first paint may not be that meaningful yet and improved interactivity might be good too.
Comment 28 Tony Gentilcore 2011-02-22 09:23:54 PST
(In reply to comment #27)
> Would it hurt to always yield before script execution (that is remove the first paint test)?  In some cases the first paint may not be that meaningful yet and improved interactivity might be good too.

I tried that and the increased number of layouts pushed out the total load time. I also felt like the pages had more annoying visual shift w/ that behavior. My reasoning here is that there is a certain value in the first paint in that it is the first real indication to the user that the page is responding (even if there is little or no useful content).

Regarding this patch itself, I had to roll it back because it was causing flakiness on the chromium bots. It turns out we have a lot of layout tests that incorrectly assume the parser doesn't yield. Someone just pointed out this example on the webkit-dev list: <iframe onload="foo()"><script>function foo() {...}</script>. Since we wait 250ms to schedule the first layout, most tests didn't exercise the new yield. But the chromium debug bots ran certain tests slow enough that the new yield was exposing bugs in the tests.

To find them, I've made a local change to set defaultParserTimeLimit to 0 and defaultParserChunkSize to 1 which causes the tokenizer to yield between every token. It exposes the tests which aren't resilient to parser yields. I'm planning to fix those up, then roll forward my original patch.
Comment 29 Eric Seidel (no email) 2011-02-22 12:14:32 PST
(In reply to comment #28)
> To find them, I've made a local change to set defaultParserTimeLimit to 0 and defaultParserChunkSize to 1 which causes the tokenizer to yield between every token. It exposes the tests which aren't resilient to parser yields. I'm planning to fix those up, then roll forward my original patch.

FANTASTIC.  We did similarly when writing the HTML5 parser.
http://trac.webkit.org/browser/trunk/LayoutTests/html5lib/webkit-resumer.html
does similarly, but for the HTML5 spec (letting the parser yield between every character) which found a ton of bugs in the old parser and helpped us make the new parser resiliant to network variation.

I'm very glad you're fixing the layout tests.
Comment 30 Tony Gentilcore 2011-02-22 12:32:57 PST
Reopening since this is rolled back.
Comment 31 Xianzhu Wang 2011-02-23 22:21:57 PST
My last running of layout tests on chromium-linux with maximum parser yielding enabled showed that 1.7% of layout tests (253 of 15000) newly failed.

I have a concern about web page compatibility. Will this fix fail many existing web pages?
Comment 32 Tony Gentilcore 2011-03-09 17:20:52 PST
Created attachment 85263 [details]
Patch for landing
Comment 33 Tony Gentilcore 2011-03-09 17:21:36 PST
Re-landing same patch now that blocking bugs have been fixed.
Comment 34 Tony Gentilcore 2011-03-10 12:57:24 PST
Comment on attachment 85263 [details]
Patch for landing

Clearing flags on attachment: 85263

Committed r80749: <http://trac.webkit.org/changeset/80749>
Comment 35 Tony Gentilcore 2011-03-10 12:57:30 PST
All reviewed patches have been landed.  Closing bug.
Comment 36 Tony Gentilcore 2011-03-11 10:29:39 PST
Comment on attachment 85263 [details]
Patch for landing

Clearing flags on attachment: 85263

Committed r80861: <http://trac.webkit.org/changeset/80861>
Comment 37 Tony Gentilcore 2011-03-11 10:29:45 PST
All reviewed patches have been landed.  Closing bug.