First implementation of the paint slimming update algorithm

First implementation of the paint slimming update algorithm

This patch implements the basic paint slimming update algorithm as
described in [1]. The basic goal of the paint slimming update is to
merge new display items with the existing display items. By tracking
invalidations and using the paint order implied by the existing paint
list, an updated paint list can be created with a single walk through
both lists.

[1] https://docs.google.com/a/chromium.org/document/d/1w9vjJSV9Itk9UjhuaOMIIhd_LDYAfHbMepkwV5ZNPUI/edit#heading=h.gcmtb6aof29f

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

[pdr., 2014-10-31 05:16:56]

pdr@chromium.org changed reviewers:
+ chrishtr@chromium.org, leviw@chromium.org, schenney@chromium.org

[leviw_travelin_and_unemployed, 2014-10-31 19:10:03]

This isn't as ugly as you led me to believe! It's exciting!

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
Source/core/paint/ViewDisplayList.cpp:38: PaintList::iterator
ViewDisplayList::wasUninvalidatedRepaint(PaintList::iterator begin, const
DisplayItem& displayItem)
UninvalidatedRepaint? Let's come up with a better name.

wasRepaintWithoutInvalidation?

It's also weird that this function call sounds like a boolean question, but
returns an iterator answer.

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
Source/core/paint/ViewDisplayList.cpp:62: return displayItem.renderer() &&
m_invalidated.contains(displayItem.renderer());
I wonder if this hash lookup won't get expensive...

[leviw_travelin_and_unemployed, 2014-10-31 20:26:55]

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
Source/core/paint/ViewDisplayList.cpp:62: return displayItem.renderer() &&
m_invalidated.contains(displayItem.renderer());
On 2014/10/31 19:10:02, leviw wrote:
> I wonder if this hash lookup won't get expensive...

To be clear, I don't think we should take it away now, but we use bits on
RenderObjects that track invalidation in the current RACUN world to avoid such
things. Perhaps we could re-use them.

[pdr., 2014-10-31 20:37:56]

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
Source/core/paint/ViewDisplayList.cpp:38: PaintList::iterator
ViewDisplayList::wasUninvalidatedRepaint(PaintList::iterator begin, const
DisplayItem& displayItem)
On 2014/10/31 at 19:10:02, leviw wrote:
> UninvalidatedRepaint? Let's come up with a better name.
> 
> wasRepaintWithoutInvalidation?
> 
> It's also weird that this function call sounds like a boolean question, but
returns an iterator answer.

Good catch. Went with findNotUnDeRepaintWithoutUnNotWithDeInvalidation.

https://codereview.chromium.org/697543002/diff/1/Source/core/paint/ViewDispla...
Source/core/paint/ViewDisplayList.cpp:62: return displayItem.renderer() &&
m_invalidated.contains(displayItem.renderer());
On 2014/10/31 at 19:10:02, leviw wrote:
> I wonder if this hash lookup won't get expensive...

We should be able to store both this lookup and the repaint lookup as two bools
on renderobject, removing all lookups.

[chrishtr, 2014-10-31 21:30:12]

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
Source/core/paint/ViewDisplayList.cpp:42: PaintList::iterator
ViewDisplayList::findRepaintWithoutInvalidation(PaintList::iterator begin, const
DisplayItem& displayItem)
The name findRepaintWithoutInvalidation is not that great for explaining what
this is doing. How about just findDisplayItem? and move the check for
wasInvalidated up to the caller and don't call this method unless you want to
find the display item.

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
File Source/core/paint/ViewDisplayList.h (right):

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
Source/core/paint/ViewDisplayList.h:96: PaintList::iterator
findRepaintWithoutInvalidation(PaintList::iterator, const DisplayItem&);
This one deserves documentation.

[pdr., 2014-11-01 05:23:23]

Thanks for the reviews. PTAL

I've updated this and cleaned up the sharp edges, including adding more tests.
Followups will remove both of the maps used in this patch. There's a large FIXME
about handling clips that I think would be best handled in a followup as well.

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/40001/Source/core/paint/ViewDi...
Source/core/paint/ViewDisplayList.cpp:42: PaintList::iterator
ViewDisplayList::findRepaintWithoutInvalidation(PaintList::iterator begin, const
DisplayItem& displayItem)
On 2014/10/31 at 21:30:11, chrishtr wrote:
> The name findRepaintWithoutInvalidation is not that great for explaining what
this is doing. How about just findDisplayItem? and move the check for
wasInvalidated up to the caller and don't call this method unless you want to
find the display item.

Good idea. Done.

[leviw_travelin_and_unemployed, 2014-11-03 18:04:53]

lgtm

https://codereview.chromium.org/697543002/diff/60001/Source/core/paint/ViewDi...
File Source/core/paint/ViewDisplayList.cpp (right):

https://codereview.chromium.org/697543002/diff/60001/Source/core/paint/ViewDi...
Source/core/paint/ViewDisplayList.cpp:59: bool
ViewDisplayList::wasInvalidated(const DisplayItem& displayItem) const
FIXME: should use a bit on RenderObject.

[pdr., 2014-11-04 06:11:08]

The CQ bit was checked by pdr@chromium.org

[pdr., 2014-11-04 06:11:08]

Thanks for the reviews!

[commit-bot: I haz the power, 2014-11-04 06:12:09]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/697543002/80001

[commit-bot: I haz the power, 2014-11-04 07:15:55]

Committed patchset #5 (id:80001) as 184821