Closed Bug 1236043 Opened 8 years ago Closed 8 years ago

Use a different approach for simplifying the invalid region of a layer (TiledRegion)

Categories

(Core :: Graphics: Layers, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla48
Tracking Status
firefox46 --- affected
firefox48 --- fixed

People

(Reporter: mstange, Assigned: mstange)

References

(Depends on 6 open bugs)

Details

(Keywords: feature, Whiteboard: gfx-noted)

Attachments

(4 files, 4 obsolete files)

This is similar to bug 1169502 (which I never finished), but for the invalid region of a layer.

We frequently have the problem that we invalidate too much during scrolling because stuff gets invalidated both on the top and on the bottom of the display port, and our invalid region simplification causes the invalid region to include stuff in between.

Bug 1164227 worked around this for some cases, but it's not catching all of them - for example the testcase in bug 1221094 still invalidates even with the patches in that bug. The workaround from bug 1164227 also doesn't help if web authors do their own display port management in JS.

The reason we call mInvalidRegion.SimplifyOutward(20) in the first place is that we want to limit the complexity of the region so that operations on it are fast.
But there are other ways we can limit the complexity of a region than just by counting rectangles.
A few months ago, Jeff and I came up with the idea of a tiled region: A region structure that stores one rectangle per tile, based on some fixed tile size (which doesn't necessarily have to match the size of our PaintedLayer tiles). This kind of region structure would only be used for regions which are allowed to include more pixels than requested - they have to, because many region shapes can not be represented with just one rectangle per tile. But for the invalid region of a layer, that's exactly what we want.
A tiled region would still have a limit on its complexity (rectangle count <= tile count == ceil(layer width / tile size) * ceil(layer height / tile size)), and it would never simplify across tiles. There wouldn't even be a separate simplification step - the region automatically "simplifies" whenever you accumulate a new rectangle or region into it.
Attached patch proof of concept (obsolete) — Splinter Review
This patch works surprisingly well. Algorithmically it's really bad, though.

Jeff, do you have any thoughts on how this should be implemented?
Flags: needinfo?(jmuizelaar)
(In reply to Markus Stange [:mstange] from comment #1)
> Created attachment 8703150 [details] [diff] [review]
> proof of concept
> 
> This patch works surprisingly well. Algorithmically it's really bad, though.
> 
> Jeff, do you have any thoughts on how this should be implemented?

Can you summarize the semantics of TiledRegion in your patch?
Flags: needinfo?(jmuizelaar)
TiledRegion only supports the Or operation, or being initialized with an existing region. In both cases it processes the region and makes sure that there is only one rectangle per tile, enlarging the region if necessary. (So "OrWith" should really be called "Accumulate" or "AccumulateAndPossiblyEnlarge", but I wanted a drop-in replacement so that I wouldn't have to change the callers.)
Flags: needinfo?(jmuizelaar)
Whiteboard: gfx-noted
Keywords: feature
Attached patch proof of concept (obsolete) — Splinter Review
Attachment #8703150 - Attachment is obsolete: true
Comment on attachment 8734002 [details] [diff] [review]
proof of concept

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

::: gfx/src/TiledRegion.h
@@ +82,5 @@
> +    }
> +    mCachedRegionIsValid = false;
> +  }
> +
> +  void OrWith(const Region& aRegion) {

You should probably just loop over the region's rectangles and or them in. That will make things faster.

@@ +197,5 @@
> +    MOZ_ASSERT(aTilePosition.x < mTileBounds.XMost());
> +    MOZ_ASSERT(aTilePosition.y < mTileBounds.YMost());
> +    MOZ_ASSERT(aTilePosition.x % TileSize == 0);
> +    MOZ_ASSERT(aTilePosition.y % TileSize == 0);
> +    int32_t colCount = mTileBounds.width / TileSize;

Watch out for signed division being turned into extra instructions of negative numbers.
Attached patch wip (obsolete) — Splinter Review
Attachment #8734002 - Attachment is obsolete: true
Summary: Use a different approach for simplifying the invalid region of a layer → Use a different approach for simplifying the invalid region of a layer (TiledRegion)
Attachment #8734093 - Attachment is obsolete: true
(In reply to Jeff Muizelaar [:jrmuizel] from comment #5)
> @@ +197,5 @@
> > +    MOZ_ASSERT(aTilePosition.x < mTileBounds.XMost());
> > +    MOZ_ASSERT(aTilePosition.y < mTileBounds.YMost());
> > +    MOZ_ASSERT(aTilePosition.x % TileSize == 0);
> > +    MOZ_ASSERT(aTilePosition.y % TileSize == 0);
> > +    int32_t colCount = mTileBounds.width / TileSize;
> 
> Watch out for signed division being turned into extra instructions of
> negative numbers.

It doesn't look like that's happening... I'm attaching the disassembly if you want to read it. I experimented with adding uint32_t casts all over the place and it didn't change anything.
Assignee: nobody → mstange
Status: NEW → ASSIGNED
Flags: needinfo?(jmuizelaar)
Comment on attachment 8735605 [details]
MozReview Request: Bug 1236043 - Add a TiledRegion class. r?jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/42865/diff/1-2/
Comment on attachment 8735606 [details]
MozReview Request: Bug 1236043 - Use TiledRegion for the invalid region of a layer. r?jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/42867/diff/1-2/
This still has quite a few failures on try. Looking into those.
Depends on: 1260965
Make the test_transformed_scrolling_repaints* tests taller so that the top and the bottom of the scrolled area don't share the same tile.
Fuzz layout/reftests/text/wordwrap-03.html on Linux because the native textbox gradient is painted in a slightly different position depending on the invalid area.
Mark layout/reftests/forms/select/out-of-bounds-selectedindex.html as fuzzy on Android because some listbox rounded corner pixel differs with the new invalidation behavior.
Mark layout/reftests/bugs/456219-1c.html as fuzzy on Linux, reasons unknown. :-(
Disable flexbox-widget-flex-items-3.html because of bad file input drawing on Linux, see bug 1260965.

Review commit: https://reviewboard.mozilla.org/r/44413/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/44413/
Attachment #8738282 - Flags: review?(jmuizelaar)
Comment on attachment 8735605 [details]
MozReview Request: Bug 1236043 - Add a TiledRegion class. r?jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/42865/diff/2-3/
Comment on attachment 8735606 [details]
MozReview Request: Bug 1236043 - Use TiledRegion for the invalid region of a layer. r?jrmuizel

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/42867/diff/2-3/
Attachment #8735604 - Attachment is obsolete: true
Attachment #8735604 - Flags: review?(jmuizelaar)
With this new patch set, there's one last test failure left to fix: test_transformed_scrolling_repaints_3.html on Windows 7.
https://treeherder.mozilla.org/#/jobs?repo=try&revision=c9cdfce097ca
Comment on attachment 8735605 [details]
MozReview Request: Bug 1236043 - Add a TiledRegion class. r?jrmuizel

https://reviewboard.mozilla.org/r/42865/#review42673

::: gfx/src/TiledRegion.h:40
(Diff revision 3)
> + * size is hard-coded as kTileSize in TiledRegion.cpp.
> + * A TiledRegion starts out empty. You can add rectangles or (regular) regions
> + * into it by calling Add(). Add() is a mutating union operation (similar to
> + * OrWith on nsRegion) that's *not* exact, because it will enlarge the region as
> + * necessary to satisfy the "one rectangle per tile" requirement.
> + * Tiled regions convert implicitly to the underlying regular region type.

I'd prefer to not have the implicit conversion as it's a somewhat expensive operation.

::: gfx/src/TiledRegion.cpp:105
(Diff revision 3)
> +};
> +
> +// A TileRange describes a range of tiles contained inside a certain tile
> +// bounds (which is a rectangle that includes all tiles that you're
> +// interested in). The tile range can start and end at any point inside a
> +// tile row.

"The tile range can start and end at any point inside inside the tile bounds"

::: gfx/src/TiledRegion.cpp:108
(Diff revision 3)
> +// bounds (which is a rectangle that includes all tiles that you're
> +// interested in). The tile range can start and end at any point inside a
> +// tile row.
> +// The tile range end is described by the tile that starts at the bottom
> +// left corner of the tile bounds, i.e. the first tile under the tile
> +// bounds.

This sentence is wrong.
"The tile range end sentinel is described by the tile that the tile iterator would advance to after the last tile" e.g. the first tile under the tile bounds if tile range extends completely to the right most wall of the tile bounds.

::: gfx/src/TiledRegion.cpp:113
(Diff revision 3)
> +// bounds.
> +class TileRange {
> +public:
> +  // aTileBounds, aStart and aEnd need to be aligned with the tile grid.
> +  TileRange(const pixman_box32_t& aTileBounds,
> +            const IntPoint& aStart, const IntPoint& aEnd)

It looks like you only need a Size instead of a pixman_box32_t to specify the area. I'm not sure it's worth making this change though.

::: gfx/src/TiledRegion.cpp:137
(Diff revision 3)
> +      return (mEnd.x - mStart.x) / kTileSize;
> +    }
> +    size_t numberOfFullRows = (mEnd.y - mStart.y) / kTileSize - 1;
> +    return (mTileBounds.x2 - mStart.x) / kTileSize +
> +      (mTileBounds.x2 - mTileBounds.x1) / kTileSize * numberOfFullRows +
> +      (mEnd.x - mTileBounds.x1) / kTileSize;

Seems like you could factor out the / kTileSize

::: gfx/src/TiledRegion.cpp:292
(Diff revision 3)
> +           ++tileIt, ++rectIndex) {
> +        mRects[rectIndex] = tileIt.IntersectionWith(aRect);
> +      }
> +      return IterationAction::CONTINUE;
> +    },
> +    [&](size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {

If these lambdas both take a reference to the nsTArray as a parameter you can drop all off the captures. This should make it easier for the compiler to understand what's going on.
Attachment #8735605 - Flags: review?(jmuizelaar) → review+
Attachment #8735606 - Flags: review?(jmuizelaar) → review+
Comment on attachment 8735606 [details]
MozReview Request: Bug 1236043 - Use TiledRegion for the invalid region of a layer. r?jrmuizel

https://reviewboard.mozilla.org/r/42867/#review42989
Comment on attachment 8738282 [details]
MozReview Request: Bug 1236043 - Adjust reftest conditions for new invalid region simplification. r?jrmuizel

https://reviewboard.mozilla.org/r/44413/#review42991

I like it when the reftest annotations include the rationale. Do this as much as you please.
Attachment #8738282 - Flags: review?(jmuizelaar) → review+
Landed yeterday (probably didn't get marked due to 'back out' and its number right after):
https://hg.mozilla.org/mozilla-central/rev/195696ac5a24
https://hg.mozilla.org/mozilla-central/rev/62108d9ec459
https://hg.mozilla.org/mozilla-central/rev/9116ef367e02
https://hg.mozilla.org/mozilla-central/rev/be713202544a
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
Depends on: 1266161
Depends on: 1266051
No longer depends on: 1266051
Depends on: 1276160
Depends on: 1281364
Depends on: 1283826
Depends on: 1274126
Depends on: 1401239
Depends on: 1402710
You need to log in before you can comment on or make changes to this bug.