Isolation of subtrees of stacking contexts and out-of-flow positioned objects

Isolation of subtrees of stacking contexts and out-of-flow positioned objects

BUG=

[Xianzhu, 2016-07-18 03:20:32]

The CQ bit was checked by wangxianzhu@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-18 03:20:41]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-18 04:37:04]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-18 04:37:06]

Dry run: Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Xianzhu, 2016-07-18 17:58:45]

wangxianzhu@chromium.org changed reviewers:
+ pdr@chromium.org, trchen@chromium.org

[Xianzhu, 2016-07-18 17:58:45]

This is not ready for review yet. Some layout tests result 1-pixel shift of some
paintings in spv2 mode.

Frame viewer tracing seems not working in spv2 mode yet. What are your practices
to debug such issues in spv2 mode?

[trchen, 2016-07-19 22:38:42]

I got that you want to re-use nodes that will be created in the first place
whenever possible, but I think it will be a lot of mess. You'll need to isolate
the whole context anyway, for example:

<div id="dynamic">
  <div id="cached" style="opacity:0.5">
    <div style="position:absolute;"></div>
  </div>
</div>


The innermost element will refer to context.absolute.transform, which may or may
not be created by the cached element depending on its
isContainerForAbsolutePosition status.

I think for the proof-of-concept we should just blindly isolate all 10 nodes in
the context. We'll think about how to save a little bit later.

[Xianzhu, 2016-07-19 22:48:14]

On 2016/07/19 22:38:42, trchen wrote:
> I got that you want to re-use nodes that will be created in the first place
> whenever possible, but I think it will be a lot of mess. You'll need to
isolate
> the whole context anyway, for example:
> 
> <div id="dynamic">
>   <div id="cached" style="opacity:0.5">
>     <div style="position:absolute;"></div>
>   </div>
> </div>
> 
> 
> The innermost element will refer to context.absolute.transform, which may or
may
> not be created by the cached element depending on its
> isContainerForAbsolutePosition status.
> 
> I think for the proof-of-concept we should just blindly isolate all 10 nodes
in
> the context. We'll think about how to save a little bit later.

I'm forcing isolation for out-of-order nodes, so the absolute position one just
reference its own no-op nodes. In this way we don't need to create nodes in
other context.

We also don't need to create nodes for fixed-position context, because even if I
don't force isolation for out-of-order nodes, fixed-position objects are
stacking-contexts so they will have their own no-op nodes.

The problem of creating duplicated no-op nodes for absolute-position context is
that we need to add two fields in ObjectPaintProperties to record the extra 2
nodes (absolutePosition.clip and absolutePosition.transform). Forcing isolation
also for out-of-order nodes can avoid this complexity.

[Xianzhu, 2016-07-19 22:49:09]

Description was changed from

==========
Isolation of subtrees of stacking contexts

BUG=
==========

to

==========
Isolation of subtrees of stacking contexts and out-of-flow positioned objects

BUG=
==========

[trchen, 2016-07-19 23:18:09]

Chatted with xianzhu offline. I think his idea will work.
The basic idea is that we don't need to isolate absolute/fixed descendant
because they will isolate them self, so we only need to make sure our
normal-flow
contents are properly isolated.

The trade-off is that we will still be able to cache paint chunk subsequence,
but property tree still needs to be rebuilt (to reattach isolation nodes) for
subtrees that are not invalidated. That sounds like a good trade-off to me.

[chrishtr, 2016-07-19 23:57:41]

On 2016/07/19 at 23:18:09, trchen wrote:
> Chatted with xianzhu offline. I think his idea will work.
> The basic idea is that we don't need to isolate absolute/fixed descendant
> because they will isolate them self, so we only need to make sure our
normal-flow
> contents are properly isolated.

It's kind of the other way around right? isPaintPropertyIsolationBoundary
returns true for out-of-flow positioned elements.

> 
> The trade-off is that we will still be able to cache paint chunk subsequence,
> but property tree still needs to be rebuilt (to reattach isolation nodes) for
> subtrees that are not invalidated.

Only up to the isolation attachment point, right?

> That sounds like a good trade-off to me.

I'm curious how the trade-off could be different under another implementation.
Just to understand what tradeoff you're seeing.

[Xianzhu, 2016-07-20 19:04:39]

On 2016/07/19 23:57:41, chrishtr wrote:
> On 2016/07/19 at 23:18:09, trchen wrote:
> > Chatted with xianzhu offline. I think his idea will work.
> > The basic idea is that we don't need to isolate absolute/fixed descendant
> > because they will isolate them self, so we only need to make sure our
> normal-flow
> > contents are properly isolated.
> 
> It's kind of the other way around right? isPaintPropertyIsolationBoundary
> returns true for out-of-flow positioned elements.
>

The other way is to isolate for stacking context only. In this way, because
absolute-position and fixed-position descendants need different paint property
tree builder contexts, in case the stacking context is not the container of
these descendants, we need to create no-op nodes not only in the 'currrent'
context, but also in the 'absolute' and 'fixed' contexts.
 
> > 
> > The trade-off is that we will still be able to cache paint chunk
subsequence,
> > but property tree still needs to be rebuilt (to reattach isolation nodes)
for
> > subtrees that are not invalidated.
> 
> Only up to the isolation attachment point, right?
> 
> > That sounds like a good trade-off to me.
> 
> I'm curious how the trade-off could be different under another implementation.
> Just to understand what tradeoff you're seeing.

Let's name the method in the current CL A, and the other way B.

The traceoffs are about the following things:
- B (con) needs to create no-op nodes for multiple contexts and record these
nodes in ObjectPaintProperties;
- B (potential pro) could use the method like subsequence-caching to cache paint
property subtrees of stacking contexts which are isolation boundaries (However,
this might not be feasible because PaintLayer::needsRepaint is set in paint
invalidation, but paint invalidation will depend on paint properties);
- A (pro) doesn't need no-op nodes for multiple contexts;
- A (con) may create more no-op nodes than B does.

[Xianzhu, 2016-07-20 19:46:09]

The CQ bit was checked by wangxianzhu@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-20 19:46:47]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-20 21:01:14]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-20 21:01:16]

Dry run: Try jobs failed on following builders:
  mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)

[Xianzhu, 2016-07-21 18:33:45]

The CQ bit was checked by wangxianzhu@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-21 18:34:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-21 20:33:53]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-21 20:33:54]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[pdr., 2016-07-22 00:06:23]

I'm a little worried about the two proposals that add extra nodes because of the
cost for pathological cases where every object isolates. I'm also scared of the
cognitive overhead of isolation vs non-isolation prop node types. Lastly, I'd
like to avoid differences between the cc and blink trees wherever possible.

Instead of paying a cost up-front, could we rely on invalidation and more tree
walking? The prepaint walk kicks off both property tree generation and paint
invalidation, so we could re-use paint invalidation bits or add property tree
invalidation bits. The idea would be to initially force a full subtree walk
anytime the property tree structure changes.

[Xianzhu, 2016-07-22 00:12:23]

On 2016/07/22 00:06:23, pdr. wrote:
> I'm a little worried about the two proposals that add extra nodes because of
the
> cost for pathological cases where every object isolates. I'm also scared of
the
> cognitive overhead of isolation vs non-isolation prop node types. Lastly, I'd
> like to avoid differences between the cc and blink trees wherever possible.
> 
> Instead of paying a cost up-front, could we rely on invalidation and more tree
> walking? The prepaint walk kicks off both property tree generation and paint
> invalidation, so we could re-use paint invalidation bits or add property tree
> invalidation bits. The idea would be to initially force a full subtree walk
> anytime the property tree structure changes.

Will think about this, especially the interrelationship between property tree
structure change and subsequence caching.

A prerequisite question: where will combination of 2d transform layers and layer
squashing occur?

[pdr., 2016-07-22 00:37:30]

On 2016/07/22 at 00:12:23, wangxianzhu wrote:
> On 2016/07/22 00:06:23, pdr. wrote:
> > I'm a little worried about the two proposals that add extra nodes because of
the
> > cost for pathological cases where every object isolates. I'm also scared of
the
> > cognitive overhead of isolation vs non-isolation prop node types. Lastly,
I'd
> > like to avoid differences between the cc and blink trees wherever possible.
> > 
> > Instead of paying a cost up-front, could we rely on invalidation and more
tree
> > walking? The prepaint walk kicks off both property tree generation and paint
> > invalidation, so we could re-use paint invalidation bits or add property
tree
> > invalidation bits. The idea would be to initially force a full subtree walk
> > anytime the property tree structure changes.
> 
> Will think about this, especially the interrelationship between property tree
structure change and subsequence caching.
> 
> A prerequisite question: where will combination of 2d transform layers and
layer squashing occur?

I think that would be PaintArtifactCompositor? I don't have a good mental model
of how incremental updates should work :/ Our initial spv2 designs left a lot of
this unanswered.

[Xianzhu, 2016-07-22 00:49:20]

On 2016/07/22 00:37:30, pdr. wrote:
> On 2016/07/22 at 00:12:23, wangxianzhu wrote:
> > On 2016/07/22 00:06:23, pdr. wrote:
> > > I'm a little worried about the two proposals that add extra nodes because
of
> the
> > > cost for pathological cases where every object isolates. I'm also scared
of
> the
> > > cognitive overhead of isolation vs non-isolation prop node types. Lastly,
> I'd
> > > like to avoid differences between the cc and blink trees wherever
possible.
> > > 
> > > Instead of paying a cost up-front, could we rely on invalidation and more
> tree
> > > walking? The prepaint walk kicks off both property tree generation and
paint
> > > invalidation, so we could re-use paint invalidation bits or add property
> tree
> > > invalidation bits. The idea would be to initially force a full subtree
walk
> > > anytime the property tree structure changes.
> > 
> > Will think about this, especially the interrelationship between property
tree
> structure change and subsequence caching.
> > 
> > A prerequisite question: where will combination of 2d transform layers and
> layer squashing occur?
> 
> I think that would be PaintArtifactCompositor? I don't have a good mental
model
> of how incremental updates should work :/ Our initial spv2 designs left a lot
of
> this unanswered.

Then the cc layer tree will be different from the paint property tree, right? I
think removal of isolation nodes will be covered by combination of 2d transform
nodes and squashing. In this CL the distinction of isolation nodes from normal
nodes in PaintArtifactCompositor is just to keep the existing behavior not
affected by the isolation nodes. The distinction may disappear when we have full
functional PaintArtifactCompositor.

The spv2 paint invalidation doc describes some scenarios of incremental updates
for paint invalidation
(https://docs.google.com/document/d/1M669yu7nsF9Wrkm7nQFi3Pp2r-QmCMqm4K7fPPo-d...),
but it doesn't cover incremental updates for e.g. paint property tree and layer
tree (though some mechanisms for paint invalidation may be useful for them, e.g.
chunk ids), and there might be more corner cases to consider. Comments are
welcome.

Anyway the cost of extra nodes is also my concern. Will think more about this.

BTW, there are weird pixel differences in layout test results. Many of them are
about the anti-aliased pixel between 'w' and 'i'. No idea why this happened.

[Xianzhu, 2016-07-25 21:26:38]

For now this Cl might be unnecessary because we'll invalidate the subtree when
transform, opacity, etc. changes. We also reuse changed property nodes for an
object.

https://codereview.chromium.org/2176573004/ which enables subsequence-caching
for spv2 passed for all current spv2 layout tests.

Closing this now. May reconsider this if we encounter real problems.

[pdr., 2016-07-25 21:36:22]

I talked with Tien-Ren and now better understand the isolation node proposals.
Because we effectively already create isolation nodes for paint layers, we won't
really create so many extra nodes so I no longer feel it's too scary. I might
suggest just calling them something that describes what they do instead of
introducing a new term  though--reparenteningNodeForSubsequenceCaching or
something like that.

[pdr., 2016-07-25 21:38:02]

On 2016/07/25 at 21:36:22, pdr. wrote:

Ack! We were both adding comments at the same time. I was pretty convinced we
need to do something for these cases, but I need to look at how the new patch
works.

[pdr., 2016-07-25 23:26:04]

On 2016/07/25 at 21:26:38, wangxianzhu wrote:
> For now this Cl might be unnecessary because we'll invalidate the subtree when
transform, opacity, etc. changes. We also reuse changed property nodes for an
object.
> 

Chris, Tien-Ren, and I talked about this for some time and we don't think it is
possible to rely on existing invalidation caused by transform, opacity, etc
changes. We thought of two examples:
1) When a clip node is added at the root of the document, we use
repaint-after-layout technology to prune the paint walk today. With your
proposal, we would need to keep doing the paint walk.
2) When there is a composited 3d transform on node A, and a new composited 3d
transform is added to an ancestor, we do not need to do the paint walk on node A
again. With your proposal, we would need to do the paint walk for A.

Do you have an idea on how to solve these issues without affecting performance
too much?

My comment on https://codereview.chromium.org/2176573004 asking for tests was
getting at these issues, but maybe we can land
https://codereview.chromium.org/2176573004/ anyway because all proposals will
have that code?

[Xianzhu, 2016-07-26 00:11:10]

On 2016/07/25 23:26:04, pdr. wrote:
> On 2016/07/25 at 21:26:38, wangxianzhu wrote:
> > For now this Cl might be unnecessary because we'll invalidate the subtree
when
> transform, opacity, etc. changes. We also reuse changed property nodes for an
> object.
> > 
> 
> Chris, Tien-Ren, and I talked about this for some time and we don't think it
is
> possible to rely on existing invalidation caused by transform, opacity, etc
> changes.

Agreed. Will add more details in reply of
https://codereview.chromium.org/2176573004.

> We thought of two examples:
> 1) When a clip node is added at the root of the document, we use
> repaint-after-layout technology to prune the paint walk today. With your
> proposal, we would need to keep doing the paint walk.
> 2) When there is a composited 3d transform on node A, and a new composited 3d
> transform is added to an ancestor, we do not need to do the paint walk on node
A
> again. With your proposal, we would need to do the paint walk for A.
> 
> Do you have an idea on how to solve these issues without affecting performance
> too much?
>

What do you refer to as "my proposal"?

Paint tree walk pruning seems a much broader issue than the subtree isolation
issue. Currently when a node is inserted/deleted, the nodes needing update the
parent pointers may be very deep in the dom tree, and we don't know where to
stop until we finish traversing the whole dom tree. It seems that we need
top-down pointers in the paint property tree, or use other means (e.g.
LayoutBlock::positionedObjects or PaintLayer structure) to find which child
nodes need to update the parent pointers.   

> My comment on https://codereview.chromium.org/2176573004 asking for tests was
> getting at these issues, but maybe we can land
> https://codereview.chromium.org/2176573004/ anyway because all proposals will
> have that code?

I was replying in the CL when I saw this message. They are really related. Will
add more there.

Subtree isolation may be not only for subsequence caching. Perhaps is "subtree
synchronization point" a better name? At a subtree synchronization point, we
synchronize all the paint property subtrees.

[chrishtr, 2016-07-26 00:41:49]

My current feeling is that we should re-paint everything that may be affected by
paint property tree nodes which change. Adding up to 7 new isolation property
tree nodes is a lot of overhead and complexity. Also, only handling normal-flow
descendants 

Thus in some cases,
adding a single property tree node could cause re-paint of the entire page.

However, this does not preclude various optimizations, such as:

- New paint property tree nodes don't affect paint chunks that are not on a
descendant chain in any tree (e.g. siblings). Therefore they don't need to
be painted.
- In some cases, we may be able to efficiently detect whether paint chunks that
are descendants actually reference new paint property tree nodes.
If they don't, then they don't need to be re-painted. (trchen had an idea to
detect this situation by reference counting pointers to property tree nodes)

Two other things that came to mind:

- we have similar complications to the SPv1 subsequence caching system. e.g when
an overflow-related property changes, needsRepaint is set on overflow change. We
also I believe set needsRepaint conservatively in similar cases?
- We should consider which use cases benefit the most from SPv1 subsequence
caching, and target those use cases with minimal code complexity.
My intuition (which needs to be backed by data...) is that the most important
use case is to avoid traversing the tree when local invalidation s occur
elsewhere.

On 2016/07/26 at 00:11:10, wangxianzhu wrote:
> On 2016/07/25 23:26:04, pdr. wrote:
> > On 2016/07/25 at 21:26:38, wangxianzhu wrote:
> > > For now this Cl might be unnecessary because we'll invalidate the subtree
when
> > transform, opacity, etc. changes. We also reuse changed property nodes for
an
> > object.
> > > 
> > 
> > Chris, Tien-Ren, and I talked about this for some time and we don't think it
is
> > possible to rely on existing invalidation caused by transform, opacity, etc
> > changes.
> 
> Agreed. Will add more details in reply of
https://codereview.chromium.org/2176573004.
> 
> > We thought of two examples:
> > 1) When a clip node is added at the root of the document, we use
> > repaint-after-layout technology to prune the paint walk today. With your
> > proposal, we would need to keep doing the paint walk.
> > 2) When there is a composited 3d transform on node A, and a new composited
3d
> > transform is added to an ancestor, we do not need to do the paint walk on
node A
> > again. With your proposal, we would need to do the paint walk for A.
> > 
> > Do you have an idea on how to solve these issues without affecting
performance
> > too much?
> >
> 
> What do you refer to as "my proposal"?
> 
> Paint tree walk pruning seems a much broader issue than the subtree isolation
issue. Currently when a node is inserted/deleted, the nodes needing update the
parent pointers may be very deep in the dom tree, and we don't know where to
stop until we finish traversing the whole dom tree. It seems that we need
top-down pointers in the paint property tree, or use other means (e.g.
LayoutBlock::positionedObjects or PaintLayer structure) to find which child
nodes need to update the parent pointers.   
> 
> > My comment on https://codereview.chromium.org/2176573004 asking for tests
was
> > getting at these issues, but maybe we can land
> > https://codereview.chromium.org/2176573004/ anyway because all proposals
will
> > have that code?
> 
> I was replying in the CL when I saw this message. They are really related.
Will add more there.
> 
> Subtree isolation may be not only for subsequence caching. Perhaps is "subtree
synchronization point" a better name? At a subtree synchronization point, we
synchronize all the paint property subtrees.

Did you have another use case in mind? That would certainly affect things.

[Xianzhu, 2016-07-26 16:52:10]

On 2016/07/26 00:41:49, chrishtr wrote:
> My current feeling is that we should re-paint everything that may be affected
by
> paint property tree nodes which change. Adding up to 7 new isolation property
> tree nodes is a lot of overhead and complexity. Also, only handling
normal-flow
> descendants 
> 

With the choice of this CL, we add up to 3 new isolation property tree nodes
(may be 4 if we add scrolling nodes) for a stacking context or an out-of-flow
positioned object. If we chose not to create isolation nodes for
non-stacking-context out-of-flow positioned objects, there would be up to 5 new
nodes and 2 new references from ObjectPaintProperties for each stacking context.
The overhead still looks scary. I feel this would create 1x to 2x number of more
nodes.

> Thus in some cases,
> adding a single property tree node could cause re-paint of the entire page.
> 
> However, this does not preclude various optimizations, such as:
> 
> - New paint property tree nodes don't affect paint chunks that are not on a
> descendant chain in any tree (e.g. siblings). Therefore they don't need to
> be painted.
> - In some cases, we may be able to efficiently detect whether paint chunks
that
> are descendants actually reference new paint property tree nodes.
> If they don't, then they don't need to be re-painted. (trchen had an idea to
> detect this situation by reference counting pointers to property tree nodes)
>

I think we should separate the need of pre-paint tree walk and the need of
repaint. We need to walk into the subtree when a property node is created during
pre-paint tree walk to update the tree structure (the parent node), but don't
necessarily repaint the subtree (more discussions below).

> Two other things that came to mind:
> 
> - we have similar complications to the SPv1 subsequence caching system. e.g
when
> an overflow-related property changes, needsRepaint is set on overflow change.
We
> also I believe set needsRepaint conservatively in similar cases?

In spv1, every change of clipping (except for a composited contents layer) will
cause change of paint results. In spv2, we should introduce interest rects for
scrolling overflow clippings, so repaint is needed only if the interest rect
changes, which requires basically the same algorithm we used in
GraphicsLayer::paintWithoutCommit(), which is separate from paint invalidation
algorithm.

Thus perhaps we don't need to invalidate any object or any layer during paint
invalidation for property changes. For layers, we can check interest rect change
in shouldRepaintSubsequence(). Rasterization invalidation caused by property
changes will happen after paint.

Without isolation, if we don't repaint the subtree with changed paint property,
references to out-dated property nodes from PaintChunkProperties of cached
chunks is still a problem. Will think more about this. Repaint merely for
updating the references is not good.

> - We should consider which use cases benefit the most from SPv1 subsequence
> caching, and target those use cases with minimal code complexity.
> My intuition (which needs to be backed by data...) is that the most important
> use case is to avoid traversing the tree when local invalidation s occur
> elsewhere.
> 
> > Subtree isolation may be not only for subsequence caching. Perhaps is
"subtree
> synchronization point" a better name? At a subtree synchronization point, we
> synchronize all the paint property subtrees.
> 
> Did you have another use case in mind? That would certainly affect things.

No. Thought of isolation nodes might help pruning pre-paint tree walk, but it
seemed not to.