Do not eagerly allocate inherited widget caches when initializing element tree by jonahwilliams · Pull Request #95596 · flutter/flutter

jonahwilliams · 2021-12-20T20:18:46Z

Currently, creating an inherited element causes it to allocate a hashmap containing itself and all parent elements, by copying the parent inherited element cache. This has roughly quadradic complexity with respect to the number of inherited elements in the widget tree, and quadradic space for the hashmap allocations. The purpose of this cache is to ensure that the of pattern and similar remain as fast as possible, since widgets frequently look up many inherited widgets in their build methods.

However, I believe that most of these caches are ending up unused, and hence we are wasting space/cpu time allocating that space. Suppose you have a handful of inherited elements at the top level of your widget tree (Directionality, Localizations, State management something). The only inherited element cache that will be used is the "last" one, and all of the others are wasted.

We should be able to improve the performance by making this inherited element cache lazy. Instead of eagerly copying the map, each element will store a parent pointer and cache the inherited element at the lowest level inherited element the first time a type is requested. This should have roughly the same complexity, but much closer to linear space.

As a bit of a sidecar, I remove the hashCode override on element. As far as I can tell, the goal of this is avoid big ints/mints due to boxing concerns and allocation - but the default hashCode is identity hashCode, which is stored on the object itself and requires no additional allocations. Removing this further improved the benchmark below.

---- Performance Measurements ---

To test this theory I ran a benchmark supplied by @dnfield which repeatedly runs first builds.

On a Pixel 4 without this patch, this ran at 774 ms with a standard deviation of 31 ms. With this patch it ran in 685 ms with a standard deviation of 24ms.

For web builds, the time improved from roughly 2.4 seconds to 2.1 seconds. I did not compute any further stats for this.

import 'dart:ui' as ui show window;
import 'package:flutter/material.dart';

void main() {
  final binding = WidgetsFlutterBinding.ensureInitialized();
  ui.window.onPointerDataPacket = null;

  var root = MediaQuery.fromWindow(
      child: Directionality(
    textDirection: TextDirection.ltr,
    child: Material(
      child: Column(
        children: List<Widget>.generate(9, (index) {
          return ListTile(
              leading: CircleAvatar(child: Text(index.toString())),
              title: Text('Content $index'));
        }),
      ),
    ),
  ));

  var sw = Stopwatch()..start();
  for (var count = 0; count < 1000; count++) {
    var renderViewElement = RenderObjectToWidgetAdapter(container: binding.renderView, child: root)
      .attachToRenderTree(binding.buildOwner!, null);
  }
  sw.stop();
  print(sw.elapsed);
}

…herited

jonahwilliams · 2021-12-20T20:26:12Z

FYI @dnfield / @goderbauer

jonahwilliams · 2021-12-20T20:26:58Z

I bet you could get even better performance by using IdentityHashMaps, which IIRC are just regular JS maps when compiled for that?

goderbauer · 2022-01-04T19:56:57Z

Interesting approach and those numbers do look like a nice improvement.

Do the benchmark numbers in the PR description include the improvements achieved by removing hashCode? Or does that improve the stated numbers even more?

Did you run this by any chance against one of our benchmarks that represents the real world a little better (e.g. the transitions perf benchmark, for example)? Curious to see if this would show up there as well.

jonahwilliams · 2022-01-04T21:53:02Z

It includes hashCode, I could break that out too though.

Did you run this by any chance against one of our benchmarks that represents the real world a little better (e.g. the transitions perf benchmark, for example)? Curious to see if this would show up there as well.

no not yet - do we have the ability to run the devicelab on a PR yet 😅 ? The biggest issue is that my pixel 4 is too fast and I don't have a slower device

goderbauer · 2022-01-04T21:54:11Z

no not yet - do we have the ability to run the devicelab on a PR yet 😅 ?

@CaseyHillers Does that exit? :)

jonahwilliams · 2022-01-04T22:06:54Z

That said I can still try - what is your favorite benchmark? I would expect this would improve worst dart frame times, but not much else

jonahwilliams · 2022-01-04T22:24:21Z

ahh you said transitions perf, will try

…herited

jonahwilliams · 2022-01-06T01:37:33Z

From running the new_gallery transition perf on a pixel 4:

With change: (x3)

"average_frame_build_time_millis": 3.23 / 3.37 / 3.46
"90th_percentile_frame_build_time_millis": 5.222, / 5.8 /5.56
"99th_percentile_frame_build_time_millis": 23.842 / 23.15 / 26.097,
"worst_frame_build_time_millis": 98.947 / 95.621 / 98.716,
"missed_frame_build_budget_count": 41 / 39 / 34,

ToT (x3)

"average_frame_build_time_millis": 3.32 / 3.25 / 3.31
"90th_percentile_frame_build_time_millis": 5.33 / 5.214 / 5.45,
"99th_percentile_frame_build_time_millis": 25.302 / 24.736 / 25.142,
"worst_frame_build_time_millis": 89.851 / 110.829 / 118.102,
"missed_frame_build_budget_count": 44 / 71 / 22,

I would run it more but it takes a while. So the numbers here aren't super clear - the 99th time is sometimes better, though average times aren't much different. I'd also let @dnfield have a go at it to see if it is worth anything on the low end device

CaseyHillers · 2022-01-10T18:29:25Z

no not yet - do we have the ability to run the devicelab on a PR yet sweat_smile ?

@CaseyHillers Does that exit? :)

You can run the hot reload tests if you make changes to dev/. Feel free to update the runIf in ci.yaml if there's other paths that should trigger the on device tests, or update some documentation in dev/.

dnfield · 2022-01-10T23:42:34Z

packages/flutter/lib/src/widgets/framework.dart

+// expensive map allocations until they are needed.
+class _InheritedLookup {
+  _InheritedLookup? parent;
+  final HashMap<Type, InheritedElement> current = HashMap<Type, InheritedElement>();


I kind of wonder if there's some way we can rework this so that there's only a single HashMap per depth of the tree, rather than having every element get one of these. It could live on the build owner and you could basically say "get me the inherited element for my current depth". You'd need to update it when an inherited element gets a new depth.

Does that make sense?

Don't we have fewer hashmaps than per depth of the tree today? since we push down the hashmap created by an inherited element to all non-inherited elements

I think you're right - I was thinking about cases where you might have a multi-child widget that has multiple sibling children that are inherited widgets, but in that case my suggestion doesn't even make sense.

Also, I'm realizing now tht this will completely avoid copying the hash maps and my comment below doesn't make sense either. Sorry!

I'm trying to think if there's some way we can test this.

WDYT of making this class public and just adding some unit tests for it?

That way we could have some tests that are more targetted and won't just break because someone refactors this and just starts getting errors about some weird inherited widget.

Sure, can do!

Hixie · 2022-01-10T23:48:30Z

packages/flutter/lib/src/widgets/framework.dart

+// trees that contain a significant number of inherited widgets by deferring
+// expensive map allocations until they are needed.
+class _InheritedLookup {
+  _InheritedLookup? parent;


Can parent change? it's marked mutable here but there's no effort to invalidate the cache when it changes.

I don't see any code that changes it after the initial creation, which suggests maybe it should be final and set in the constructor?

Hixie · 2022-01-10T23:49:58Z

This looks great!

Given the sensitivity of these changes, it might make sense to separate out the sidecar into its own PR so that it gets validated against all the benchmarks independently.

…herited

jonahwilliams · 2022-01-14T05:42:29Z

Removed hashcode change, will split that out elsewhere

dnfield · 2022-01-14T17:40:46Z

The VM has a new fast path for copying LinkedHashMap (https://dart-review.googlesource.com/c/sdk/+/222249). That hasn't rolled into the framework yet, but once it does we might get more benefit from changing all the HashMap instances to Map.

dnfield · 2022-01-14T17:41:19Z

When It ried ot test that patch locally I still saw profiling get hung up in list copies, but it's possible the VM can further optimize those as well...

jonahwilliams · 2022-01-14T18:16:35Z

quadadic space is quadradic space

jonahwilliams · 2022-01-14T18:17:19Z

but actually, we could improve web pretty dramatically with LinkedHashMap since it is possible to get an es6 map out of it. Follow up patch

dnfield · 2022-01-14T19:06:57Z

I don't mean instead of this patch, I mean in addition :)

jonahwilliams · 2022-01-14T21:29:28Z

With hashCode removed, the benchmark runs in 725ms instead of 685 ms. still an improvement, but a smaller one

flutter-dashboard · 2022-01-14T21:29:33Z

It looks like this pull request may not have tests. Please make sure to add tests before merging. If you need an exemption to this rule, contact Hixie on the #hackers channel in Chat.

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.

jonahwilliams · 2022-01-14T21:37:21Z

hashcode change is #96644

dnfield

Lgtm

fluttergithubbot · 2022-01-15T21:35:22Z

This pull request is not suitable for automatic merging in its current state.

The status or check suite Linux web_long_running_tests_3_5 has failed. Please fix the issues identified (or deflake) before re-applying this label.

…zing element tree (flutter/flutter#95596)

…ment tree (flutter#95596)

…zing element tree (#95596)" This reverts commit ba2f2c6.

gaaclarke · 2022-04-27T18:11:46Z

packages/flutter/lib/src/widgets/framework.dart

+    _inheritedLookup = InheritedTreeCache(_parent?._inheritedLookup)
+      ..[widget.runtimeType] = this;


Nit: In case we try this again, every time you make an InheritedTreeCache you add an item. We might as well do that as part of the constructor instead of calling 2 methods.

jonahwilliams added 3 commits December 18, 2021 12:08

Remove quadradic inherited element behavior

d9ad1fd

remove hash collisions

44dfb8b

Merge branch 'master' of github.com:flutter/flutter into lazy_init_in…

0ae3af6

…herited

flutter-dashboard bot added the framework flutter/packages/flutter repository. See also f: labels. label Dec 20, 2021

Merge branch 'master' of github.com:flutter/flutter into lazy_init_in…

ef6bc59

…herited

dnfield reviewed Jan 10, 2022

View reviewed changes

Hixie reviewed Jan 10, 2022

View reviewed changes

jonahwilliams added 2 commits January 13, 2022 21:39

Merge branch 'master' of github.com:flutter/flutter into lazy_init_in…

7128591

…herited

remove hashcode change, make parent final

51e9729

jonahwilliams marked this pull request as ready for review January 14, 2022 21:29

jonahwilliams requested review from Hixie and dnfield January 14, 2022 21:29

jonahwilliams changed the title ~~[WIP] Do not eagerly allocate inherited widget caches when initializing element tree~~ Do not eagerly allocate inherited widget caches when initializing element tree Jan 14, 2022

Add unit tests and rename

6df089c

dnfield approved these changes Jan 15, 2022

View reviewed changes

dnfield added the waiting for tree to go green label Jan 15, 2022

fluttergithubbot removed the waiting for tree to go green label Jan 15, 2022

dnfield added the waiting for tree to go green label Jan 15, 2022

fluttergithubbot merged commit ba2f2c6 into flutter:master Jan 18, 2022

engine-flutter-autoroll mentioned this pull request Jan 18, 2022

Roll Flutter from 3e6e996f9eff to a2ac0e30fd41 (82 revisions) flutter/plugins#4680

Closed

engine-flutter-autoroll added a commit to engine-flutter-autoroll/plugins that referenced this pull request Jan 18, 2022

ba2f2c6 Do not eagerly allocate inherited widget caches when initiali…

be4565b

…zing element tree (flutter/flutter#95596)

jonahwilliams deleted the lazy_init_inherited branch January 18, 2022 19:09

jonahwilliams mentioned this pull request Jan 20, 2022

[framework] dont allocate forgotten children set in profile/release mode #94911

Merged

engine-flutter-autoroll added a commit to engine-flutter-autoroll/plugins that referenced this pull request Feb 4, 2022

ba2f2c6 Do not eagerly allocate inherited widget caches when initiali…

4cae932

…zing element tree (flutter/flutter#95596)

jonahwilliams mentioned this pull request Feb 4, 2022

[framework] inline casts on Element.widget getter to improve web performance #97822

Merged

clocksmith pushed a commit to clocksmith/flutter that referenced this pull request Mar 8, 2022

Do not eagerly allocate inherited widget caches when initializing ele…

d50e8bd

…ment tree (flutter#95596)

jonahwilliams pushed a commit that referenced this pull request Mar 15, 2022

Revert "Do not eagerly allocate inherited widget caches when initiali…

d79700a

…zing element tree (#95596)" This reverts commit ba2f2c6.

jonahwilliams mentioned this pull request Mar 15, 2022

Revert "Do not eagerly allocate inherited widget caches when initializing element tree" #100152

Merged

gaaclarke reviewed Apr 27, 2022

View reviewed changes

dnfield mentioned this pull request Apr 29, 2022

Lazily build inherited lookup maps, but then eagerly build them as so… #102832

Closed

		_inheritedLookup = InheritedTreeCache(_parent?._inheritedLookup)
		..[widget.runtimeType] = this;

Conversation

jonahwilliams commented Dec 20, 2021

Uh oh!

jonahwilliams commented Dec 20, 2021

Uh oh!

jonahwilliams commented Dec 20, 2021

Uh oh!

goderbauer commented Jan 4, 2022

Uh oh!

jonahwilliams commented Jan 4, 2022

Uh oh!

goderbauer commented Jan 4, 2022

Uh oh!

jonahwilliams commented Jan 4, 2022

Uh oh!

jonahwilliams commented Jan 4, 2022

Uh oh!

jonahwilliams commented Jan 6, 2022

Uh oh!

CaseyHillers commented Jan 10, 2022

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!

Hixie commented Jan 10, 2022

Uh oh!

jonahwilliams commented Jan 14, 2022

Uh oh!

dnfield commented Jan 14, 2022

Uh oh!

dnfield commented Jan 14, 2022

Uh oh!

jonahwilliams commented Jan 14, 2022

Uh oh!

jonahwilliams commented Jan 14, 2022

Uh oh!

dnfield commented Jan 14, 2022

Uh oh!

jonahwilliams commented Jan 14, 2022

Uh oh!

flutter-dashboard bot commented Jan 14, 2022

Uh oh!

jonahwilliams commented Jan 14, 2022

Uh oh!

dnfield left a comment

Choose a reason for hiding this comment

Uh oh!

fluttergithubbot commented Jan 15, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants