[display_list] grow display list backing store by power of two. #56004

jonahwilliams · 2024-10-21T23:20:19Z

Right now the DL is always growing by a minimum 4096 bytes at a time. On applications with large display lists, this can lead to hundreds of reallocations as the display list is build, as long as each draw op is small. For example, the framework benchmark long picture scrolling draws many lines, each of which is a pretty small op.

Update the code so that we grow by doubling, with a minimum increment of ~16K

… limit

flutter-dashboard · 2024-10-21T23:20:22Z

It looks like this pull request may not have tests. Please make sure to add tests before merging. If you need an exemption, contact "@test-exemption-reviewer" in the #hackers channel in Discord (don't just cc them here, they won't see it!).

If you are not sure if you need tests, consider this rule of thumb: the purpose of a test is to make sure someone doesn't accidentally revert the fix. Ask yourself, is there anything in your PR that you feel it is important we not accidentally revert back to how it was before your fix?

Reviewers: Read the Tree Hygiene page and make sure this patch meets those guidelines before LGTMing. The test exemption team is a small volunteer group, so all reviewers should feel empowered to ask for tests, without delegating that responsibility entirely to the test exemption group.

chinmaygarde

Worth a shot as this is the same strategy used in the Impeller allocator too.

chinmaygarde · 2024-10-22T06:30:30Z

display_list/dl_builder.cc

+/// @brief Return the next power of 2.
+///
+/// If the provided value is a power of 2, returns as is.
+uint64_t NextPowerOfTwo(uint64_t x) {


This goop can be replaced with std::bit_ceil(x)? I remember I couldn't use it earlier because it was C++ 17 only.

It seems like this is C++ 20 only

chinmaygarde · 2024-10-22T06:32:01Z

display_list/dl_builder.cc

-    // Next greater multiple of DL_BUILDER_PAGE.
-    allocated_ = (used_ + size + DL_BUILDER_PAGE) & ~(DL_BUILDER_PAGE - 1);
+    // Next power of two, up to a limit of DL_BUILDER_MAX_GROWTH. This
+    // assumes that the requested size to allocate is alwaus less than


Typo: always

chinmaygarde · 2024-10-22T06:34:50Z

display_list/dl_builder.cc

 template <typename T, typename... Args>
 void* DisplayListBuilder::Push(size_t pod, Args&&... args) {
  size_t size = SkAlignPtr(sizeof(T) + pod);
  FML_CHECK(size < (1 << 24));


Does this assertion make sense now?

I'm not certain the origin of this check.

Me either, it might be a carry over from SkLiteDL days?

Lets remove it and see what breaks then :)

Ooopa. No! I just rememered!

It is necessary because the size field is 24-bits.

Well, I'll add it back when I get back lol

It's never fired AFAIK, so maybe this should be the impetus that gets me to rewrite builder to not use the size fields any more and produce the offset vector up front...

AFAIK this check could only fire If I tried to encode something that required allocating more than 1 << 24 bytes right?

flar

I'm pretty sure recording a very large drawVertices might overflow the growth code, there should be unit tests where we append very large ops. Things that append arrays to them include:

rendering ops that have gradients
drawAtlas
drawPoints
~~drawVertices~~ (oops, no, just copied by reference now)
(check anything that uses the CopyV mechanism that adds more data to the pod)

flar · 2024-10-22T20:54:08Z

display_list/dl_builder.cc

+    // assumes that the requested size to allocate is always less than
+    // kDLBuilderMaxGrowth, which given is over a MB is a reasonable
+    // assumption.
+    uint64_t next_size = NextPowerOfTwo(used_ + size);


used_ starts at 0, as does allocated_ and the first thing we record is something very small, like 8 bytes. So, we do our first growth to 8 bytes, then 16, then ... when our first growth used to be to 4096.

I think we need both a minimum starting size and a maximum growth size for this...

Good point, we should set a min size to the page size.

flar · 2024-10-22T20:55:42Z

display_list/dl_builder.cc

+    // assumption.
+    uint64_t next_size = NextPowerOfTwo(used_ + size);
+    uint64_t growth_in_bytes = (next_size - allocated_);
+    allocated_ += std::min(growth_in_bytes, kDLBuilderMaxGrowth);


If we need more than MaxGrowth then we fail here. You can max the "unused" part of the growth to MaxGrowth, but you can't make it less than the amount we need total (used_ + size). Better math is needed here...

okay, I think I was trying to be too clever. I've changed this code so that we always double, and we first increment by whatever is bigger - required size or page size, where page size is about 16K

jonahwilliams · 2024-10-22T21:17:15Z

I believe you changed drawVertices to not copy into the display list. drawPoints/drawAtlas still embed their data right?

flar · 2024-10-22T22:05:48Z

I believe you changed drawVertices to not copy into the display list. drawPoints/drawAtlas still embed their data right?

Anything that uses CopyV in dl_builder.cc could potentially have a very large size. I didn't double check, that list was off the top of my head...

jonahwilliams · 2024-10-22T22:26:06Z

Confirmed that drawPoints does it, I'll use this to test

flar

A nit on the data in the test.

flar · 2024-10-23T04:52:58Z

display_list/display_list_unittests.cc

+  EXPECT_EQ(NextPowerOfTwo(5), 8u);
+  EXPECT_EQ(NextPowerOfTwo(8), 8u);
+
+  EXPECT_EQ(NextPowerOfTwo(16), 16u);


I think you wanted 7 as the arg here?

Or something less than 16 but larger than 8...

flar · 2024-10-23T04:54:42Z

display_list/dl_builder.cc

 template <typename T, typename... Args>
 void* DisplayListBuilder::Push(size_t pod, Args&&... args) {
  size_t size = SkAlignPtr(sizeof(T) + pod);
  FML_CHECK(size < (1 << 24));


Me either, it might be a carry over from SkLiteDL days?

flar · 2024-10-23T04:56:09Z

display_list/dl_builder.cc

-    allocated_ = (used_ + size + DL_BUILDER_PAGE) & ~(DL_BUILDER_PAGE - 1);
+    // Round up the allocated size + used size to the next power of 2, with a
+    // minimum increment of kDLPageSize.
+    allocated_ = NextPowerOfTwo(used_ + std::max(size, kDLPageSize));


jonahwilliams · 2024-10-23T15:27:47Z

The benchmark to watch is https://flutter-flutter-perf.skia.org/e/?begin=1727976394&end=1729696415&queries=test%3Dvery_long_picture_scrolling_perf_ios__e2e_summary&requestType=0&selected=commit%3D42943%26name%3D%252Carch%253Dintel%252Cbranch%253Dmaster%252Cconfig%253Ddefault%252Cdevice_type%253DiPhone_11%252Cdevice_version%253Dnone%252Chost_type%253Dmac%252Csub_result%253D99th_percentile_frame_rasterizer_time_millis%252Ctest%253Dvery_long_picture_scrolling_perf_ios__e2e_summary%252C

…o. (flutter/engine#56004)

flutter/engine@50f6d98...ec6e28a 2024-10-23 jonahwilliams@google.com [display_list] grow display list backing store by power of two. (flutter/engine#56004) 2024-10-23 skia-flutter-autoroll@skia.org Roll Fuchsia Linux SDK from xPbin_33tT-_omeQT... to NxrFCTty8wV4-6Cpl... (flutter/engine#56056) 2024-10-23 skia-flutter-autoroll@skia.org Roll Dart SDK from 20470aaa17be to 2a4b728f6a03 (3 revisions) (flutter/engine#56055) 2024-10-23 robert.ancell@canonical.com Move get_keyboard_state from FlKeyboardViewDelegate to FlKeyboardManager. (flutter/engine#56021) 2024-10-23 robert.ancell@canonical.com Move send_key_event from FlKeyboardViewDelegate to FlKeyboardManager. (flutter/engine#56020) 2024-10-23 bdero@google.com [Flutter GPU] Fix assert failure in createDeviceBufferWithCopy. (flutter/engine#56039) 2024-10-22 skia-flutter-autoroll@skia.org Roll Dart SDK from 8de85635d731 to 20470aaa17be (4 revisions) (flutter/engine#56038) 2024-10-22 ditman@gmail.com [web] Remove old futureToPromise. (flutter/engine#55847) 2024-10-22 737941+loic-sharma@users.noreply.github.com [dart:ui] Improve Clip's docs (flutter/engine#55978) 2024-10-22 jonahwilliams@google.com [Impeller] flush thread local resources during toImage/toImageSync. (flutter/engine#56037) 2024-10-22 kpsroka@users.noreply.github.com [canvaskit] Makes access to CkSurface null-safer (flutter/engine#54895) Also rolling transitive DEPS: fuchsia/sdk/core/linux-amd64 from xPbin_33tT-_ to NxrFCTty8wV4 If this roll has caused a breakage, revert this CL and stop the roller using the controls here: https://autoroll.skia.org/r/flutter-engine-flutter-autoroll Please CC codefu@google.com,zra@google.com on the revert to ensure that a human is aware of the problem. To file a bug in Flutter: https://github.com/flutter/flutter/issues/new/choose To report a problem with the AutoRoller itself, please file a bug: https://issues.skia.org/issues/new?component=1389291&template=1850622 Documentation for the AutoRoller is here: https://skia.googlesource.com/buildbot/+doc/main/autoroll/README.md

jonahwilliams · 2024-10-24T01:44:50Z

reason for revert: unexpected framework ui thread regression, no performance improvement

…o. (#56004)" This reverts commit ec6e28a.

…wo. (#56004)" (#56078) Reverts: #56004 Initiated by: jonahwilliams Reason for reverting: unexpected framework ui thread regression, no performance improvement Original PR Author: jonahwilliams Reviewed By: {flar, chinmaygarde} This change reverts the following previous change: Fixes flutter/flutter#157108 Right now the DL is always growing by a minimum 4096 bytes at a time. On applications with large display lists, this can lead to hundreds of reallocations as the display list is build, as long as each draw op is small. For example, the framework benchmark long picture scrolling draws many lines, each of which is a pretty small op. Update the code so that we grow by doubling, with a minimum increment of ~16K

…57453) flutter/engine@50f6d98...ec6e28a 2024-10-23 jonahwilliams@google.com [display_list] grow display list backing store by power of two. (flutter/engine#56004) 2024-10-23 skia-flutter-autoroll@skia.org Roll Fuchsia Linux SDK from xPbin_33tT-_omeQT... to NxrFCTty8wV4-6Cpl... (flutter/engine#56056) 2024-10-23 skia-flutter-autoroll@skia.org Roll Dart SDK from 20470aaa17be to 2a4b728f6a03 (3 revisions) (flutter/engine#56055) 2024-10-23 robert.ancell@canonical.com Move get_keyboard_state from FlKeyboardViewDelegate to FlKeyboardManager. (flutter/engine#56021) 2024-10-23 robert.ancell@canonical.com Move send_key_event from FlKeyboardViewDelegate to FlKeyboardManager. (flutter/engine#56020) 2024-10-23 bdero@google.com [Flutter GPU] Fix assert failure in createDeviceBufferWithCopy. (flutter/engine#56039) 2024-10-22 skia-flutter-autoroll@skia.org Roll Dart SDK from 8de85635d731 to 20470aaa17be (4 revisions) (flutter/engine#56038) 2024-10-22 ditman@gmail.com [web] Remove old futureToPromise. (flutter/engine#55847) 2024-10-22 737941+loic-sharma@users.noreply.github.com [dart:ui] Improve Clip's docs (flutter/engine#55978) 2024-10-22 jonahwilliams@google.com [Impeller] flush thread local resources during toImage/toImageSync. (flutter/engine#56037) 2024-10-22 kpsroka@users.noreply.github.com [canvaskit] Makes access to CkSurface null-safer (flutter/engine#54895) Also rolling transitive DEPS: fuchsia/sdk/core/linux-amd64 from xPbin_33tT-_ to NxrFCTty8wV4 If this roll has caused a breakage, revert this CL and stop the roller using the controls here: https://autoroll.skia.org/r/flutter-engine-flutter-autoroll Please CC codefu@google.com,zra@google.com on the revert to ensure that a human is aware of the problem. To file a bug in Flutter: https://github.com/flutter/flutter/issues/new/choose To report a problem with the AutoRoller itself, please file a bug: https://issues.skia.org/issues/new?component=1389291&template=1850622 Documentation for the AutoRoller is here: https://skia.googlesource.com/buildbot/+doc/main/autoroll/README.md

…ter/engine#56004) Fixes flutter#157108 Right now the DL is always growing by a minimum 4096 bytes at a time. On applications with large display lists, this can lead to hundreds of reallocations as the display list is build, as long as each draw op is small. For example, the framework benchmark long picture scrolling draws many lines, each of which is a pretty small op. Update the code so that we grow by doubling, with a minimum increment of ~16K

…wo. (flutter#56004)" (flutter/engine#56078) Reverts: flutter/engine#56004 Initiated by: jonahwilliams Reason for reverting: unexpected framework ui thread regression, no performance improvement Original PR Author: jonahwilliams Reviewed By: {flar, chinmaygarde} This change reverts the following previous change: Fixes flutter#157108 Right now the DL is always growing by a minimum 4096 bytes at a time. On applications with large display lists, this can lead to hundreds of reallocations as the display list is build, as long as each draw op is small. For example, the framework benchmark long picture scrolling draws many lines, each of which is a pretty small op. Update the code so that we grow by doubling, with a minimum increment of ~16K

jonahwilliams added 2 commits October 21, 2024 15:58

[display_list] grow display list backing allocation by doubling up to…

70736e1

… limit

[display_list] grow by powers of 2.

3f9d30b

testing.

404bc7b

chinmaygarde approved these changes Oct 22, 2024

View reviewed changes

jonahwilliams requested a review from flar October 22, 2024 15:05

++

dd30ed3

flar suggested changes Oct 22, 2024

View reviewed changes

add allocating tests and check overflow.

213182f

jonahwilliams changed the title ~~[display_list] grow display list backing store by power of two up to ~1MB.~~ [display_list] grow display list backing store by power of two. Oct 22, 2024

flar approved these changes Oct 23, 2024

View reviewed changes

jonahwilliams added 2 commits October 23, 2024 08:12

fix test case, remove mystery check.

f824776

Merge branch 'main' into fix_page_herustics

7f96e69

jonahwilliams added the autosubmit Merge PR when tree becomes green via auto submit App label Oct 23, 2024

auto-submit bot merged commit ec6e28a into flutter:main Oct 23, 2024

engine-flutter-autoroll mentioned this pull request Oct 23, 2024

Roll Flutter Engine from 50f6d98cb8be to ec6e28ac8b49 (11 revisions) flutter/flutter#157453

Merged

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

ec6e28a [display_list] grow display list backing store by power of tw…

ff965af

…o. (flutter/engine#56004)

jonahwilliams added the revert Label used to revert changes in a closed and merged pull request. label Oct 24, 2024

auto-submit bot pushed a commit that referenced this pull request Oct 24, 2024

Revert "[display_list] grow display list backing store by power of tw…

e0cf4f9

…o. (#56004)" This reverts commit ec6e28a.

auto-submit bot mentioned this pull request Oct 24, 2024

Reverts "[display_list] grow display list backing store by power of two. (#56004)" #56078

Merged

auto-submit bot removed the revert Label used to revert changes in a closed and merged pull request. label Oct 24, 2024

[display_list] grow display list backing store by power of two. #56004

[display_list] grow display list backing store by power of two. #56004

Uh oh!

Conversation

jonahwilliams commented Oct 21, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

flutter-dashboard bot commented Oct 21, 2024

Uh oh!

chinmaygarde left a comment

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!

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!

flar left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

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!

jonahwilliams commented Oct 22, 2024

Uh oh!

flar commented Oct 22, 2024

Uh oh!

jonahwilliams commented Oct 22, 2024

Uh oh!

flar left a comment

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!

jonahwilliams commented Oct 23, 2024

Uh oh!

jonahwilliams commented Oct 24, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

jonahwilliams commented Oct 21, 2024 •

edited

Loading

flar left a comment •

edited

Loading