Slimming Paint phase 2 compositing algorithm plumbing & skeleton display list API.

Slimming Paint phase 2 compositing algorithm plumbing & skeleton display list API.

BUG=481592

[chrishtr, 2015-07-22 18:23:28]

https://codereview.chromium.org/1238123004/diff/20001/public/platform/WebDisp...
File public/platform/WebDisplayList.h (right):

https://codereview.chromium.org/1238123004/diff/20001/public/platform/WebDisp...
public/platform/WebDisplayList.h:24: virtual const WebVector<WebDisplayItem>&
webDisplayItems() const = 0;
This really should just be ListContainer<DisplayItem> This representation is
just something to get it to compile pre-Blink/cc merge.

[jbroman, 2015-07-22 21:20:06]

jbroman@chromium.org changed reviewers:
+ jbroman@chromium.org

[jbroman, 2015-07-22 21:20:07]

https://codereview.chromium.org/1238123004/diff/260001/public/platform/WebCon...
File public/platform/WebContentLayerClient.h (right):

https://codereview.chromium.org/1238123004/diff/260001/public/platform/WebCon...
public/platform/WebContentLayerClient.h:74: virtual const WebDisplayList*
displayList() const { return 0; };
What will cc do with the display list for a layer? In particular, will it do
anything other than paint its contents?

[chrishtr, 2015-07-22 22:09:59]

https://codereview.chromium.org/1238123004/diff/260001/public/platform/WebCon...
File public/platform/WebContentLayerClient.h (right):

https://codereview.chromium.org/1238123004/diff/260001/public/platform/WebCon...
public/platform/WebContentLayerClient.h:74: virtual const WebDisplayList*
displayList() const { return 0; };
On 2015/07/22 at 21:20:07, jbroman wrote:
> What will cc do with the display list for a layer? In particular, will it do
anything other than paint its contents?

cc will raster it yeah. This is the representation of the slices of the display
list that should be rastered into this particular content layer. This way there
are no extra copies in order to get them into an iterable data structure..

[chrishtr, 2015-07-23 14:29:43]

chrishtr@chromium.org changed reviewers:
+ enne@chromium.org, pdr@chromium.org, weiliangc@chromium.org

[chrishtr, 2015-07-23 14:29:44]

Please review. The patch is still rough, please focus for the moment on the
structure of the API.

Also note that some pieces of the API are not fully connected or optimized,
please take that into account.

[jbroman, 2015-07-23 19:44:05]

At a high level, seems reasonable. I would suggest leaving diffs out of the
initially landing patch, and landing diffing code in a followup.

[chrishtr, 2015-07-23 20:52:24]

On 2015/07/23 at 19:44:05, jbroman wrote:
> At a high level, seems reasonable. I would suggest leaving diffs out of the
initially landing patch, and landing diffing code in a followup.

I updated it to remove the implementation of DisplayListDiff, and instead add a
TODO.

[Ian Vollick, 2015-07-23 22:53:05]

vollick@chromium.org changed reviewers:
+ vollick@chromium.org

[Ian Vollick, 2015-07-23 22:53:06]

https://codereview.chromium.org/1238123004/diff/320001/Source/core/dom/Docume...
File Source/core/dom/DocumentLifecycle.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/core/dom/Docume...
Source/core/dom/DocumentLifecycle.h:68: // TODO(chrishtr): add lifecycle states
for scrolling update and paint.
This sounds exciting. Where will the scrolling update fit in the document
lifecycle? After paint, before compositing?

[chrishtr, 2015-07-23 23:57:39]

https://codereview.chromium.org/1238123004/diff/320001/Source/core/dom/Docume...
File Source/core/dom/DocumentLifecycle.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/core/dom/Docume...
Source/core/dom/DocumentLifecycle.h:68: // TODO(chrishtr): add lifecycle states
for scrolling update and paint.
On 2015/07/23 at 22:53:06, vollick (ooo until July 27) wrote:
> This sounds exciting. Where will the scrolling update fit in the document
lifecycle? After paint, before compositing?

t has to be after compositing also, to map scrolling requests to the right
backing. This is what we do pre-slimming-paint also:

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...

[pdr., 2015-07-24 05:37:51]

https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
File Source/core/compositing/DisplayListCompositingBuilder.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
Source/core/compositing/DisplayListCompositingBuilder.cpp:15:
DisplayItemTransformTreeBuilder transformTreeBuilder;
Can you talk a bit about how fixed position diffs might work here? I'm thinking
through how the diff format would need to contain layer diffs which seems to
introduce a chicken-and-egg issue.

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp:63: //
TODO(chrishtr): use |displayListDiff| to optimize.
Can you expand a little about how the diff would help? Would the DisplayListDiff
contains transform diff information?

[chrishtr, 2015-07-24 14:53:45]

Thank you for these questions, they are insightful and important. I have tried
to give a complete response.

One might argue that this deserves a careful design document explaining the ins
and outs, which is certainly one option. Another is to first prototype to
understand the cases and performance in practice, and document as we go and
after the fact. I prefer the latter for this situation, in part because of the
positive experience I think we had with using implementation experience to help
us understand the right structure of a DisplayItemList and the right merge
algorithm (which ended up being significantly different than the one we design
doc'ed), though the thought and discussion we are putting into the design this
week is definitely valuable.

https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
File Source/core/compositing/DisplayListCompositingBuilder.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
Source/core/compositing/DisplayListCompositingBuilder.cpp:15:
DisplayItemTransformTreeBuilder transformTreeBuilder;
On 2015/07/24 at 05:37:51, pdr wrote:
> Can you talk a bit about how fixed position diffs might work here? I'm
thinking through how the diff format would need to contain layer diffs which
seems to introduce a chicken-and-egg issue.

Fixed position display items would be emitted as they are already today (as part
of the DisplayItemList), and the diff format would have no special treatment of
{Begin,End}FixedPositionDisplayItems. If they are part of the diff (meaning they
might have changed) then the corresponding part of the transform tree and layer
structure would be rebuilt.

Jeremy's design doc has additional details:

https://docs.google.com/document/d/1VWjdq8hCJlNbak5ZyAsnLh-0--Hl_wht0xyuagODl...

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp:63: //
TODO(chrishtr): use |displayListDiff| to optimize.
On 2015/07/24 at 05:37:51, pdr wrote:
> Can you expand a little about how the diff would help? Would the
DisplayListDiff contains transform diff information?

Transform-related display items might occur in the diff. In those cases, some or
all of the transform tree would have to be rebuilt. If no transform-related
display items occur in the diff then the diff can be applied to the display
items comprising the 2D regions between the transform-related display items.

The equivalent optimizations we have today are in the CompositingUpdateType
enums in DeprecatedPaintLayerCompositor:

enum CompositingUpdateType {
    CompositingUpdateNone,
    CompositingUpdateAfterGeometryChange,
    CompositingUpdateAfterCompositingInputChange,
    CompositingUpdateRebuildTree,
};

CompositingUpdateNone is the default, and happens when "regular" invalidations
happen that somehow Blink knows don't affect the size, ordering, quantity and
positioning of the DeprecatedPaintLayers, and so the invalidations can't
possibly affect compositing (though this of course is incorrect already because
of the fundamental compositing bug).

In this case the new system will handle it by the display list diff only
containing changes that are between layerization hint boundaries. This means
that the diff needs to be smart enough that if a hint moves its index in the
display list, but is otherwise unchanged (e.g. its client id is the same), then
it is not part of the diff. This allows non-layerization display items to come
and go as a developer modifies the contents of a composited layer, without
causing rebuild. I think this can be implemented without too much trouble in the
diff algorithm.

If the above properties of the diff algorithm hold, then it should be
straightforward to notice that the transform tree is unchanged in
DisplayItemTransformTreeBuilder, and therefore DisplayListCompsitingBuilder can
use that fact to only invalidate whatever is now dirty inside a composited
layer.

CompositingUpdateAfterGeometryChange happens only when attempting "direct"
compositing updates, which is basically transform, opacity and scrolling of a
transform node. The way this would be implemented in the new system is to have
an update which modifies only the transform display item that implements the
transform, opacity or scrolling update (perhaps via the same functions in
DeprecatedPaintLayer that already set CompositingUpdateAfterGeometryChange
today).

The merge algorithm would output the new display list, plus a diff that says
only the transform display item changed. The code here would then easily notice
that, and compare the old and new transform display items to effect the change.
You might say that this is a lot of work for a simple change, and I agree that
it's the case where the amount of work relative to what is done today is the
highest. My response is that it's important for code sanity and layering to
represent diffs to display lists uniformly, and to make it fast (if necessary)
by optimizing the merge algorithm for such cases to be faster. Though the merge
algorithm already has optimizations for copying common subsequences (implemented
by Xianzhu) that should make this exact case fast. Doing it in a one-off way
will IMO result in difficult to understand code which can poke at compositing
from various places and encourage code layering violations.

The difference between CompositingUpdateAfterCompositingInputChange and
CompositingUpdateRebuildTree is that in
CompositingUpdateAfterCompositingInputChange mode  the code in
DeprecatedPaintLayerCompositor attempts to walk through the algorithm deciding
layerization, and if it manages to make it through without changing any
layerization decisions, it keeps the current tree and mutates its various
geometry parameters based on the new state. Otherwise it bails and performs
CompositingUpdateRebuildTree, which is the full rebuild hammer.

I think the equivalent optimizations for
CompositingUpdateAfterCompositingInputChange can be implemented directly in
DisplayListCompositingBuilder without the guessing process from various call
sites in Blink (e.g. in the call sites in DeprecatedPaintLayer it's not clear
today why exactly those situations deserve
CompositingUpdateAfterCompositingInputChange but others deserve
CompositingUpdateRebuildTree. The difference comes down to "it seems to work"
most of the time).

and GraphicsLayerUpdateScope in CompositedDeprecatedPaintLayerMapping:

enum GraphicsLayerUpdateScope {
    GraphicsLayerUpdateNone,
    GraphicsLayerUpdateLocal,
    GraphicsLayerUpdateSubtree,
};

GraphicsLayerUpdateNone is similar to CompositingUpdateNone, yet more
specialized.

GraphicsLayerUpdateLocal is supposed to be set when you know that a
GraphicsLayer but not its children need to be updated. There are three use cases
of this field. Two are arguably obscure, and the third is the direct compositing
update case that I discussed above in the context of
CompositingUpdateAfterGeometryChange.

[chrishtr, 2015-07-24 14:56:37]

On 2015/07/24 at 14:53:45, chrishtr wrote:
> Thank you for these questions, they are insightful and important. I have tried
to give a complete response.
> 
> One might argue that this deserves a careful design document explaining the
ins and outs, which is certainly one option. Another is to first prototype to
understand the cases and performance in practice, and document as we go and
after the fact. I prefer the latter for this situation, in part because of the
positive experience I think we had with using implementation experience to help
us understand the right structure of a DisplayItemList and the right merge
algorithm (which ended up being significantly different than the one we design
doc'ed), though the thought and discussion we are putting into the design this
week is definitely valuable.
> 
>
https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
> File Source/core/compositing/DisplayListCompositingBuilder.cpp (right):
> 
>
https://codereview.chromium.org/1238123004/diff/320001/Source/core/compositin...
> Source/core/compositing/DisplayListCompositingBuilder.cpp:15:
DisplayItemTransformTreeBuilder transformTreeBuilder;
> On 2015/07/24 at 05:37:51, pdr wrote:
> > Can you talk a bit about how fixed position diffs might work here? I'm
thinking through how the diff format would need to contain layer diffs which
seems to introduce a chicken-and-egg issue.
> 
> Fixed position display items would be emitted as they are already today (as
part of the DisplayItemList), and the diff format would have no special
treatment of {Begin,End}FixedPositionDisplayItems. If they are part of the diff
(meaning they might have changed) then the corresponding part of the transform
tree and layer structure would be rebuilt.
> 
> Jeremy's design doc has additional details:
> 
>
https://docs.google.com/document/d/1VWjdq8hCJlNbak5ZyAsnLh-0--Hl_wht0xyuagODl...
> 
>
https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
> File Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp
(right):
> 
>
https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
> Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp:63: //
TODO(chrishtr): use |displayListDiff| to optimize.
> On 2015/07/24 at 05:37:51, pdr wrote:
> > Can you expand a little about how the diff would help? Would the
DisplayListDiff contains transform diff information?
> 
> Transform-related display items might occur in the diff. In those cases, some
or all of the transform tree would have to be rebuilt. If no transform-related
display items occur in the diff then the diff can be applied to the display
items comprising the 2D regions between the transform-related display items.
> 
> The equivalent optimizations we have today are in the CompositingUpdateType
enums in DeprecatedPaintLayerCompositor:
> 
> enum CompositingUpdateType {
>     CompositingUpdateNone,
>     CompositingUpdateAfterGeometryChange,
>     CompositingUpdateAfterCompositingInputChange,
>     CompositingUpdateRebuildTree,
> };
> 
> CompositingUpdateNone is the default, and happens when "regular" invalidations
happen that somehow Blink knows don't affect the size, ordering, quantity and
positioning of the DeprecatedPaintLayers, and so the invalidations can't
possibly affect compositing (though this of course is incorrect already because
of the fundamental compositing bug).
> 
> In this case the new system will handle it by the display list diff only
containing changes that are between layerization hint boundaries. This means
that the diff needs to be smart enough that if a hint moves its index in the
display list, but is otherwise unchanged (e.g. its client id is the same), then
it is not part of the diff. This allows non-layerization display items to come
and go as a developer modifies the contents of a composited layer, without
causing rebuild. I think this can be implemented without too much trouble in the
diff algorithm.

To give credit where due, the points about allowing hint display items to change
indices in the DisplayItemList without diffs saying they changed is a result of
collaboration with Wei when she was in SFO.

> 
> If the above properties of the diff algorithm hold, then it should be
straightforward to notice that the transform tree is unchanged in
DisplayItemTransformTreeBuilder, and therefore DisplayListCompsitingBuilder can
use that fact to only invalidate whatever is now dirty inside a composited
layer.
> 
> CompositingUpdateAfterGeometryChange happens only when attempting "direct"
compositing updates, which is basically transform, opacity and scrolling of a
transform node. The way this would be implemented in the new system is to have
an update which modifies only the transform display item that implements the
transform, opacity or scrolling update (perhaps via the same functions in
DeprecatedPaintLayer that already set CompositingUpdateAfterGeometryChange
today).
> 
> The merge algorithm would output the new display list, plus a diff that says
only the transform display item changed. The code here would then easily notice
that, and compare the old and new transform display items to effect the change.
You might say that this is a lot of work for a simple change, and I agree that
it's the case where the amount of work relative to what is done today is the
highest. My response is that it's important for code sanity and layering to
represent diffs to display lists uniformly, and to make it fast (if necessary)
by optimizing the merge algorithm for such cases to be faster. Though the merge
algorithm already has optimizations for copying common subsequences (implemented
by Xianzhu) that should make this exact case fast. Doing it in a one-off way
will IMO result in difficult to understand code which can poke at compositing
from various places and encourage code layering violations.
> 
> The difference between CompositingUpdateAfterCompositingInputChange and
CompositingUpdateRebuildTree is that in
CompositingUpdateAfterCompositingInputChange mode  the code in
DeprecatedPaintLayerCompositor attempts to walk through the algorithm deciding
layerization, and if it manages to make it through without changing any
layerization decisions, it keeps the current tree and mutates its various
geometry parameters based on the new state. Otherwise it bails and performs
CompositingUpdateRebuildTree, which is the full rebuild hammer.
> 
> I think the equivalent optimizations for
CompositingUpdateAfterCompositingInputChange can be implemented directly in
DisplayListCompositingBuilder without the guessing process from various call
sites in Blink (e.g. in the call sites in DeprecatedPaintLayer it's not clear
today why exactly those situations deserve
CompositingUpdateAfterCompositingInputChange but others deserve
CompositingUpdateRebuildTree. The difference comes down to "it seems to work"
most of the time).
> 
> and GraphicsLayerUpdateScope in CompositedDeprecatedPaintLayerMapping:
> 
> enum GraphicsLayerUpdateScope {
>     GraphicsLayerUpdateNone,
>     GraphicsLayerUpdateLocal,
>     GraphicsLayerUpdateSubtree,
> };
> 
> GraphicsLayerUpdateNone is similar to CompositingUpdateNone, yet more
specialized.
> 
> GraphicsLayerUpdateLocal is supposed to be set when you know that a
GraphicsLayer but not its children need to be updated. There are three use cases
of this field. Two are arguably obscure, and the third is the direct compositing
update case that I discussed above in the context of
CompositingUpdateAfterGeometryChange.

[enne (OOO), 2015-07-24 18:19:24]

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/ContentLayerDelegate.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/ContentLayerDelegate.h:70: // This is only set on a
root graphics layer. Alternatively, this could be set on the layer tree host.
On the LTH, yes please.

[weiliangc, 2015-07-24 19:17:15]

Thanks for putting this together!

My main question is that since right now we have a DisplayItemList to
WebDisplayItemList conversion, maybe it'd be ok for WebLayers to own partial
WebDisplayItemList?

Right now I think there is a risk that we are rebuilding WebDisplayItemList by
iterating layers, and that invalidates the indices we saved on DisplayList.

And a very Bike Shedding request, maybe we can have names more distinctive than
DisplayItemList and DisplayList? Call them Global and Partial maybe?

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/ContentLayerDelegate.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/ContentLayerDelegate.cpp:98:
m_painter->displayList()->displayItemInternal(i).appendToWebDisplayItemList(webDisplayItemList);
Is it possible that this line changes the order of DisplayItems in the global
DisplayItemList, thus invalidate the indices we saved in the offset of
WebDisplayList on each layer?

Since we'd have to convert DisplayItem to WebDisplayItem, maybe we could let
Layers own the partial WebDisplayItemList? WDYT?

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/ContentLayerDelegate.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/ContentLayerDelegate.h:70: // This is only set on a
root graphics layer. Alternatively, this could be set on the layer tree host.
On 2015/07/24 at 18:19:24, enne wrote:
> On the LTH, yes please.

It'd make sense for the global DisplayItemList to be on LTH too I think.

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemList.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemList.h:69: void
commitNewDisplayItems(DisplayListDiff* = 0);
What owns the DisplayListDiff? Root Graphics Layer?

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.h:31: void
build(const DisplayItemList& displayList, const DisplayListDiff&);
Would it make sense to make DisplayItemTransformTreeBuilder look more like
DisplayListCompositngBuilder?
Such as, set const & to displayList and displayListDiff in constructor, build(),
and hide and processDisplayItem() function?

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayList.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayList.h:29: Vector<unsigned> offsets;
Maybe we should have more check to what we put into offset? Can we have function
that adds and sequence of indices and modifies offsets there while hiding
offset?

[chrishtr, 2015-07-24 19:27:22]

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/ContentLayerDelegate.cpp (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/ContentLayerDelegate.cpp:98:
m_painter->displayList()->displayItemInternal(i).appendToWebDisplayItemList(webDisplayItemList);
On 2015/07/24 at 19:17:15, weiliangc wrote:
> Is it possible that this line changes the order of DisplayItems in the global
DisplayItemList, thus invalidate the indices we saved in the offset of
WebDisplayList on each layer?
> 
> Since we'd have to convert DisplayItem to WebDisplayItem, maybe we could let
Layers own the partial WebDisplayItemList? WDYT?

I think we should end up with representation in which there is exactly one
display list array that everyone on the same thread shares. The copying in this
CL is necessary only before the blink/cc merge.

As for whether there is a bug in this sample implementation...maybe. :)

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemList.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemList.h:69: void
commitNewDisplayItems(DisplayListDiff* = 0);
On 2015/07/24 at 19:17:15, weiliangc wrote:
> What owns the DisplayListDiff? Root Graphics Layer?

The caller of commitNewDisplayItems owns it locally. In this CL the diff is not
part of the API to cc, the API is still:

1. a vector of cc::Layer*'s, on which one stores the usual bits, including
crucially raster invalidation rects. These rects are derived from the
DisplayListDiff as interpreted by the DisplayListCompositingBuilder.

2. property trees (stored on the LTH probably)

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.h:31: void
build(const DisplayItemList& displayList, const DisplayListDiff&);
On 2015/07/24 at 19:17:15, weiliangc wrote:
> Would it make sense to make DisplayItemTransformTreeBuilder look more like
DisplayListCompositngBuilder?
> Such as, set const & to displayList and displayListDiff in constructor,
build(), and hide and processDisplayItem() function?

Common patterns good yes. :)

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
File Source/platform/graphics/paint/DisplayList.h (right):

https://codereview.chromium.org/1238123004/diff/320001/Source/platform/graphi...
Source/platform/graphics/paint/DisplayList.h:29: Vector<unsigned> offsets;
On 2015/07/24 at 19:17:15, weiliangc wrote:
> Maybe we should have more check to what we put into offset? Can we have
function that adds and sequence of indices and modifies offsets there while
hiding offset?

Yes. Getting these right is important.