Closed Bug 845874 Opened 7 years ago Closed 6 years ago

Switch to Y-X banded regions

Categories

(Core :: Graphics, defect)

x86
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla29
Tracking Status
firefox28 --- wontfix

People

(Reporter: jrmuizel, Assigned: jrmuizel)

References

Details

(Whiteboard: [not-fixed-in-holly][qa-])

Attachments

(2 files, 4 obsolete files)

Currently our regions code is just a simple y,x sorted list of non-intersecting rectangles. This can cause us to have simple regions represented in a complex unoptimizable way.

Most other region code seems to use a Y-X banded implementation.
http://cgit.freedesktop.org/pixman/tree/pixman/pixman-region.c#n122
Much of this code originated from X11's region code which is now in pixman (Qt, Wine). WebKit uses the ideas from "Scanline Coherent Shape Algebra" which I believe is a similar idea. Skia also seems to use a similar idea, but I haven't spent enough time looking at their implementation to figure it out yet.
Pixman uses x1,y1,x2,y2 storage for rectangles which makes implementing nsRegion on top of it a little trickier. WebKit's uses x,y,w,h
Blocks: 898416
Depends on: 911868
Duplicate of this bug: 911590
The perf results from bug 898416

Before:
I gave up running the test after only getting half way though testVisibilty and having 13 minutes pass.

After:
Total Time: 2 min
testDisplay:2374
testVisibilty:398
testFourClassReflow:1774
testFourScriptReflows:1809
testFontSizeEm:1816
Attachment #789723 - Attachment is obsolete: true
Attached patch Actually replace nsRegion (obsolete) — Splinter Review
This passes all the tests.
Attachment #799058 - Attachment is obsolete: true
Attachment #799557 - Flags: review?(roc)
Comment on attachment 799557 [details] [diff] [review]
Actually replace nsRegion

Review of attachment 799557 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/src/CanonicalRegion.h
@@ +3,5 @@
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +
> +#ifndef nsIntRegion_h__
> +#define nsIntRegion_h__

Why do we have this CanonicalRegion.h file? Shouldn't it just be removed from the patch?
Comment on attachment 799557 [details] [diff] [review]
Actually replace nsRegion

Review of attachment 799557 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/src/CanonicalRegion.h
@@ +3,5 @@
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +
> +#ifndef nsIntRegion_h__
> +#define nsIntRegion_h__

Yes. Sorry this was unintentionally left in the patch.
Comment on attachment 799557 [details] [diff] [review]
Actually replace nsRegion

Review of attachment 799557 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/src/nsRegion.cpp
@@ +301,5 @@
>      firstDeviceRect =
> +      first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
> +    pixman_box32_t box = { firstDeviceRect.x, firstDeviceRect.y,
> +	                 firstDeviceRect.x + firstDeviceRect.width,
> +			 firstDeviceRect.y + firstDeviceRect.height };

Can we create RectToBox and BoxToRect helpers?

::: gfx/src/nsRegion.h
@@ +60,5 @@
>  
> +  static
> +  nsresult InitStatic()
> +  {
> +	  return NS_OK;

Fix indent.

Or better still, remove this function entirely!

@@ +153,5 @@
>    }
>  
> +  bool Contains (const nsRect& aRect) const
> +  {
> +    pixman_box32_t box = { aRect.x, aRect.y, aRect.x+aRect.width, aRect.y+aRect.height };

aRect.XMost()/YMost(), or RectToBox helper

@@ +174,5 @@
> +  bool IsComplex () const { return GetNumRects() > 1; }
> +  bool IsEqual (const nsRegion& aRegion) const
> +  {
> +    return pixman_region32_equal(const_cast<pixman_region32_t*>(&mImpl),
> +				 const_cast<pixman_region32_t*>(&aRegion.mImpl));

Instead of repeating all these casts, let's have a private access method in nsRegion, say pixman_region_32_t* Impl() containing the cast.
Attached patch Address the review comments (obsolete) — Splinter Review
Attachment #799557 - Attachment is obsolete: true
Attachment #799557 - Flags: review?(roc)
Attachment #800874 - Flags: review?(roc)
Comment on attachment 800874 [details] [diff] [review]
Address the review comments

Review of attachment 800874 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/src/nsRegion.h
@@ +235,4 @@
>  
> +  static inline pixman_box32_t RectToBox(const nsRect &aRect)
> +  {
> +    pixman_box32_t box = { aRect.x, aRect.y, aRect.x+aRect.width, aRect.y+aRect.height };

XMost, YMost

@@ +240,5 @@
> +  }
> +
> +  static inline pixman_box32_t RectToBox(const nsIntRect &aRect)
> +  {
> +    pixman_box32_t box = { aRect.x, aRect.y, aRect.x+aRect.width, aRect.y+aRect.height };

Here too
Attachment #800874 - Flags: review?(roc) → review+
What's blocking this from being checked in?
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #11)
> What's blocking this from being checked in?

There's a talos regression caused by a behaviour change that I'm still trying to track down. We're painting more during tsvgr_opacity and I'm not sure why yet.
Comment on attachment 800874 [details] [diff] [review]
Address the review comments

Review of attachment 800874 [details] [diff] [review]:
-----------------------------------------------------------------

::: gfx/src/nsRegion.cpp
@@ +24,2 @@
>  {
> +  // XXX this could be made faster

Please file a bug for this and reference the bug # in the comment here. There are 570 XXX comments in gfx/ and nobody ever acts on them. We should track them bug with a proper meta bug. Many of these are good first bugs.
nsRegion::ScaleToInsidePixels would adjust firstDeviceRect but this change was never added to the newly constructed region. This caused seams to develop in the region which cause component alpha to be used causing a talos regression.
So it looks like there's still a real Tresize regression on windows 8
Attachment #800874 - Attachment is obsolete: true
Calling PushLayer more often seems to be the cause of the regression.
So I figured out why yesterday.

With the old region code we end up with this region:
http://people.mozilla.org/~jmuizelaar/region-pre.html
which is represented like this:
http://people.mozilla.org/~jmuizelaar/region-post.html
with the new code.

We call SimplifyOutward(4) on this. With old regions we can't simplify it so we end up taking the bounds and get 1 rect. With the new regions we have only 3 rects to start and so we do nothing. The difference between 3 rects and 1 rect cause D2D to do a PushLayer() instead of a ClipRect() and that seems to be the cause for the regression.

There doesn't really seem any good way to fix this other than to improve D2D's clipping behaviour. So I think it makes sense to land and take the regression.
There will be cases where not having to simplify out will improve performance, so I would call this a wash here.
Jeff and I chatted about a few potential alternatives:

- having a version of Simplify which calculates % coverage of the region inside its bounding rect.  If it's > N (for some passed-in N, maybe 75%?), then just use the bounding rect.

- On D2D especially, just always simplify to the bounding rect in this case.  If we PushLayer, we're re-rendering everything anyway, so clipping with that is never going to be a win, no matter what the coverage is like.
Is it true then that bug 934860 would fix this regression?

I just landed a patch to disable that for now, but I think we should assume that it is going to be enabled again soon.

Given Vlad's point that we have to render the bounds of the invalid area anyway, simplifying the bounding box shouldn't regress performance. However if we can determine that very few (or maybe no?) display items itersect multiple rects in the region, we can paint the rects separately and probably cull some display items from being painted entirely.

I'll try come up with something along those lines for bug 938395.
(In reply to Matt Woodrow (:mattwoodrow) from comment #22)
> Is it true then that bug 934860 would fix this regression?

It could certainly help.

> I just landed a patch to disable that for now, but I think we should assume
> that it is going to be enabled again soon.
> 
> Given Vlad's point that we have to render the bounds of the invalid area
> anyway, simplifying the bounding box shouldn't regress performance.

We don't actually render display items that don't intersect with the invalid region, even if they are in the bounding box correct? That means that expanding to the bounding box will regress performance.
Depends on: 940373
https://hg.mozilla.org/mozilla-central/rev/d0255c4b2adc
Assignee: nobody → jmuizelaar
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
Unfortunately it causes system-cairo build breakage - see Bug 941595
Depends on: 941595
Depends on: 942250
jrmuizel's given me the go-ahead to back this out of Holly, meaning this patch is (at this point) not going to ship on the 28 train.
I should specify that we're backing it out of Holly due to bug 942250.
Uh, so this is appears to not be a simple back-out. I think I'm going to get jrmuizel to do this tomorrow.
We got a backout landed on Holly - backed out as https://hg.mozilla.org/projects/holly/rev/9e7f91032d7d.

This puts us in the awkward position of having status-firefox28 being WONTFIX, but the target milestone still at Firefox 28 because 29 does not exist.

I've adjusted the target milestone accordingly.
Target Milestone: mozilla28 → mozilla29
Depends on: 947847
Whiteboard: [not-fixed-in-holly]
The patch of this bug broke the composition function of b2g keyboard as well. See bug 946068.
Sorry, the root cause of bug 946068 is not this bug.
No longer depends on: 946068
Whiteboard: [not-fixed-in-holly] → [not-fixed-in-holly][qa-]
Depends on: 1027000
You need to log in before you can comment on or make changes to this bug.