Replace style sharing cousin list search with LRU

Replace style sharing cousin list search with LRU

The current implementation of style sharing uses a very confusing set of methods to
search a node's cousins in an attempt to find other nodes to share style with. This
patch replaces this confusing method with a simple LRU that allows us to find
nodes to share with even if they're not our cousins.

The previous implementation of this was reverted due to a performance regression
due to decreased sharing occurring in certain situations during parse time when
we'd clear the LRU after every node was appended. This updated patch uses RefPtrs
to allow these nodes to be held onto, and avoids clearing the LRU during attach,
and only when styles change.

Because this change introduces RefPtrs that can hold onto nodes while the style
resolver is active, Internal gc functions are updated to clear the style sharing list.

Previous codereview: https://codereview.chromium.org/23075004/

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

[leviw_travelin_and_unemployed, 2013-08-20 00:37:18]

I've looked into the performance of this a ton, and it's complicated. HTML5 full
render is a fraction of a percent slower with this patch, shadow dom and some
css tests are faster (the focus test is way faster, for example), and the
typical 25 tests are all quite close, with this and the current solution trading
back and forth for performance.

I still expect some noise from the bots, but I expect we'll ultimately be better
off.

[esprehn, 2013-08-20 00:48:01]

I dunno what's going on with the parent->document()->document() thing but that
looks wrong. Also what happens if I move an element between documents? I think
we'll share with the wrong one.

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/css/re...
File Source/core/css/resolver/SharedStyleFinder.cpp (right):

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/css/re...
Source/core/css/resolver/SharedStyleFinder.cpp:285: for
(StyleSharingList::iterator iter = styleSharingList.begin(); iter !=
styleSharingList.end(); ++iter) {
I think we usually use "it" for iterators.

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/css/re...
Source/core/css/resolver/SharedStyleFinder.cpp:286: if
(canShareStyleWithElement(context, iter->get())) {
if (!...)
  continue;

would make this nicer since then the whole loop isn't indented.

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/dom/Co...
File Source/core/dom/ContainerNode.cpp (right):

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/dom/Co...
Source/core/dom/ContainerNode.cpp:1040: if (StyleResolver* resolver =
parent->document()->document()->styleResolverIfExists())
document()->document() is nonsense. Why are you going through parent here
instead of just document() on yourself?

[leviw_travelin_and_unemployed, 2013-08-20 00:54:09]

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/css/re...
File Source/core/css/resolver/SharedStyleFinder.cpp (right):

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/css/re...
Source/core/css/resolver/SharedStyleFinder.cpp:286: if
(canShareStyleWithElement(context, iter->get())) {
On 2013/08/20 00:48:01, esprehn wrote:
> if (!...)
>   continue;
> 
> would make this nicer since then the whole loop isn't indented.

Sure.

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/dom/Co...
File Source/core/dom/ContainerNode.cpp (right):

https://chromiumcodereview.appspot.com/23049008/diff/14001/Source/core/dom/Co...
Source/core/dom/ContainerNode.cpp:1040: if (StyleResolver* resolver =
parent->document()->document()->styleResolverIfExists())
On 2013/08/20 00:48:01, esprehn wrote:
> document()->document() is nonsense. Why are you going through parent here
> instead of just document() on yourself?

document()->document() is a mistake, but this is a static function. There's no
this to use.

[leviw_travelin_and_unemployed, 2013-08-20 05:43:33]

The blink trybots aren't very happy today... anyhow, ptal.

[leviw_travelin_and_unemployed, 2013-08-22 17:12:35]

Bump.

[esprehn, 2013-08-22 17:33:02]

Clearing the cache inside updateTreeAfterInsertion doesn't look right, I think
you want to clear it right at the start of ::recalcStyle so it's always fresh.

https://codereview.chromium.org/23049008/diff/29001/Source/core/dom/Container...
File Source/core/dom/ContainerNode.cpp (right):

https://codereview.chromium.org/23049008/diff/29001/Source/core/dom/Container...
Source/core/dom/ContainerNode.cpp:1041: resolver->clearStyleSharingList();
Why do you need to clear the sharing list after inserting a new child? Note that
not all code paths even go through here, so if you need this clearing it here is
incomplete.

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

https://codereview.chromium.org/23049008/diff/29001/Source/core/dom/Document....
Source/core/dom/Document.cpp:1685: m_styleResolver->clearStyleSharingList();
I think it'd make more sense to clear it at the start of ::recalcStyle since
then you know it's always correct inside there. That'd also mean you wouldn't
need the other clear() calls.

https://codereview.chromium.org/23049008/diff/29001/Source/core/dom/Document....
Source/core/dom/Document.cpp:1936: m_styleResolver->clearStyleSharingList();
Why doesn't this function just call clearStyleResolver() ? It's not clear why we
even need a style resolver if the RenderView is destroyed (you can't recalcStyle
then anyway).

[leviw_travelin_and_unemployed, 2013-08-22 22:25:27]

On 2013/08/22 17:33:02, esprehn wrote:
> Clearing the cache inside updateTreeAfterInsertion doesn't look right, I think
> you want to clear it right at the start of ::recalcStyle so it's always fresh.

Doing this (this was actually my original strategy) does have web-facing
implications... It causes us to hold onto RefPtrs following a Style Recalc that
are there until another occurs, which breaks some lifetime tests
(http/tests/media/media-source/webkitmediasource-closed-on-htmlmediaelement-destruction.html
and svg/dom/SVGViewSpec-invalid-ref-crash.html specifically).

WDYT?

[esprehn, 2013-08-22 22:36:59]

On 2013/08/22 22:25:27, Levi wrote:
> On 2013/08/22 17:33:02, esprehn wrote:
> > Clearing the cache inside updateTreeAfterInsertion doesn't look right, I
think
> > you want to clear it right at the start of ::recalcStyle so it's always
fresh.
> 
> Doing this (this was actually my original strategy) does have web-facing
> implications... It causes us to hold onto RefPtrs following a Style Recalc
that
> are there until another occurs, which breaks some lifetime tests
>
(http/tests/media/media-source/webkitmediasource-closed-on-htmlmediaelement-destruction.html
> and svg/dom/SVGViewSpec-invalid-ref-crash.html specifically).
> 
> WDYT?

If you clear it at the start and end of recalcStyle the elements shouldn't live
any longer than before?

[leviw_travelin_and_unemployed, 2013-08-22 22:57:46]

On 2013/08/22 22:36:59, esprehn wrote:
> If you clear it at the start and end of recalcStyle the elements shouldn't
live
> any longer than before?

Sadly no... We still fail without the updateTreeAfterInsertion change :-/

[esprehn, 2013-08-22 23:06:09]

On 2013/08/22 22:57:46, Levi wrote:
> On 2013/08/22 22:36:59, esprehn wrote:
> > If you clear it at the start and end of recalcStyle the elements shouldn't
> live
> > any longer than before?
> 
> Sadly no... We still fail without the updateTreeAfterInsertion change :-/

Gross, that must be because of synchronous attaches which are filling the cache.

LGTM on this patch. We'll clean this up in the future once we lazy attach all
the time.

[commit-bot: I haz the power, 2013-09-05 16:01:24]

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

[commit-bot: I haz the power, 2013-09-05 17:02:12]

Change committed as 157311