Reverse style resolution to avoid N^2 walk when building the render tree

Reverse style resolution to avoid N^2 walk when building the render tree

Blink resolves style by walking each element from first child to last, but
when we go to insert their renderer, we look for the next renderer to insert
before. On the initial style resolve, this means we'll walk the entire DOM
tree trying to find the right renderer to insert before leading to an N^2
loop over the DOM on load.

This could be fixed by changing the semantics by which we insert renderers
(insert after instead of insert before). Instead, here I reverse the order
we resolve style. This should ensure that in the common case, we'll find
the renderer to insert before immediately.

Testing this change uncovered a bug in checkForSiblingStyleChanges whereby
we'd invalidate the wrong sibling in certain cases for changed children
of elements with directly adjacent sibling selectors. I fixed this
and added a simplified test (acid3 caught it with this change, but it's
a nightmare to debug).

We still attempt to process whitespace text nodes in DOM order by keeping a
stack-allocated vector of whitespace children we postpone recalcing style on
until the end. If we go past that limit, we process them and continue going.
Also removing the didReattach check to force whitespace reattachment. This
causes some whitespace layout tests results to change, but doesn't appear
to break anything.

BUG=288225, 245478
R=esprehn@chromium.org, ojan@chromium.org

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

[ojan, 2013-09-23 21:21:58]

lgtm

[commit-bot: I haz the power, 2013-09-23 21:22:09]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/1

[commit-bot: I haz the power, 2013-09-24 03:06:15]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/22001

[esprehn, 2013-09-24 03:50:19]

LGTM, amazing work!

[commit-bot: I haz the power, 2013-09-24 06:32:22]

Retried try job too often on win_blink_rel for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_...

[commit-bot: I haz the power, 2013-09-24 20:53:51]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/33012

[commit-bot: I haz the power, 2013-09-25 01:32:03]

Retried try job too often on win_blink_rel for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_...

[commit-bot: I haz the power, 2013-09-25 02:49:13]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/33012

[commit-bot: I haz the power, 2013-09-25 03:39:44]

Retried try job too often on win_blink_rel for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_...

[leviw_travelin_and_unemployed, 2013-09-25 18:19:02]

Looking at the Linux layout tests results, it's totally adding flake (the Acid3
test sometimes has an anonymous block with empty rendertexts, and sometimes
doesn't). I have a suspicion that this is a result of changed timing and not
logic, as I don't believe this actually alters how we determine needing
whitespace renderers. I may be wrong about that.

Tons of empty RenderText flake sucks... Any ideas? I'm game to dcommit and sort
this out in test expectations, or dive into trying to resolve the flake.

[leviw_travelin_and_unemployed, 2013-09-25 23:45:11]

FWIW: I can reproduce the flake on Acid3 on my Linux box. I get my "updated"
expectations 75% of the time, and the old ones the other 25%. I couldn't manage
to trigger flake on the same test without this patch.

[leviw_travelin_and_unemployed, 2013-09-30 22:16:56]

On 2013/09/25 23:45:11, Levi wrote:
> FWIW: I can reproduce the flake on Acid3 on my Linux box. I get my "updated"
> expectations 75% of the time, and the old ones the other 25%. I couldn't
manage
> to trigger flake on the same test without this patch.

PTAL. The extra complexity in Element makes me sad. This just further cements in
my mind that we need to come up with a better way to handle whitespace text
nodes.

Ojan and I discussed disabling the optimization for a day to get some
perf/memory data on what we're saving, just for curiosity sake.

[ojan, 2013-09-30 22:50:34]

lgtm, but I'd like Elliott to look over the recalcTextStyle bit before
committing this.

[esprehn, 2013-09-30 22:52:03]

You missed the Vector for ShadowRoot :/

LGTM if this works and we can evolve to fix that. This whitespace stuff is so
awful.

https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/shadow/Sh...
File Source/core/dom/shadow/ShadowRoot.cpp (right):

https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/shadow/Sh...
Source/core/dom/shadow/ShadowRoot.cpp:195: child->reattachWhitespaceSiblings();
You're missing the nasty whitespace stuff in here... I think you want to
encapsulate that inside something like a WhitespaceChildList that inside
append() understands when it hits the limit to call the recalc loop.

WhitespaceChildList whitespaceChildren;

whitespaceChildren.append(...);

to hide all the nastiness.

[esprehn, 2013-09-30 22:55:33]

https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp
File Source/core/dom/Element.cpp (right):

https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.c...
Source/core/dom/Element.cpp:1573: if (textChild->containsOnlyWhitespace()) {
This also makes us do the string scan for whitespace on every text node. The
boolean meant we didn't do that except when something reattached. We should be
really careful, this makes us probe the string contents of every string as the
recalcStyle loop walks down the tree.

Watch the perf bots for that.

[leviw_travelin_and_unemployed, 2013-09-30 22:56:58]

On 2013/09/30 22:55:33, esprehn wrote:
>
https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp
> File Source/core/dom/Element.cpp (right):
> 
>
https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.c...
> Source/core/dom/Element.cpp:1573: if (textChild->containsOnlyWhitespace()) {
> This also makes us do the string scan for whitespace on every text node. The
> boolean meant we didn't do that except when something reattached. We should be
> really careful, this makes us probe the string contents of every string as the
> recalcStyle loop walks down the tree.
> 
> Watch the perf bots for that.

Yeah :-/

I ran the perf tests locally with this and didn't see a regression, but I don't
trust it.

If you come up with a new idea to avoid this I'd love to hear it.

[esprehn, 2013-09-30 23:03:12]

On 2013/09/30 22:56:58, Levi wrote:
> ...
> > 
> > Watch the perf bots for that.
> 
> Yeah :-/
> 
> I ran the perf tests locally with this and didn't see a regression, but I
don't
> trust it.
> 
> If you come up with a new idea to avoid this I'd love to hear it.

Lets land this and watch the perf bots. The n^2 inside innerHTML is super bad
and this fixes that. A 2% regression from whitespace silliness is better than a
100%+ regression from adding the n^2 into innerHTML'ed content.

[ojan, 2013-10-02 00:56:54]

lgtm

The change description could explain why all these expected results change.

[commit-bot: I haz the power, 2013-10-02 17:58:50]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/89001

[commit-bot: I haz the power, 2013-10-02 18:47:57]

Sorry for I got bad news for ya.
Compile failed with a clobber build on win_blink_rel.
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_...
Your code is likely broken or HEAD is junk. Please ensure your
code is not broken then alert the build sheriffs.
Look at the try server FAQ for more details.

[commit-bot: I haz the power, 2013-10-02 20:41:55]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/105001

[commit-bot: I haz the power, 2013-10-02 23:16:14]

Retried try job too often on win_blink_rel for step(s) webkit_lint,
webkit_python_tests, webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_...

[commit-bot: I haz the power, 2013-10-03 18:24:11]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/119001

[leviw_travelin_and_unemployed, 2013-10-03 20:33:58]

Committed patchset #19 manually as r158839 (presubmit successful).