Improve DisplayList bounds calculations #28656

flar · 2021-09-16T05:05:36Z

These changes are to help improve our bounds calculations - and thus our cache memory usage - for the DisplayList.

The effort was triggered by the regression documented in flutter/flutter#88745 which resulted in disabling the DisplayList mechanism by default in the product. Rerunning the tests confirms that this PR fixes flutter/flutter#88745

Testing locally with the Flutter Gallery transition benchmarks we could see that our cache usage was higher with DisplayList and we've taken a number of steps to reduce that usage back to the baseline, including this PR and #28158 and #28287.

Improving our bounds resulted in a whole new algorithm for the DisplayListBoundsCalculator class which now does all of its own work except for a few cases where we deal with opaque Skia objects which must be trusted as sources or modifiers of rendering bounds (SkTextBlob, ShadowUtils, SkImageFilter, SkMaskFilter, SkPathEffect). Some reasons for introducing the new architecture were:

Avoiding having to translate the DisplayList data into an SkPaint to compute the bounds
Avoiding the fact that SkPaint cannot distinguish between various operations which have reduced bounds considerations (some operations are always strokes, others are always fills, some cannot produce a miter or an end cap, some may not be governed by a MaskFilter or PathEffect during rendering, etc). The SkPaint bounds computation method does not allow the caller to specify these conditions and so it would often produce bounds that were unnecessarily conservative because it took action based on attributes that didn't apply. Trying to "patch up" an SkPaint to reflect these conditions ended up even more complicated than just avoiding it in the first place.
Avoiding some bugs in Skia bounds computations (which have all been reported). Most of these issues were due to a heavy reliance on developers only setting "the right attributes" that belonged with a given operation, but some of them resulted in under-computing the proper bounds (triggering a test failure in the canvas unit tests heavily updated in this PR). These issues have workarounds and you can see a number of lines of code in that file that refer to Skia bugs on a line that works around the referenced bugs...

For this PR the bounds accuracy testing in display_list_canvas_unittests.cc have been enabled by default and they now verify what should be reasonably optimal bounds representing a tradeoff between time and area. More importantly, there is an assert that our bounds are never larger than the bounds computed by SkPicture/Recorder for the tested cases which are fairly extensive, representing:

Every drawing operation we support
Rendered with every Paint attribute we support
Rendered with a variety of Clip options
Rendered with a variety of transforms
Rendered with a few cases of save/saveLayer/restore

The matrix of tests is quite large and the bounds returned are both encompassing of all pixels that were rendered (or else a hard test failure results) and no looser than those computed by the Skia mechanism (which, for now, just reports the condition as it does not represent a functional program bug). (Note that our bounds accuracy performance is already being tracked by the recent changes to report cache metrics for all benchmarks to Skia Perf so we should get perf failures if our cache usage regresses.)

The tests were modified in a couple of key ways to try to verify these conditions:

Some tests were rendering a simple version of the primitive that didn't exhibit any corner cases (such as path join miters in particular). The tests were modified where possible to try to trigger any conditions that are covered by conservative estimates in the bounds calculations. Basically, they now try to "earn" their conservative bounds.
A "tolerance" object was added to the bounds tests to help account for cases where the bounds would be calculated with a conservative consideration that the test case cannot correct for. For example, the bounds calculation code might compute the bounds of a simple horizontal line as if it has an unruly assortment of geometry that triggers worst cases for joins, end caps, and path effects. Unfortunately, simple lines can never do that and the code to detect that case in the bounds calculations is outside of our current concept of a tradeoff between accuracy and computational speed - so we add a tolerance to the testing computations in some of those cases to overlook or forgive that extra bounds padding.
Another tolerance case is an SkTextBlob for which we rely on Skia to tell us what the bounds of the glyphs are - but they return a dramatic overestimate of those bounds based on maximal typographic metrics and obscure glyphs present in the font. Even using the supposedly homogenous ahem font still produces wildly over-estimated bounds for a simple string. So, a tolerance for the base bounds of a text blob are recorded.
Finally, some of the adjustments are attribute-specific. To that end, an adjuster function is allowed which can dynamically update the tolerances based on the final rendering attributes. This is used to dynamically handle path effect tolerances for lines as well as targeting a relaxation of tolerances for some operations under a perspective transform where the bounds computed are highly conservative.

A minor, seemingly unrelated, change in the code was made to rename one of the parameters to drawShadow which had a name that conflicted with its usage. It shouldn't have been causing problems because it was just passed along from source to destination as "that flag that the developer handed us and which we need to remember and eventually pass to Skia". Since we never interpreted its value ourselves, the name didn't really matter, but I noticed it was wrong when I was updating the shadow tests.

…unds

flar · 2021-09-16T21:35:31Z

After re-running the internal memory consumption tests on this cherry-picked PR, it appears that this patch results in undoing the regressions of flutter/flutter#88745

dnfield

Cool! Mostly nits, main concern is around the threading questions.

flow/display_list_utils.cc

flow/display_list_utils.h

dnfield · 2021-09-16T22:06:12Z

flow/display_list_utils.h

+  static constexpr int kIsNonGeometric = 0x00;
+
+  // A geometric operation that is defined as a fill operation
+  // regardless of what the current paint Style is set to.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsFilledGeometry = 0x01;
+
+  // A geometric operation that is defined as a stroke operation
+  // regardless of what the current paint Style is set to.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsStrokedGeometry = 0x02;
+
+  // A geometric operation that may be a stroke or fill operation
+  // depending on the current state of the paint Style attribute.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsDrawnGeometry = 0x04;
+
+  static constexpr int kIsAnyGeometryMask =  //
+      kIsFilledGeometry |                    //
+      kIsStrokedGeometry |                   //
+      kIsDrawnGeometry;


Consider an enum class.

(for this and below)

These are mask constants...?

Yes, you can still define them as an enum class to get some more type safety, but I believe you'd have to overload any operators you use to do so. Your call.

I like the idea of using an enum if we don't want to make it an enum class which would need overloading the operators. Just groups the various values better IMO.

enum FlagValue { kSomething = 1 << 0, kSomethingElse = 1 << 1, kAnotherThing = 1 << 2, };

I see lots of tutorials on this, but none of them answer the basic question of "why".

enums are enumerable. You can see all of its values right there.

Except if it is flags then you don't see all of its values right there. You can make up other values by combining them. Which of the enumerated values is kIsFrog | kIsZebra. I don't see a "zebra frog" in the list and such an animal would not likely survive long.

So, this concept has philosophical problems.

What advantages does it provide? "Hey, it's an enum!" - and how does that help anything?

One of the advantages of enums is knowing that your switch statements are complete, but you don't use flags in switches and if you did this aspect of enums would lie to you. As long as you had a case for each bit flag (which would be a horribly inefficient switch table) then it would think things were complete.

I suppose it has a type associated with it, but I feel like it is expressing "apples" as if they were "oranges".

If you use an enum class the compiler will help make sure you use the right types and don't end up accidentally mixing things up. But it does require operator overloading

flow/display_list_utils.h

flar · 2021-09-16T22:35:30Z

I filed flutter/flutter#90232 and linked it into flutter/flutter#85737 for updating the DisplayList API names.

chinmaygarde

Thanks for the great PR commit message. Helped me understand what you were going for. I took a close look at the unit-tests but must admit I could not follow how the tolerances were setup. Some other minor comments but otherwise looks good to me.

flow/display_list.cc

flow/display_list_canvas_unittests.cc

flow/display_list_utils.h

chinmaygarde · 2021-09-17T00:52:48Z

flow/display_list_utils.h

+    virtual BoundsAccumulator* accumulatorForRestore() { return outer_; }
+    virtual SkRect getLayerBounds() { return SkRect::MakeEmpty(); }
+
+    // is_flooded is to true if we ever encounter an operation


In this case, won't the bounds be infinitely big? Not sure why we need two fields to convey this information.

Only if they failed to provide a cull rect or surround these operations with a clip.

I'm following what happens with SkPicture. If you record one with no bounds then the cull rect defaults to an empty rect. When they encounter an op with no bounds (drawColor for instance) then they accumulate the cull rect - which is empty if it was defaulted - which is a NOP.

Essentially I do the same thing, but at least I set a flag indicating that you had an unbounded operation with no cull rect or clip to contain it.

If I returned an infinite bounds then you'd lose any information on what was drawn that was reasonably bounded. With Skia you'd at least get the bounds of the finite operations and so I wanted to follow suit.

chinmaygarde · 2021-09-17T00:53:55Z

flow/display_list_utils.h

+
+    virtual BoundsAccumulator* accumulatorForLayer() { return outer_; }
+    virtual BoundsAccumulator* accumulatorForRestore() { return outer_; }
+    virtual SkRect getLayerBounds() { return SkRect::MakeEmpty(); }


This can be pure virtual right? Can you also document these virtuals? And also OOL them?

Making them pure virtual may make the subclasses slightly easier to read. Perhaps also just document them. Your call.

If they were pure virtual then I'd need another class just to implement the most common trivial implementations.

flow/display_list_utils.h

chinmaygarde · 2021-09-17T01:04:08Z

flow/display_list_utils.h

+  static constexpr int kIsNonGeometric = 0x00;
+
+  // A geometric operation that is defined as a fill operation
+  // regardless of what the current paint Style is set to.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsFilledGeometry = 0x01;
+
+  // A geometric operation that is defined as a stroke operation
+  // regardless of what the current paint Style is set to.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsStrokedGeometry = 0x02;
+
+  // A geometric operation that may be a stroke or fill operation
+  // depending on the current state of the paint Style attribute.
+  // This flag will automatically assume |kApplyMaskFilter|.
+  static constexpr int kIsDrawnGeometry = 0x04;
+
+  static constexpr int kIsAnyGeometryMask =  //
+      kIsFilledGeometry |                    //
+      kIsStrokedGeometry |                   //
+      kIsDrawnGeometry;


I like the idea of using an enum if we don't want to make it an enum class which would need overloading the operators. Just groups the various values better IMO.

enum FlagValue { kSomething = 1 << 0, kSomethingElse = 1 << 1, kAnotherThing = 1 << 2, };

flow/display_list_utils.h

flar · 2021-09-17T04:45:50Z

Still TBD - a better name for "transparentOccluder" that doesn't parse as "the thing, except its not the thing because it has a flaw". (I added this to the issues mentioned in the Flutter Issue below. The name, for now, at least matches what Skia and PhysicalShapeLayer call the parameter...)

I am not planning on switching the flags to enums at this point.

Naming style issues will be considered in a sweep once the functional bugs are all fixed. See flutter/flutter#90232

chinmaygarde

Looks good to me. Are there any open questions from other reviewers to be handled here?

flow/display_list_canvas_unittests.cc

flow/display_list_utils.h

flar · 2021-09-17T18:58:55Z

Looks good to me. Are there any open questions from other reviewers to be handled here?

@dnfield ?

flar · 2021-09-17T20:21:56Z

It looks like dnfield cannot get back to this today. I don't think he expressed any functional concerns (other than the GPU lifetime concerns that were already patched by another PR) and I believe that the code style concerns he expressed can be dealt with under flutter/flutter#90232 so I'm going to land this and can address any remaining concerns with future PRs.

flar added 5 commits September 14, 2021 11:26

improve display list bounds calculations

615bccc

rework bounds calculations for better layer bounds management

94d0ed2

add SaveLayer tests to DL_canvas test suite and fix discovered bugs

7391696

first pass at improving corner cases of bounds testing

66cc99d

major updates to bounds testing and a minor improvement in dashing bo…

957e543

…unds

google-cla bot added the cla: yes label Sep 16, 2021

zanderso requested review from chinmaygarde and dnfield September 16, 2021 21:26

flar mentioned this pull request Sep 16, 2021

20% graphics memory increase in latest roll flutter/flutter#88745

Closed

dnfield reviewed Sep 16, 2021

View reviewed changes

flar mentioned this pull request Sep 16, 2021

Update DisplayList method names for Flutter style guidelines flutter/flutter#90232

Closed

chinmaygarde reviewed Sep 17, 2021

View reviewed changes

feedback from review, naming, final modifiers, abbreviations in strings

7f54d56

chinmaygarde approved these changes Sep 17, 2021

View reviewed changes

flow/display_list_canvas_unittests.cc Show resolved Hide resolved

flow/display_list_utils.h Show resolved Hide resolved

flar requested a review from dnfield September 17, 2021 18:59

flar added the waiting for tree to go green This PR is approved and tested, but waiting for the tree to be green to land. label Sep 17, 2021

fluttergithubbot merged commit e1e6a41 into flutter:master Sep 17, 2021

engine-flutter-autoroll mentioned this pull request Sep 17, 2021

Roll Engine from 4a803193817d to e1e6a41df77d (2 revisions) flutter/flutter#90297

Merged

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Sep 17, 2021

e1e6a41 Improve DisplayList bounds calculations (flutter/engine#28656)

f4e8252

akbiggs pushed a commit to akbiggs/engine that referenced this pull request Sep 21, 2021

Improve DisplayList bounds calculations (flutter#28656)

d068f0f

flar mentioned this pull request Sep 21, 2021

adjust naming of DisplayList methods, fields and parameters to match style guide #28753

Merged

This was referenced Sep 30, 2021

☂️ - Take advantage of new DisplayList format flutter/flutter#85737

Closed

DisplayList should compute bounds directly flutter/flutter#91060

Closed

Improve DisplayList bounds calculations #28656

Improve DisplayList bounds calculations #28656

Uh oh!

Conversation

flar commented Sep 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

flar commented Sep 16, 2021

Uh oh!

dnfield left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

flar commented Sep 16, 2021

Uh oh!

chinmaygarde left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

flar commented Sep 17, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

chinmaygarde left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

flar commented Sep 17, 2021

Uh oh!

flar commented Sep 17, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

flar commented Sep 16, 2021 •

edited

Loading

flar commented Sep 17, 2021 •

edited

Loading