[Impeller] Polyline generation optimization. #36759

dnfield · 2022-10-14T18:16:43Z

The proposed approach has several advantages:

It is much faster for quadratics, since we no longer have to
elevate them to cubics.
It is slightly slower for cubics, but also produces fewer and
more accurate points on average, which results in faster
tessellation and a net decrease in CPU time.
The core of the algorithm is parallelizable, which should make it
easier to use on the GPU without significant changes.

Before this change:

2022-10-14T11:11:14-07:00
Running out/host_release/geometry_benchmarks
Run on (10 X 2400 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB (x10)
  L1 Instruction 128 KiB (x10)
  L2 Unified 4096 KiB (x5)
Load Average: 7.00, 5.70, 5.09
------------------------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations UserCounters...
------------------------------------------------------------------------------------------
BM_Polyline/cubic_polyline           22642 ns        22585 ns        31151 SinglePointCount=251 TotalPointCount=7.8189M
BM_Polyline/cubic_polyline_tess      78041 ns        77847 ns         9114 SinglePointCount=251 TotalPointCount=2.28761M
BM_Polyline/quad_polyline            22622 ns        22562 ns        31047 SinglePointCount=236 TotalPointCount=7.32709M
BM_Polyline/quad_polyline_tess       74762 ns        74563 ns         9318 SinglePointCount=236 TotalPointCount=2.19905M

After:

2022-10-14T11:12:26-07:00
Running out/host_release/geometry_benchmarks
Run on (10 X 2400 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB (x10)
  L1 Instruction 128 KiB (x10)
  L2 Unified 4096 KiB (x5)
Load Average: 4.32, 5.21, 4.96
------------------------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations UserCounters...
------------------------------------------------------------------------------------------
BM_Polyline/cubic_polyline           35580 ns        35574 ns        19980 SinglePointCount=155 TotalPointCount=3.0969M
BM_Polyline/cubic_polyline_tess      70250 ns        70240 ns         9998 SinglePointCount=155 TotalPointCount=1.54969M
BM_Polyline/quad_polyline            15065 ns        15062 ns        46802 SinglePointCount=144 TotalPointCount=6.73949M
BM_Polyline/quad_polyline_tess       48014 ns        47992 ns        14644 SinglePointCount=144 TotalPointCount=2.10874M

I want the benchmark to land first.

Bottom line is that creating polylines for quadratics gets much faster/leaner/more accurate. Creating polylines for cubics gets slightly slower but creates fewer more accurate points. This is a big win for quadratics, and a small win for cubics once you include tessellation.

The other nice property is that these algorithms are more translatable to shaders than the recursive algorithm.

The proposed approach has several advantages: - It is _much_ faster for quadratics, since we no longer have to elevate them to cubics. - It is slightly slower for cubics, but also produces fewer and more accurate points on average, which results in faster tessellation and a net decrease in CPU time. - The core of the algorithm is parallelizable, which should make it easier to use on the GPU without significant changes. I do not intend to land the changes to the benchmark in this patch, but it was helpful for local testing. Before landing this I will update/add appropriate benchmarks.

dnfield · 2022-10-14T18:24:43Z

Argh. One of these commits had a ncie message I'll try to lift into the body of the PR...

dnfield · 2022-10-14T20:56:43Z

This is ready for review.

chinmaygarde

I have definitely not dedicated the time needed to understand and appreciate the technique in detail. Will definitely do so over the weekend. I did play around with the results. Perhaps, as a followup, add sections about this to the wiki (go/impeller-docs) or references to the reading list (go/impeller-reading-list)?

chinmaygarde · 2022-10-18T18:44:57Z

impeller/tessellator/c/tessellator.h

                                         int fill_type,
-                                         Scalar scale,
+                                         Scalar tolerance,
+                                         // Unused, remaining for ABI stability.


Can we clean this up at all?

vector_graphics is potentially using these parameters and would crash without them. Although I don't think we actually have anything using them right now - I'll just drop them for now and we can clean up vg separately.

chinmaygarde · 2022-10-18T18:45:26Z

impeller/geometry/path_component.h


  std::vector<Point> Extrema() const;

+  std::vector<QuadraticPathComponent> ToQuadratics(Scalar accuracy) const;


ToQuadraticPathComponent?

done, but with the s still :)

chinmaygarde · 2022-10-18T18:46:43Z

impeller/geometry/path_component.cc

+  auto a0 = ApproximateParabolaIntegral(x0);
+  auto a2 = ApproximateParabolaIntegral(x2);
+  Scalar val = 0.f;
+  if (isfinite(scale)) {


std::isfinite

dnfield · 2022-10-19T03:36:50Z

I had already added some sources to the reading list related to this, and there are some links in the comments - definitely let me know if there's still something missing, because I spent a few days immersed in this and probably missed adding something.

auto-submit · 2022-10-19T03:40:09Z

auto label is removed for flutter/engine, pr: 36759, due to - The status or check suite Mac iOS Engine has failed. Please fix the issues identified (or deflake) before re-applying this label.

The status or check suite Mac Host Engine has failed. Please fix the issues identified (or deflake) before re-applying this label.
The status or check suite Linux linux_host_engine has failed. Please fix the issues identified (or deflake) before re-applying this label.
The status or check suite Linux linux_arm_host_engine has failed. Please fix the issues identified (or deflake) before re-applying this label.
The status or check suite Linux Android AOT Engine has failed. Please fix the issues identified (or deflake) before re-applying this label.

dnfield · 2022-10-19T05:26:03Z

https://flutter-engine-perf.skia.org/e/?keys=X18cd97edd746da8f4ac526310da80177

…e#36759)

…113761) * 9f09f4ce8 Roll Dart SDK from f21024945abf to 99f266a404bd (1 revision) (flutter/engine#36860) * 3f58c9743 [Impeller] Polyline generation optimization. (flutter/engine#36759) * d6ccb2d67 Roll Skia from af544866f04d to 161637433767 (1 revision) (flutter/engine#36861) * f32d29056 Add DOM TouchEvent modifiers accessors (flutter/engine#36836) * dd9159958 Roll Fuchsia Linux SDK from oMrS1TjaSIjntnBvR... to IvN-WLezL2sS_wSzZ... (flutter/engine#36862) * cfe164f66 [fuchsia][scenic] Fix invalid viewRef error in pointer injection. (flutter/engine#36850) * bd15adf16 Roll Skia from 161637433767 to 50363183d1c7 (3 revisions) (flutter/engine#36864) * e351b05c7 Roll Fuchsia Mac SDK from XZV0Cqcpiv74L7ric... to M5-c50jCcV0ypwYcT... (flutter/engine#36865) * a89ed7a72 Roll Skia from 50363183d1c7 to 572d4e85f83e (1 revision) (flutter/engine#36867) * cca0812cf Roll Skia from 572d4e85f83e to 8928b024556f (1 revision) (flutter/engine#36868) * 488b76725 Roll Skia from 8928b024556f to 025ae7eec03e (6 revisions) (flutter/engine#36869) * 7997edc4f [web] Some cleanup for text tests (flutter/engine#36425) * a831dd269 Roll Skia from 025ae7eec03e to a9255bc938bf (1 revision) (flutter/engine#36870) * 80847c95f [fuchsia][input] Delete legacy pointer handler (flutter/engine#36857) * e4c27fc90 Roll Skia from a9255bc938bf to 4fa600316d1d (6 revisions) (flutter/engine#36872) * 9e635b177 Roll Fuchsia Linux SDK from IvN-WLezL2sS_wSzZ... to zw_jyeiHfJtAXF_qp... (flutter/engine#36875) * a5c5c25ba Roll Skia from 4fa600316d1d to 723ccd171e37 (3 revisions) (flutter/engine#36876) * 2f235c4ba Roll Fuchsia Mac SDK from M5-c50jCcV0ypwYcT... to 7lmBrmhOLwrqoqXk0... (flutter/engine#36877) * 0f0739651 [fuchsia] Bump the Fuchsia target API level to 10 (flutter/engine#36858) * 490b06d13 Roll Skia from 723ccd171e37 to fc7d5c9ee970 (1 revision) (flutter/engine#36878)

dnfield added 9 commits October 12, 2022 21:26

Add polyline benchmark with lots of cubics and quads

f88929c

Counters

1399c98

Update build file

c570f08

Tessellate too

5cd28d7

merge

81da8f6

Refactor polyline bench slightly, add benchmarks including tessellation

d2e8f15

merge

6475d1c

unused test code

3ac466e

dnfield requested review from bdero, chinmaygarde and jonahwilliams October 14, 2022 18:16

dnfield added 2 commits October 14, 2022 11:22

make tessellator static

3fc3ff9

merge

630140f

chinmaygarde changed the title ~~Polyline opt~~ [Impeller] Polyline generation optimization. Oct 14, 2022

chinmaygarde assigned dnfield Oct 14, 2022

chinmaygarde added the e: impeller label Oct 14, 2022

dnfield marked this pull request as ready for review October 14, 2022 20:56

chinmaygarde approved these changes Oct 18, 2022

View reviewed changes

dnfield added 2 commits October 18, 2022 20:32

merge

2d70679

review

dd0c272

dnfield added the autosubmit Merge PR when tree becomes green via auto submit App label Oct 19, 2022

auto-submit bot removed the autosubmit Merge PR when tree becomes green via auto submit App label Oct 19, 2022

Save before commit...

bbe5364

dnfield added the autosubmit Merge PR when tree becomes green via auto submit App label Oct 19, 2022

auto-submit bot merged commit 3f58c97 into flutter:main Oct 19, 2022

dnfield deleted the polyline_opt branch October 19, 2022 05:21

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to 3f58c9743662 (7 revisions) flutter/flutter#113672

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

beee359

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to d6ccb2d67e50 (8 revisions) flutter/flutter#113674

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

5050d00

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to f32d290564e7 (9 revisions) flutter/flutter#113675

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

15cc1e6

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to dd91599581e0 (10 revisions) flutter/flutter#113676

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

47f2ab4

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to cfe164f66119 (11 revisions) flutter/flutter#113678

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

3f71279

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to bd15adf1651e (12 revisions) flutter/flutter#113679

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

72e917d

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to e351b05c7297 (13 revisions) flutter/flutter#113684

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

f75fde2

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to e351b05c7297 (13 revisions) flutter/flutter#113686

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

1368ae5

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to e351b05c7297 (13 revisions) flutter/flutter#113695

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

9509aeb

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to a89ed7a722a1 (14 revisions) flutter/flutter#113698

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

cddb1fd

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 19, 2022

Roll Flutter Engine from 563b8e830c69 to cca0812cf700 (15 revisions) flutter/flutter#113701

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 19, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

cd9f544

…e#36759)

engine-flutter-autoroll mentioned this pull request Oct 20, 2022

Roll Flutter Engine from d62aa9526a56 to 490b06d13390 (20 revisions) flutter/flutter#113761

Merged

engine-flutter-autoroll added a commit to engine-flutter-autoroll/flutter that referenced this pull request Oct 20, 2022

3f58c9743 [Impeller] Polyline generation optimization. (flutter/engin…

ab1735f

…e#36759)


		std::vector<Point> Extrema() const;

		std::vector<QuadraticPathComponent> ToQuadratics(Scalar accuracy) const;

[Impeller] Polyline generation optimization. #36759

[Impeller] Polyline generation optimization. #36759

Uh oh!

Conversation

dnfield commented Oct 14, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dnfield commented Oct 14, 2022

Uh oh!

dnfield commented Oct 14, 2022

Uh oh!

chinmaygarde left a comment

Choose a reason for hiding this comment

Uh oh!

chinmaygarde Oct 18, 2022

Choose a reason for hiding this comment

Uh oh!

dnfield Oct 19, 2022

Choose a reason for hiding this comment

Uh oh!

chinmaygarde Oct 18, 2022

Choose a reason for hiding this comment

Uh oh!

dnfield Oct 19, 2022

Choose a reason for hiding this comment

Uh oh!

chinmaygarde Oct 18, 2022

Choose a reason for hiding this comment

Uh oh!

dnfield Oct 19, 2022

Choose a reason for hiding this comment

Uh oh!

dnfield commented Oct 19, 2022

Uh oh!

auto-submit bot commented Oct 19, 2022

Uh oh!

dnfield commented Oct 19, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

dnfield commented Oct 14, 2022 •

edited

Loading