Revert 151996 "Avoid N^2 walk placing renderers when building th..."

Revert 151996 "Avoid N^2 walk placing renderers when building th..."

> 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
> 
> Review URL: https://chromiumcodereview.appspot.com/15871005

TBR=leviw@chromium.org

[eseidel, 2013-06-10 20:37:32]

I'm making a new revert, I don't think this one will compile.

[eseidel, 2013-06-11 21:09:57]

The CQ doesn't seem to want to land this... despite the CQ box being checked for
over 22 hours.

[Ryan Tseng, 2013-06-11 21:12:57]

CQ isn't picking it up.  Is it busted?

Logs are saying:
2013-06-11 14:09:43,693    INFO Processing issue 16629006 (set(['try job
rietveld', 'reviewer_lgtm', 'tree status', 'project_bases']), 1)
2013-06-11 14:09:43,693    INFO svn://svn.chromium.org/blink/ not in
whitelist

What does that mean?


On Tue, Jun 11, 2013 at 2:09 PM, <eseidel@chromium.org> wrote:

> The CQ doesn't seem to want to land this... despite the CQ box being
> checked for
> over 22 hours.
>
>
https://codereview.chromium.**org/16629006/<https://codereview.chromium.org/1...
>

[iannucci, 2013-06-11 21:24:21]

On 2013/06/11 21:12:57, Ryan T. wrote:
> CQ isn't picking it up.  Is it busted?
> 
> Logs are saying:
> 2013-06-11 14:09:43,693    INFO Processing issue 16629006 (set(['try job
> rietveld', 'reviewer_lgtm', 'tree status', 'project_bases']), 1)
> 2013-06-11 14:09:43,693    INFO svn://svn.chromium.org/blink/ not in
> whitelist
> 
> What does that mean?
> 
> 
> On Tue, Jun 11, 2013 at 2:09 PM, <mailto:eseidel@chromium.org> wrote:
> 
> > The CQ doesn't seem to want to land this... despite the CQ box being
> > checked for
> > over 22 hours.
> >
> >
>
https://codereview.chromium.**org/16629006/%3Chttps://codereview.chromium.org...>
> >

I think CQ is looking for .../blink/trunk

[eseidel, 2013-06-11 21:26:44]

This revert bug was originally created by drover, then I separately reverted
with git and uploaded a new patch file to it.  Then I marked that second patch
file for CQ.

Presumably the base url from drover and the patch from git are incompatible?

[eseidel, 2013-06-11 22:27:33]

I've filed https://code.google.com/p/chromium/issues/detail?id=248720 about this
bug, and will close this issue and make a new one for the CQ to munch on.