Open Bug 971349 Opened 10 years ago Updated 2 years ago

make 3d-transform overflow calculation duplicate work less

Categories

(Core :: Layout, defect, P4)

Product:
Core
Component:
Layout
Type:
defect

Tracking

()

People

(Reporter: dbaron, Unassigned)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

Attachments

(1 obsolete file) 

I think the overflow area calculation that we do in the presence of 3-D transforms is doing more work than it needs to.  In particular, in nsFrame::FinishAndStoreOverflow, to handle some cases involving both transform-style:preserve-3d and perspective, does recursion over some of the descendants of the frame, redoing work that was previously done.

Bug 971296 comment 3 has profile data suggesting this is worth working on.

I don't fully understand the code in question, but both the code itself and the amount of time we spend in it make me suspect we could do better.

A few thoughts on how include:

 (1) We could consider participants in a 3-D rendering context as only contributing to the overflow area of the element that flattens that 3-D rendering context, and not to any of the intermediates.  I think this makes the most sense from a standards perspective in terms of the definition of overflow; it probably requires us to have some special invalidation handling, though, to handle invalidation requests on 3-D preserving frames in the interior of the 3-D scene (i.e., not the root that flattens it, but also not leaves).

 (2) We could use the OverflowChangedTracker to coalesce the work we have to do (which I would think is easier for the UpdateOverflow codepath than the Reflow codepath).

(I think these are alternatives and don't make sense together, though I'm not sure of that, either.)
Matt, curious if you have any thoughts here, either on why the code is doing what it currently is, and on whether and how you think we could do better.
Flags: needinfo?(matt.woodrow)
Oh, and the code I'm talking about here is the calls to ComputePreserve3DChildrenOverflow and RecomputePerspectiveChildrenOverflow from nsIFrame::FinishAndStoreOverflow (which are the only calls to those functions, I believe), and the recursive calls in both RecomputePreserve3DChildrenOverflow (called from the first) and nsIFrame::RecomputePerspectiveChildrenOverflow (which is the second).
Comment on attachment 8374522 [details]
jprof profile of the painting slice, with GL Layers on Linux (.html.gz)

sorry, wrong bug
Attachment #8374522 - Attachment is obsolete: true
(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #0)
> I think the overflow area calculation that we do in the presence of 3-D
> transforms is doing more work than it needs to.  In particular, in
> nsFrame::FinishAndStoreOverflow, to handle some cases involving both
> transform-style:preserve-3d and perspective, does recursion over some of the
> descendants of the frame, redoing work that was previously done.
> 
> Bug 971296 comment 3 has profile data suggesting this is worth working on.
> 
> I don't fully understand the code in question, but both the code itself and
> the amount of time we spend in it make me suspect we could do better.
> 
> A few thoughts on how include:
> 
>  (1) We could consider participants in a 3-D rendering context as only
> contributing to the overflow area of the element that flattens that 3-D
> rendering context, and not to any of the intermediates.  I think this makes
> the most sense from a standards perspective in terms of the definition of
> overflow; it probably requires us to have some special invalidation
> handling, though, to handle invalidation requests on 3-D preserving frames
> in the interior of the 3-D scene (i.e., not the root that flattens it, but
> also not leaves).

We kind of do this already. The intermediate stages of a preserve-3d chain aren't necessarily representable as a 2d rect (think of two nested 90degree x-axis rotations), so we transform the overflow area up to the root of the chain. But we store these on the intermediate frames too, so that visibility calculation doesn't think the intermediate frames have a 0 sized area.

 
>  (2) We could use the OverflowChangedTracker to coalesce the work we have to
> do (which I would think is easier for the UpdateOverflow codepath than the
> Reflow codepath).

Isn't this what it's doing already? That was what it was added for in bug 815666.


(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #1)
> Matt, curious if you have any thoughts here, either on why the code is doing
> what it currently is, and on whether and how you think we could do better.

Bug 815666 tries to summarize some of the problem. Basically, the transform (and thus the overflow) of leaf frames is dependant on the transform/perspecrtive of their ancestors, and that value is dependent on the size of the parent.

I don't doubt we can improve things, but it's a fairly complex problem.
Flags: needinfo?(matt.woodrow)
(In reply to Matt Woodrow (:mattwoodrow) from comment #5)
> We kind of do this already. The intermediate stages of a preserve-3d chain
> aren't necessarily representable as a 2d rect (think of two nested 90degree
> x-axis rotations), so we transform the overflow area up to the root of the
> chain. But we store these on the intermediate frames too, so that visibility
> calculation doesn't think the intermediate frames have a 0 sized area.

Right, but needing to store it on the intermediate frames means there are more frames that need to be updated if the ancestor's transform changes, since if the data on the intermediate frames is useful for things like invalidation then it has to be a function of the transform on the ancestor.  (But what overflow area do you store in the case of two nested 90deg x-axis rotations?)

> >  (2) We could use the OverflowChangedTracker to coalesce the work we have to
> > do (which I would think is easier for the UpdateOverflow codepath than the
> > Reflow codepath).
> 
> Isn't this what it's doing already? That was what it was added for in bug
> 815666.

No.  The OverflowChangedTracker ensures that we call UpdateOverflow (or call FinishAndStoreOverflow directly instead of via UpdateOverflow) on descendants before calling it on ancestors.  The problem here, I think, is that when we call FinishAndStoreOverflow on the ancestor, it goes and *recomputes* stuff for descendants again, and calls FinishAndStoreOverflow on those descendants again -- entirely independently of the OverflowChangedTracker.
(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #6)
 
> Right, but needing to store it on the intermediate frames means there are
> more frames that need to be updated if the ancestor's transform changes,
> since if the data on the intermediate frames is useful for things like
> invalidation then it has to be a function of the transform on the ancestor. 
> (But what overflow area do you store in the case of two nested 90deg x-axis
> rotations?)

The inner frame get its pre-transform overflow and transforms it by a 180deg x-axis rotation. This is a bit weird, since we're in the parent frame's coordinate space, but we don't have much choice. For computing the outer frames overflow, we can't just union the children and then transform, since that would transform them too many times. We instead have to walk the children, and transform them individually (if they aren't part of the preserve-3d chain) or just include their area directly (if they are already transformed into our coordinate space).

We could try not doing this, and only include their bounds in the root preserve-3d frame's overflow, but we'd need to find everything that depends on this intermediate overflow and fix it. I don't *think* it should matter for invalidation, since the intermediate frames don't build display items for the transform, and no transformed content will still have its overflow included. It is an issue for BuildDisplayListForChild which will bail out of descending further into the frame tree if the overflow area doesn't intersect the dirty region, so it would need to know that their are preserve-3d descendants further down. I'm not sure what other cases there are.


> 
> > >  (2) We could use the OverflowChangedTracker to coalesce the work we have to
> > > do (which I would think is easier for the UpdateOverflow codepath than the
> > > Reflow codepath).
> > 
> > Isn't this what it's doing already? That was what it was added for in bug
> > 815666.
> 
> No.  The OverflowChangedTracker ensures that we call UpdateOverflow (or call
> FinishAndStoreOverflow directly instead of via UpdateOverflow) on
> descendants before calling it on ancestors.  The problem here, I think, is
> that when we call FinishAndStoreOverflow on the ancestor, it goes and
> *recomputes* stuff for descendants again, and calls FinishAndStoreOverflow
> on those descendants again -- entirely independently of the
> OverflowChangedTracker.

Ah, yes, that is true. This is because the computation of overflow for preserve-3d frames is stupidly complicated (as explained above) and a lot of code doesn't compute it correctly.

Rather than trying to find all the places that compute overflow and fix them for this, we decided it would be easier to do a second pass over the frame and fix them up. It may be time to revisit that decision, or simplify the overflow computation so that it isn't an issue.

One possible idea was to store overflow as a 3d cube, rather than a 2d rectangle. That makes most of these problems go away, but it's pretty painful in its own right.
(In reply to Matt Woodrow (:mattwoodrow) from comment #7)
> (In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #6)
> > Right, but needing to store it on the intermediate frames means there are
> > more frames that need to be updated if the ancestor's transform changes,
> > since if the data on the intermediate frames is useful for things like
> > invalidation then it has to be a function of the transform on the ancestor. 
> > (But what overflow area do you store in the case of two nested 90deg x-axis
> > rotations?)
> 
> The inner frame get its pre-transform overflow and transforms it by a 180deg
> x-axis rotation. This is a bit weird, since we're in the parent frame's
> coordinate space, but we don't have much choice.

So it's not really meaningful on that intermediate frame anyway, then.

> For computing the outer
> frames overflow, we can't just union the children and then transform, since
> that would transform them too many times. We instead have to walk the
> children, and transform them individually (if they aren't part of the
> preserve-3d chain) or just include their area directly (if they are already
> transformed into our coordinate space).

Yeah, I understood that much already.  (The bit I don't understand has to do with why the Preserves3DChildren, Preserves3D, HasPerspective, and ChildrenHavePerspective functions have the conditions they do, and what exactly those conditions mean in a larger sense, or why we call part of ComputePreserve3DChildrenOverflow when Preserves3D is true.)

> We could try not doing this, and only include their bounds in the root
> preserve-3d frame's overflow, but we'd need to find everything that depends
> on this intermediate overflow and fix it. I don't *think* it should matter
> for invalidation, since the intermediate frames don't build display items
> for the transform, and no transformed content will still have its overflow
> included. It is an issue for BuildDisplayListForChild which will bail out of
> descending further into the frame tree if the overflow area doesn't
> intersect the dirty region, so it would need to know that their are
> preserve-3d descendants further down. I'm not sure what other cases there
> are.

It seems like it might be worthwhile -- especially if we might end up exposing the concept of overflow areas to Web authors in ways detectable via APIs -- and also if it could improve performance in the updating case.

> One possible idea was to store overflow as a 3d cube, rather than a 2d
> rectangle. That makes most of these problems go away, but it's pretty
> painful in its own right.

Yeah, that is another possibility, though I'm not sure what I think about it.
(In reply to Matt Woodrow (:mattwoodrow) from comment #7)
> The inner frame get its pre-transform overflow and transforms it by a 180deg
> x-axis rotation. This is a bit weird, since we're in the parent frame's
> coordinate space, but we don't have much choice.

And if I'm understanding correctly, the thing that just puts it in the parent frame's coordinate space is the code in nsDisplayTransform::GetResultingTransformMatrixInternal that just goes ahead and makes a recursive call if Preserves3D(), right?
(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #8)
> (In reply to Matt Woodrow (:mattwoodrow) from comment #7)
> > 
> > The inner frame get its pre-transform overflow and transforms it by a 180deg
> > x-axis rotation. This is a bit weird, since we're in the parent frame's
> > coordinate space, but we don't have much choice.
> 
> So it's not really meaningful on that intermediate frame anyway, then.

Not really, but we need something for visibility analysis.


> 
> > For computing the outer
> > frames overflow, we can't just union the children and then transform, since
> > that would transform them too many times. We instead have to walk the
> > children, and transform them individually (if they aren't part of the
> > preserve-3d chain) or just include their area directly (if they are already
> > transformed into our coordinate space).
> 
> Yeah, I understood that much already.  (The bit I don't understand has to do
> with why the Preserves3DChildren, Preserves3D, HasPerspective, and
> ChildrenHavePerspective functions have the conditions they do, and what
> exactly those conditions mean in a larger sense, or why we call part of
> ComputePreserve3DChildrenOverflow when Preserves3D is true.)

ChildrenHavePerspective() means that the frame has the 'perspective' property, and is attempting to apply perspective to child elements. HasPerspective() checks if we both have a parent providing a perspective value, and a transform to apply it to.

Preserves3D() means that the frame will include the transform of its parent in its transform. So it checks if the frame has a transform, and if the parent supports preserve-3d. Preserves3DChildren() means the frame will pass its transform down to any transformed children. As well as needing the 'transform-style:preserve-3d' property, there's a also a few reasons (mentioned in the spec) that stop preserve-3d from being applied. This is clipping, svg effects etc.


Calling ComputePreserve3DChildrenOverflow checks Preserve3DChildren(). Maybe it could check !parent->Preserves3DChildren() too? I think we only need to call it (as the code currently works) when we get to the very root of the preserve-3d hierarchy.

(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #9)
> (In reply to Matt Woodrow (:mattwoodrow) from comment #7)
> > The inner frame get its pre-transform overflow and transforms it by a 180deg
> > x-axis rotation. This is a bit weird, since we're in the parent frame's
> > coordinate space, but we don't have much choice.
> 
> And if I'm understanding correctly, the thing that just puts it in the
> parent frame's coordinate space is the code in
> nsDisplayTransform::GetResultingTransformMatrixInternal that just goes ahead
> and makes a recursive call if Preserves3D(), right?

Yes.
(In reply to Matt Woodrow (:mattwoodrow) from comment #10)
> ChildrenHavePerspective() means that the frame has the 'perspective'
> property, and is attempting to apply perspective to child elements.

Yeah, that's the easy one. :-)

> HasPerspective() checks if we both have a parent providing a perspective
> value, and a transform to apply it to.

I guess this makes sense except that IsTransformed checks for a pile of things other than "has a transform" -- part of it eventually boils down to nsStyleDisplay::HasTransformStyle, which also checks preserve-3d (maybe that's needed here?) and backface-visibility (which seems very suspicious to me).


> Preserves3D() means that the frame will include the transform of its parent
> in its transform. So it checks if the frame has a transform, and if the
> parent supports preserve-3d.

So this shares the quirks with HasTransform above (different from, but called by, IsTransformed mentioned above), and the quirks of Preserve3DChildren below.  The HasTransform check here does, I presume, need to check both transform and transform-style.

I guess I'm not crazy about the function name of this one; it's not clear to me why Preserves3D() is a good name for the above.

> Preserves3DChildren() means the frame will pass
> its transform down to any transformed children. As well as needing the
> 'transform-style:preserve-3d' property, there's a also a few reasons
> (mentioned in the spec) that stop preserve-3d from being applied. This is
> clipping, svg effects etc.

Yeah.  I have a refactoring patch that makes this make more sense to me that I'll post to bug 972088.

> Calling ComputePreserve3DChildrenOverflow checks Preserve3DChildren(). Maybe
> it could check !parent->Preserves3DChildren() too? I think we only need to
> call it (as the code currently works) when we get to the very root of the
> preserve-3d hierarchy.

We can't *quite* do that since we might end up in a codepath (either because we're doing UpdateOverflow, and it returns that it's propagated to an ancestor that's unchanged, or maybe maybe maybe because of reflow roots) that's calling FinishAndStoreOverflow on the descendants of the root of the preserve-3d hierarchy, but doesn't reach the root of the preserve-3d hierarchy at all.

And now that I'm answering that, I think I finally understand what the code in ComputePreserve3DChildrenOverflow is doing:  it's accounting for the 3d-preserving children already having been transformed into the coordinate system of the root of the preserve-3d hierarchy.  Though it seems odd that it's unioning with rather than replacing the existing contribution of the same child (though I don't see a way around that weaker than item (1) in comment 0), and odd that it's bothering to re-include the contributions of non-preserve-3d children, which should already have been included (before accounting for transform) and then transformed all at once in the normal (non-preserve-3d) transform handling.


Also, I guess another advantage of converting to the coordinate space of the root of the preserve-3d hierarchy is that the UpdateOverflow logic that checks whether the overflow area changed will still work correctly.
(In reply to David Baron [:dbaron] (needinfo? me) (UTC-8) from comment #11)
> 
> I guess this makes sense except that IsTransformed checks for a pile of
> things other than "has a transform" -- part of it eventually boils down to
> nsStyleDisplay::HasTransformStyle, which also checks preserve-3d (maybe
> that's needed here?) and backface-visibility (which seems very suspicious to
> me).

Ok, I think that's a valid point. We probably don't need to check for backface-visiblity here. I think we do need to check for preserve-3d though for the following case:

<div style="perspective:1000px;">
  <div style="transform-style:preserve-3d">
    <div style="transform:rotateX(45deg)">
      // Content
    </div>
  </div>
</div>

The second div isn't transformed, but we do need to treat it as having perspective since it will pass it onto the third div.


> > Preserves3D() means that the frame will include the transform of its parent
> > in its transform. So it checks if the frame has a transform, and if the
> > parent supports preserve-3d.
> 
> So this shares the quirks with HasTransform above (different from, but
> called by, IsTransformed mentioned above), and the quirks of
> Preserve3DChildren below.  The HasTransform check here does, I presume, need
> to check both transform and transform-style.
> 
> I guess I'm not crazy about the function name of this one; it's not clear to
> me why Preserves3D() is a good name for the above.

Checking backface-visibility here was intentional, and fixed a bug. But it means that we treat backface-visibility as a stacking context, which violates the spec.

The bug is fixing the following example:

<div id="parent" style="transform-style:preserve3d; transform:rotateX(10deg)">
  <div id="a"></div>
  <div id="b" style="backface-visibility:hidden"></div>
  <div id="c" style="transform:rotateX(45deg)"></div>
  <div id="d"></div>
</div>

Converted to a display list looks like:

nsDisplayTransform(parent)
  Content(a)
  Content(b)
nsDisplayTransform(parent+c)
  Content(c)
nsDisplayTransform(parent)
  Content(d)

The content for a and b end up in the same layer, and we have no way of respecting the backface-visibility request.

Pretending that backface-visibility has an implicit transform, and promoting it to a stacking context fixes this. We get a specific nsDisplayTransform(parent+b) wrapped around only b's content, and we can set the bit that tells layers not to draw it if the backface is hidden.

We could fix this by adding nsDisplayBackfaceVisibilty for backface hidden, but not transformed elements. It's a bit confusing without a stacking context since we need to find all content created by that element (but not descendants) and wrap them in one of these so that they all get layerized separately. I guess this is similar to layerising of position:fixed, which has been buggy.


Open to suggestions for better names!


> 
> We can't *quite* do that since we might end up in a codepath (either because
> we're doing UpdateOverflow, and it returns that it's propagated to an
> ancestor that's unchanged, or maybe maybe maybe because of reflow roots)
> that's calling FinishAndStoreOverflow on the descendants of the root of the
> preserve-3d hierarchy, but doesn't reach the root of the preserve-3d
> hierarchy at all.

Ah, right. I may have tried this actually and went with the current code for that reason.

> 
> And now that I'm answering that, I think I finally understand what the code
> in ComputePreserve3DChildrenOverflow is doing:  it's accounting for the
> 3d-preserving children already having been transformed into the coordinate
> system of the root of the preserve-3d hierarchy.  Though it seems odd that
> it's unioning with rather than replacing the existing contribution of the
> same child (though I don't see a way around that weaker than item (1) in
> comment 0), and odd that it's bothering to re-include the contributions of
> non-preserve-3d children, which should already have been included (before
> accounting for transform) and then transformed all at once in the normal
> (non-preserve-3d) transform handling.
> 
> 
> Also, I guess another advantage of converting to the coordinate space of the
> root of the preserve-3d hierarchy is that the UpdateOverflow logic that
> checks whether the overflow area changed will still work correctly.

We'd need to find all places that union child frames to compute overflow and make sure they skip all preserve-3d children if we're not the root, and all non-leaf preserve-3d children if we are.
Priority: -- → P4
Severity: normal → S3
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: