HTMLConstructionSite: avoid n^2 running time for large scripts.

HTMLConstructionSite: avoid n^2 running time for large scripts.

Every time background parser sends chunk, tree is flushed.

If page contains very large script, then script node content is updated
many times. Every update is causes string concatenation.

Solution: do not flush pending text until it is mandatory.

Test: https://codereview.chromium.org/500363002
Test depends on: https://codereview.chromium.org/544453004/

BUG=410790
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=181635

[eseidel, 2014-08-23 19:39:59]

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

https://codereview.chromium.org/494993002/diff/1/Source/core/html/parser/HTML...
Source/core/html/parser/HTMLConstructionSite.cpp:695: flushPendingText(true);
We'll need to fix this to be an enum (bools make for unreadable callsites), and
I'll need to think harder about this patch on monday.  But I'm certainly open to
the idea. :)

[eseidel, 2014-08-23 19:43:39]

The reason why we added this whole pendingText system was to work around similar
N^2 issues for docs.  These apps could also just stop sending multi-meg inline
js. :)

Could you also at least link to a test in your CL, even if we don't land one? 
We have order-of-magnitude LayoutTests for bugs like these. I'm not sure how
well they work though (bug 232244).
http://www.chromium.org/developers/testing/time-complexity-tests

[eustas, 2014-08-26 07:30:37]

On 2014/08/23 19:43:39, eseidel wrote:
> The reason why we added this whole pendingText system was to work around
similar
> N^2 issues for docs.  These apps could also just stop sending multi-meg inline
> js. :)
> 
> Could you also at least link to a test in your CL, even if we don't land one? 
> We have order-of-magnitude LayoutTests for bugs like these. I'm not sure how
> well they work though (bug 232244).
> http://www.chromium.org/developers/testing/time-complexity-tests

Here is the test draft:
https://codereview.chromium.org/500363002

I've measured manually 3 cases: 250k, 500k and 1M lines.

Without patch medium time (excluding warm-up run):
1.9s, 6.3s, ~25s correspondingly.

With patch:
0.45s, 0.9s, 1.6s

Warm-up run lasts ~1.5s longer in both configurations / cases.

So n^2 is cleanly visible.

Unfortunately, we can't use time-complexity test framework until it is upgraded
to run async tests.

[eustas, 2014-08-26 08:12:25]

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

https://codereview.chromium.org/494993002/diff/1/Source/core/html/parser/HTML...
Source/core/html/parser/HTMLConstructionSite.cpp:695: flushPendingText(true);
On 2014/08/23 19:39:59, eseidel wrote:
> We'll need to fix this to be an enum (bools make for unreadable callsites),
and
> I'll need to think harder about this patch on monday.  But I'm certainly open
to
> the idea. :)

Added enum.

Now codesearch is working again. I've found that some execution paths require
mandatory flush. I've added flush mode to ::flush itself and updated
HTMLTreeBuilder.

[eseidel, 2014-08-26 16:26:39]

https://codereview.chromium.org/494993002/diff/20001/Source/core/html/parser/...
File Source/core/html/parser/HTMLConstructionSite.h (right):

https://codereview.chromium.org/494993002/diff/20001/Source/core/html/parser/...
Source/core/html/parser/HTMLConstructionSite.h:97: FacultativeFlush, // Do not
flush if there is no visible changes.
I think you'll find more people who know the word "optional":
http://en.wikipedia.org/wiki/Facultative

But it still doesn't really tell the caller when the optional flush does
anything, or when you should call optional flush vs. mandatory flush. 
Definitely need more comments here.

Another option would be:
FlushAlways,
FlushIfAtTextLimit,

[eustas, 2014-08-27 11:31:26]

https://codereview.chromium.org/494993002/diff/20001/Source/core/html/parser/...
File Source/core/html/parser/HTMLConstructionSite.h (right):

https://codereview.chromium.org/494993002/diff/20001/Source/core/html/parser/...
Source/core/html/parser/HTMLConstructionSite.h:97: FacultativeFlush, // Do not
flush if there is no visible changes.
On 2014/08/26 16:26:39, eseidel wrote:
> I think you'll find more people who know the word "optional":
> http://en.wikipedia.org/wiki/Facultative
> 
> But it still doesn't really tell the caller when the optional flush does
> anything, or when you should call optional flush vs. mandatory flush. 
> Definitely need more comments here.
> 
> Another option would be:
> FlushAlways,
> FlushIfAtTextLimit,

Sounds good. Thanks.

[eustas, 2014-08-29 07:37:03]

PTAL

[eseidel, 2014-08-29 08:53:09]

https://codereview.chromium.org/494993002/diff/40001/Source/core/html/parser/...
File Source/core/html/parser/HTMLTreeBuilder.h (right):

https://codereview.chromium.org/494993002/diff/40001/Source/core/html/parser/...
Source/core/html/parser/HTMLTreeBuilder.h:86: void flush() {
m_tree.flush(FlushIfAtTextLimit); }
What does this mean now that it doesn't always "flush"?

What does it mean now to flush the treebuilder?

I'm having some difficulty (at least at 2am) paging this code back into my
brain.  The comment above this looks wrong now though.

[eustas, 2014-09-01 09:46:44]

https://codereview.chromium.org/494993002/diff/40001/Source/core/html/parser/...
File Source/core/html/parser/HTMLTreeBuilder.h (right):

https://codereview.chromium.org/494993002/diff/40001/Source/core/html/parser/...
Source/core/html/parser/HTMLTreeBuilder.h:86: void flush() {
m_tree.flush(FlushIfAtTextLimit); }
On 2014/08/29 08:53:09, eseidel wrote:
> What does this mean now that it doesn't always "flush"?
> 
> What does it mean now to flush the treebuilder?
> 
> I'm having some difficulty (at least at 2am) paging this code back into my
> brain.  The comment above this looks wrong now though.

Fixed comment. Pulled "mode" up to actual call-site.

[kouhei (in TOK), 2014-09-02 15:56:05]

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

[kouhei (in TOK), 2014-09-02 15:56:06]

https://codereview.chromium.org/494993002/diff/60001/Source/core/html/parser/...
File Source/core/html/parser/HTMLConstructionSite.h (right):

https://codereview.chromium.org/494993002/diff/60001/Source/core/html/parser/...
Source/core/html/parser/HTMLConstructionSite.h:124: void
flushPendingText(FlushMode);
Nit: Can we make this method private? It is confusing to have both
flushPendingText() and flush() exposed to user, and flushPendingText() seems to
be only used internally.

[eustas, 2014-09-02 16:04:31]

On 2014/09/02 15:56:06, kouhei wrote:
>
https://codereview.chromium.org/494993002/diff/60001/Source/core/html/parser/...
> File Source/core/html/parser/HTMLConstructionSite.h (right):
> 
>
https://codereview.chromium.org/494993002/diff/60001/Source/core/html/parser/...
> Source/core/html/parser/HTMLConstructionSite.h:124: void
> flushPendingText(FlushMode);
> Nit: Can we make this method private? It is confusing to have both
> flushPendingText() and flush() exposed to user, and flushPendingText() seems
to
> be only used internally.

To make it private we need to move flush() implementation to cpp. But according
to comments it is intentionally left in .h :-(

[eseidel, 2014-09-02 17:10:58]

The CQ bit was checked by eseidel@chromium.org

[eseidel, 2014-09-02 17:10:58]

lgtm

[eseidel, 2014-09-02 17:11:07]

The CQ bit was unchecked by eseidel@chromium.org

[eseidel, 2014-09-02 17:11:38]

Actually, we need *some* kinda of test.  Otherwise I'm sure we'll break this
again.

[eseidel, 2014-09-02 17:11:51]

Also, please link to a bug.

[eseidel, 2014-09-05 17:02:53]

lgtm

Thanks!

[eustas, 2014-09-08 12:03:36]

The CQ bit was checked by eustas@chromium.org

[commit-bot: I haz the power, 2014-09-08 12:04:31]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/eustas@chromium.org/494993002/60001

[commit-bot: I haz the power, 2014-09-08 12:38:54]

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

[commit-bot: I haz the power, 2014-09-08 12:38:55]

Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink
(http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/2...)

[eustas, 2014-09-09 08:52:18]

The CQ bit was checked by eustas@chromium.org

[commit-bot: I haz the power, 2014-09-09 08:53:12]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/eustas@chromium.org/494993002/60001

[commit-bot: I haz the power, 2014-09-09 09:27:41]

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

[commit-bot: I haz the power, 2014-09-09 09:27:42]

Try jobs failed on following builders:
  linux_blink_rel on tryserver.blink
(http://build.chromium.org/p/tryserver.blink/builders/linux_blink_rel/builds/2...)

[eustas, 2014-09-09 10:58:15]

The CQ bit was checked by eustas@chromium.org

[commit-bot: I haz the power, 2014-09-09 10:59:07]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/eustas@chromium.org/494993002/80001

[commit-bot: I haz the power, 2014-09-09 11:28:30]

Committed patchset #5 (id:80001) as 181635

[jianli, 2014-09-09 18:46:30]

A revert of this CL (patchset #5 id:80001) has been created in
https://codereview.chromium.org/555223002/ by jianli@chromium.org.

The reason for reverting is: Speculative revert.

It may break the following blink sheriff bot:
http://build.chromium.org/p/chromium.webkit/builders/Android%20Tests%20%28dbg...

.