Avoid N^2 walk placing renderers when building the render tree

Avoid N^2 walk placing renderers when building the render tree

Blink resolves style by walking each element from first children 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.

While looking at this, I also found we have an N^2 loop for resolving
Nth last child selectors, and reversing the style resolve loop would have
caused the same issue for Nth child selectors. To fix prevent this regression,
I'm piping the child index down to the style resolver in the common case.
This ensures both Nth and Nth last should usually be O(1). 

Using the microbenchmark created for lazy layout,
http://elliottsprehn.com/personal/lazyblock/, this yields a speedup of
nearly 50% (4.75s -> 2.51s).

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

[leviw_travelin_and_unemployed, 2013-05-31 02:46:35]

The test failure is confusing, but reproduces locally. There are two less empty
lines on resolve-url-on-insertion.html with this patch.

[ojan, 2013-05-31 18:05:07]

+a few other people who know about style recalc.

I wonder if we should create a StyleRecalcState or something that we pass around
that includes the StyleChange and the childIndex. We've talking about wanting
such a thing for other cases. I can't recall right now what they were though.
Maybe it makes sense to hold off on this until we have a third thing we're
passing around everywhere?

I also wonder if maybe we want a RecalcStyleNodeIterator. All it would do is
loop through the nodes in reverse, but it would put the ordering of the loop in
one place instead of littered throughout the code. You could have it take an
optional startNode for the StyleResolver cases.

I'm not sure either of those are good suggestions, but throwing them out there
to see what you all think.

https://codereview.chromium.org/15871005/diff/4001/Source/core/css/SelectorCh...
File Source/core/css/SelectorChecker.cpp (right):

https://codereview.chromium.org/15871005/diff/4001/Source/core/css/SelectorCh...
Source/core/css/SelectorChecker.cpp:498: int count = context.childIndex ?
context.childIndex : 1 + siblingTraversalStrategy.countElementsBefore(element);
Not sure where, but that childIndices start at 1 probably deserves a comment
somewhere. :(

https://codereview.chromium.org/15871005/diff/4001/Source/core/css/SiblingTra...
File Source/core/css/SiblingTraversalStrategies.h (right):

https://codereview.chromium.org/15871005/diff/4001/Source/core/css/SiblingTra...
Source/core/css/SiblingTraversalStrategies.h:103: unsigned index =
sibling->childIndex();
I think this deserves a comment. Specifically, that we short-circuit here, but
not in countElementsBefore.

[leviw_travelin_and_unemployed, 2013-06-03 21:34:22]

Added some more comments and updated the test expectations. In the lazy block
microbenchmark, this yields a nearly 50% speedup to style resolution.

[ojan, 2013-06-03 23:03:29]

This looks good modulo the couple comments below. Also, can we attach this
benchmark to the bug and link to that attachment from the change description?
Performance patches that can't be reproduced because the test case goes away a
couple years from now are my pet peeve.

https://codereview.chromium.org/15871005/diff/13009/Source/core/css/SiblingTr...
File Source/core/css/SiblingTraversalStrategies.h (right):

https://codereview.chromium.org/15871005/diff/13009/Source/core/css/SiblingTr...
Source/core/css/SiblingTraversalStrategies.h:103: unsigned index =
sibling->childIndex();
I think here and in countElementsBefore we need comments explaining why it does
or doesn't make sense to early return (e.g. an early return in
countElementsBefore would actually be *wrong*, not just different performance
and the one here is needed to avoid n^2).

https://codereview.chromium.org/15871005/diff/13009/Source/core/css/resolver/...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/15871005/diff/13009/Source/core/css/resolver/...
Source/core/css/resolver/StyleResolver.cpp:615: static int iterationCount = 0;
Leftover debugging code?

https://codereview.chromium.org/15871005/diff/13009/Source/core/dom/Document.cpp
File Source/core/dom/Document.cpp (right):

https://codereview.chromium.org/15871005/diff/13009/Source/core/dom/Document....
Source/core/dom/Document.cpp:1685: // for (Node* n = firstChild(); n; n =
n->nextSibling()) {
derp.

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

https://codereview.chromium.org/15871005/diff/13009/Source/core/dom/shadow/Sh...
Source/core/dom/shadow/ShadowRoot.cpp:148: if (styleChangeType() ==
FullStyleChange)
Did you mean to include this in this patch?

[eseidel, 2013-06-04 06:29:35]

Elliot is your best reviewer here.  but lgtm.  childIndex being 0 is confusing.

https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
File Source/core/css/resolver/StyleResolver.cpp (right):

https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
Source/core/css/resolver/StyleResolver.cpp:570: inline void
StyleResolver::initElement(Element* e, int childIndex)
I might have called this "indexInParent"?

https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
File Source/core/css/resolver/StyleResolver.h (right):

https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
Source/core/css/resolver/StyleResolver.h:195: void initElement(Element*, int
childIndex = 0);
This method is so horrible and must die.  StyleResolver should not have
per-element resolve state. :(

https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
Source/core/css/resolver/StyleResolver.h:195: void initElement(Element*, int
childIndex = 0);
Why 0?  isn't that the firstChild?

[leviw_travelin_and_unemployed, 2013-06-04 21:17:39]

On 2013/06/04 06:29:35, eseidel wrote:
> Elliot is your best reviewer here.  but lgtm.  childIndex being 0 is
confusing.

I just uploaded another patch after a re-worked shadow-DOM test uncovered a bug
(needed to reverse the loop in ChildNodesLazySnapshot). I'm happy to wait for
Elliott to land if that makes you more comfortable.
 
>
https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
> File Source/core/css/resolver/StyleResolver.cpp (right):
> 
>
https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
> Source/core/css/resolver/StyleResolver.cpp:570: inline void
> StyleResolver::initElement(Element* e, int childIndex)
> I might have called this "indexInParent"?

I'm happy to rename this. I chose this for consistency with
Element::childIndex().

>
https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
> File Source/core/css/resolver/StyleResolver.h (right):
> 
>
https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
> Source/core/css/resolver/StyleResolver.h:195: void initElement(Element*, int
> childIndex = 0);
> This method is so horrible and must die.  StyleResolver should not have
> per-element resolve state. :(
> 
>
https://codereview.chromium.org/15871005/diff/18015/Source/core/css/resolver/...
> Source/core/css/resolver/StyleResolver.h:195: void initElement(Element*, int
> childIndex = 0);
> Why 0?  isn't that the firstChild?

There's a comment in StyleResolver.h about this being origined at 1. It's
confusing, I agree :(

[ojan, 2013-06-04 23:52:37]

lgtm

[esprehn, 2013-06-05 00:12:26]

You have an unneeded isTextNode() check. We should watch the perf bots since
this means walking the children twice in the general case to compute the
childIndex and then again to call recalcStyle. It'd be better to avoid that
first loop in Element:recalcStyle entirely if there's no nth-child or adjacent
selectors active on that element's children.

https://codereview.chromium.org/15871005/diff/27001/Source/core/css/SelectorC...
File Source/core/css/SelectorChecker.cpp (right):

https://codereview.chromium.org/15871005/diff/27001/Source/core/css/SelectorC...
Source/core/css/SelectorChecker.cpp:498: int count = context.childIndex ?
context.childIndex : 1 + siblingTraversalStrategy.countElementsBefore(element);
This global is so gross. :(

https://codereview.chromium.org/15871005/diff/27001/Source/core/css/SiblingTr...
File Source/core/css/SiblingTraversalStrategies.h (right):

https://codereview.chromium.org/15871005/diff/27001/Source/core/css/SiblingTr...
Source/core/css/SiblingTraversalStrategies.h:86: ++count;
Lets watch the perf bots for this one.

https://codereview.chromium.org/15871005/diff/27001/Source/core/dom/Container...
File Source/core/dom/ContainerNode.h (right):

https://codereview.chromium.org/15871005/diff/27001/Source/core/dom/Container...
Source/core/dom/ContainerNode.h:299: // Returns 0 if there is no next Node.
is no previous node?

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

https://codereview.chromium.org/15871005/diff/27001/Source/core/dom/Element.c...
Source/core/dom/Element.cpp:1464: if (n->isTextNode() || !n->isElementNode())
You don't need to check for isTextNode, it's already covered by the
isElementNode check.

[leviw_travelin_and_unemployed, 2013-06-06 23:41:34]

PTAL.

I had to make 2 more changes to get all the tests passing. This entailed
processing radio buttons and iframes in document order when inserting a document
fragment so that checked state was resolved correctly and the FrameTree is in
the proper order. For the record, I am worried there may be more issues not
covered by our tests.

[eseidel, 2013-06-06 23:47:57]

lgtm

https://codereview.chromium.org/15871005/diff/42001/LayoutTests/http/tests/ca...
File LayoutTests/http/tests/cache/subresource-expiration-1-expected.txt (left):

https://codereview.chromium.org/15871005/diff/42001/LayoutTests/http/tests/ca...
LayoutTests/http/tests/cache/subresource-expiration-1-expected.txt:12: 
These are empty text nodes no longer being rendered?

[commit-bot: I haz the power, 2013-06-06 23:48:11]

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

[commit-bot: I haz the power, 2013-06-07 04:48:28]

Change committed as 151996

[eseidel, 2013-06-10 20:38:36]

https://code.google.com/p/chromium/issues/detail?id=248058 claims this caused a
big perf regression.

[ojan, 2013-07-10 23:24:01]

lgtm

You and Elliot can fight over who gets to land their patch first...