A flutter-tools profile screenshot from 3.13.9:

@gaaclarke really interesting PR, somehow seems related to some small changes you do that radically improve things.

WARNING: This is a somewhat breaking change (as shown by the test-change)

I am a little careful of changing the behavior here. This is used in lots and lots of places. It looks like the change is not failing any customer tests, which is a good start. I'll see if I can run google's internal tests on this to see if we can get a better understanding of how breaking this would be.

I also did a performance comparison based on N to support the proposal

I scrolled through the data and I can't see a clear pattern. It seems to be a wash, sometimes the new implementation is faster, sometimes its slower. I am actually not sure whether this is a clear win?

WARNING: This is a somewhat breaking change (as shown by the test-change)

I am a little careful of changing the behavior here. This is used in lots and lots of places. It looks like the change is not failing any customer tests, which is a good start. I'll see if I can run google's internal tests on this to see if we can get a better understanding of how breaking this would be.

Appreciated. I agree that we need to respect Hyrum's law here.

That said, the implemented semantics seem rather ad-hoc. For multiple registrations it is virtually impossible to emply the semantics correctly especially when listeners mutate the list of listeners. I'm also not convinced that the updated semantics are great either. I'd say they're about as bad.

Personally, I'd argue that multiple registrations should be rejected (at least for the animations use-case). For a listener its trivial to run code N times w/o having to register itself N-times. However, this discussion probably goes beyond the scope of this PR.

I also did a performance comparison based on N to support the proposal

I scrolled through the data and I can't see a clear pattern. It seems to be a wash, sometimes the new implementation is faster, sometimes its slower. I am actually not sure whether this is a clear win?

Yes and no but really yes :). It's a bit hard to see given the various dimensions and quite a bit of trial-by-trial variation (I'm going to blame GC and my notebook's thermals :) ). Note that when the new cases are flagged as slower, it's only a very small percentage. In most cases it's just the same +/- noise, I merely picked a conservative threshold for labeling as SLOWER vs SAME. In these cases looking at the absolute runtime can also provide a sense of how noisy the measure may be. I did share the benchmark code, so you can simply run it yourself (the script has zero deps).

Let me try to break it down:

There are 3 comparisons:

1. ObserverList before and after
2. HasedObserverList before and after
3. Improved HasedObserverList against original ObserverList (as a before and after of the second commit)

Then we have two more dimensions:

A. N number of elements. It's worth pointing out that ObserverList as implemented behaves entirely differently for N <3 and N >= 3 elements (Otherwise I would have reduced the number of data points)
B. different test cases.

1. & 2.

The changes covered by 1. and 2. are strict improvements. They don't change any semantics and thus I pulled them out into a separate commit. They should be fairly straightforward. the overriden toList() is a noticeable improvement in the general case over falling back to the Iterator.toList's default implementation. In practice, this reduces the number of memory allocations.

Note that toList() is used within notifyListeners() to make a copy of he list (to account for listeners which may mutate the list of listeners), so you'll hit the code path on every frame independent of your access patterns.

The change to ObserverList.remove is very subtle and only makes a difference if you try to delete non-registered listeners. My benchmarks don't even test for that and it's highly arguable how much of a real-life impact this would have (it certainly would if you constantly try to remove non-registered listeners). Yet, it just makes sense to not unnecessarily invalidate the internal hash set when not needed.

I pulled the "toList()" case out into a separate benchmark to make this clearer:

10 toList()                      FASTER HashedObserverList vs MyHashedObserverList     takes:      2.0x, saved:       50%   (0:00:20.598112 vs 0:00:10.332040)
1000 toList()                    FASTER HashedObserverList vs MyHashedObserverList     takes:      1.4x, saved:       28%   (0:00:01.271092 vs 0:00:00.912649)

(With N=1000 probably a lot more noisy than N=10, due to it's significantly shorter runtime. I only wanted to spend so much time tweaking the iteration numbers for every combo)

3.

"3." covers the changes within the second commit, i.e. moving from ObserverList ot HashedObserver list for animations. This is where the real meat is, i.e. 100+x improvements depending on the number of listeners. At the end of the day it's just array vs hash map. No magic involved.

My assumption is that whoever did the current implementation assumed that AnimationControllers will only drive a small, static set of animations. In these cases, sure the array is slighly faster. In the general case: "a changing, not necessarily small set of Animations", the array is atrocious.

You can see that the ObserverList implementation tries to compensate for it managing a separate, potentially stale, hash set.... Unfortunately, it doesn't help for:

• Removals, you still need to traverse the entire list and move elements
• For mutating listeners it kills the performance on every frame. When the hash set gets invalidated and notifyListeners may rebuild the hash set many times per frame. It's horrendous.

(Outside the scope of this change but the attempted band aid on ObserverList is dangerous. For certain access patterns it may help. For others it completely destroys performance. It's important to note that the access pattern for AnimationController and many other cases is entirely user-defined and the punishment is completely opaque to users. It would be a lot faster, but more importantly safer, to switch to HashedObserList for any case where the number of elements and access patterns are user-controlled).

That's where you get numbers like:

1000 add/remove                  FASTER ObserverList vs MyHashedObserverList           takes:     74.3x, saved:       99%   (0:00:45.577018 vs 0:00:00.613640)

1000 notifyListeners self-mod    FASTER ObserverList vs MyHashedObserverList           takes:    357.4x, saved:      100%   (0:01:06.012280 vs 0:00:00.184690)

Generally, I don't think we should get too hung up on the performance differences for small N that are well within the margin of error. At the end of the day, we'd be discussing 10us vs 10.5us on an already cheap operation, when in reality we're seeing 10us vs 3ms in the N=1000 case.

As a personal data point, my specific use-case that surfaced this issue has hundreds of animations popping on and off screen. These gains are not theoretical for me. At this point, I'm actually shipping a forked version of flutter incorporating these changes, which significantly reduces frame-drops for me

This pull request executed golden file tests, but it has not been updated in a while (20+ days). Test results from Gold expire after as many days, so this pull request will need to be updated with a fresh commit in order to get results from Gold.

For more guidance, visit Writing a golden file test for package:flutter.

Reviewers: Read the Tree Hygiene page and make sure this patch meets those guidelines before LGTMing.

Regarding 1 (Changes to ObservableList.remove): In practice, this sounds like regression to me. I would expect that the case where you remove a non-existent listener is very, very rare (I would almost consider it a bug in the code if somebody does that). So, optimizing for that is odd to me - since you will pay for the "optimization" in the far more common case with an additional check.

Regarding 2 (Optimizing HashedObserverList.toList): This does seem like a nice improvement and the benchmarks appear to back that up. We could probably land just this change without much trouble.

Regarding 3 (Changing AnimationLocalListenersMixin): This is actually less risky than I initially thought since it only affects this one mixin. For some reason I initially thought this would effect all ChangeNotifiers. We still need to run this change through our google testing suite to see if this would be a breaking change.

I was finally able to kick off a test run within google, let's see what it reports back. I'll keep you posted.

Also, can you please resolve the issues reported by the analyze check? Thanks!

Regarding 1 (Changes to ObservableList.remove): In practice, this sounds like regression to me. I would expect that the case where you remove a non-existent listener is very, very rare (I would almost consider it a bug in the code if somebody does that). So, optimizing for that is odd to me - since you will pay for the "optimization" in the far more common case with an additional check.

Maybe all use-cases are buggy (in which case, we should probably surface it, e.g. assert or at least log), maybe there are some valid edge cases 🤷‍♀️ . I'm not sure that ignoring it is the best way to deal with it in either case.

Meanwhile, it's the typical insurance-risk-severity evaluation: the check is basically free and the cost independent of the size, whereas invalidating the internal optimization is non-obvious to users and very costly especially for larger sets. In terms of cost, given any modern CPU with speculative execution and accurate branch prediction, I would expect this check to take <1ns :handwave:.

Personally, I can very much live w/o this "optimization", I'm merely surprised by your cost argument in the light of the benchmark results. I could certainly buy in your bug argument, however one should probably look into how to surface such bugs (independent of this change). As I was rambling earlier, I think there are other semantics that might be unintentional like FIFO (rather than LIFO) removals of duplicate listeners. Maybe duplicate listeners in general should be considered a bug? 🤷‍♀️ There would be nice benefits to it too, e.g. one could use cheaper data structure that don't need to keep track of insertion order.

Regarding 2 (Optimizing HashedObserverList.toList): This does seem like a nice improvement and the benchmarks appear to back that up. We could probably land just this change without much trouble.

Agreed, it shouldn't cause any surprises.

Regarding 3 (Changing AnimationLocalListenersMixin): This is actually less risky than I initially thought since it only affects this one mixin. For some reason I initially thought this would effect all ChangeNotifiers. We still need to run this change through our google testing suite to see if this would be a breaking change.

Thanks! Independently, it could be interesting to evaluate if other constructs would also benefit from other data structures but ultimately it will always depend on your use case.

Also, can you please resolve the issues reported by the analyze check? Thanks!

Once I get word from you on how we will or won't proceed, I'll urgently address any issues.

Thanks!

This is not causing any issues internally at google. I think we should be able to land this if the reported analyzer issues get resolved.

This is not causing any issues internally at google. I think we should be able to land this if the reported analyzer issues get resolved.

Happy to hear. Thanks!

This PR is still failing the analyzer check. Can you please take a look? Thanks.

/b/s/w/ir/x/w/flutter/packages/flutter/lib/src/animation/listener_helpers.dart:94: trailing U+0020 space character
you have a space (" ") at somewhere where it shouldn't be.

Thanks. Analyzer seems to pass now and I rebased against latest main

could you add a benchmark for this? It also would be nice to see the performance improvements this PR introduces.

I like the idea. Even more so for continuous performance monitoring. It's probably less likely that someone would stumble upon a benchmark and than decides to just implement their own AnimationListener.

I couldn't find any other micro-benchmarks in this repo. That's also why I hadn't added mine. I did share them above: https://gist.github.com/ignatz/dba6293d0fef41e3c6e1ed3c51364de6.

I had hoped that this change would be validated by existing e2e benchmarks but if you feel adding micro-benchmarks makes sense we can talk about it. That said, I understand that you folks are busy, and therefore I'd like to avoid expanding this simple change further. It has already been more than an OKR cycle.

If you're looking for microbenchmarks: https://github.com/flutter/flutter/tree/master/dev/benchmarks/microbenchmarks

Added a microbenchmark following the example of dev/benchmarks/microbenchmarks/lib/foundation/change_notifier_bench.dart.

Could you also provide me a link to a dashboard where I can see/monitor the continuous evolution of them microbenchmarks? A Google search didn't bring anything up and I'm wondering how this setup is being put to use.

I've spent countless hours complying with any remotely reasonable request. I've provided extensive benchmarks from the get go. We all know and acknowledge that his is a small change with significant performance impact.

Best practice is to pull the benchmark (and its registration) out into a separate PR, submit that first, and then a day later submit this change to make sure the benchmark works properly and this change has the desired effect.

This sounds more like an opinion than a best practice. I'm always down for a good argument, just not big on process for the sake of process. AFAICT, there's nothing to be gained from this proposal unless you believe the CI server must execute the benchmarks to be trusted.

If you think I should spend a few more weeks on back and forts with moving goal posts: fine. I you don't have the bandwidth to spend 1minute on a cherry-pick: fine. If you don't want to improve Flutter's performance: fine. If you're ok with the opportunity cost for your users: fine. If you're comfortable with disrespecting your contributors' time: fine.

If you change your mind: also fine. Otherwise thank you for you time and good luck!

And just for the record

Sadly, we currently don't have resources to take over this PR. If you could split this into two, we can land it, though.

could be misconstrued as gaslighting.

I am sorry if you misinterpreted my statement. That wasn't my intention. And there is no disrespecting anyones time. Getting any change landed sometimes requires a couple of feedback cycles and back-and-forth discussions before they are ready to land. That's just part of open-source team work.

We do appreciate your contribution, but we also expect contributors to get changes over the line and not just "throw them over the fence" to have someone else finish them when they are done with the fun bits.

I still hope that we can land this with your help.

I am sorry if you misinterpreted my statement. That wasn't my intention. And there is no disrespecting anyones time. Getting any change landed sometimes requires a couple of feedback cycles and back-and-forth discussions before they are ready to land. That's just part of open-source team work.

We do appreciate your contribution, but we also expect contributors to get changes over the line and not just "throw them over the fence" to have someone else finish them when they are done with the fun bits.

I'm not sure how to read this. Are you talking generally? Are you talking about the same PR? Maybe some context faded over time? Are you insinuating?

Personally, I didn't think that addressing every request, answering everybquestion, writing and running benchmarks for hours were the fun bits. I'm sorry you feel like I'm just throwing code over the fence.

In any case thanks for explaining team work to me. I wish you had given me a rational instead 🤷‍♀️

I still hope that we can land this with your help.

I'm still not sure what stands to be gained from the extra work but it sure seems important to you.

Good luck and thank you for your time

Hey @ignatz, if you allow me, I have pushed the benchmarks to a different PR so your contribution can be landed as part 1 (the benchmark) and part 2 (the improvements).

Hey @bernaferrari. Thanks for jumping in, much appreciated.

I don't know how to remove the benchmark commit and merge this, could you do that? @ignatz else I can reopen the PR without it...

I don't know how to remove the benchmark commit and merge this, could you do that? @ignatz else I can reopen the PR without it...

Of course, done. That's also what I offered before. In case you're curious, can be done with git rebase. There's also git cherry-pick in case you want to selectively pull in a single commit w/o creating an independent one.

To be clear, I'm happy to help with virtually any request I can remotely reason about. I merely don't like spending my time on something that has zero tangible value just because someone, unsure why, called it a "best practice". In general, most engineers will be allergic to corporate processes and authority arguments. Doesn't feel like teamwork, feels at best like someone wanting to check the "demonstrates leadership at the next level" box and triggers my inner Hixie.

I love Flutter ❤️

EDIT: I would also like to explicitly express my gratitude for you, Bernardo. You're clearly caught in the cross fire - sorry - but you also genuinely seem to want to help. Thanks!

Greetings from PR triage, checking in on this, it looks like the benchmark will need to be checked back in before we can land this PR?

For reference, #143799 was reverted in #143946.

Performance improvements like this are difficult to test, and therefore difficult to catch when they regress. The benchmark is intended to establish a baseline before this lands so we know (1) it has made an improvement on that baseline as expected, and then (2) it persists so we will know if it regresses in the future.

Also, reading through the comments here, just wanted to provide a friendly tone check. We should all be working together respectfully, per our code of conduct. 🙂

I'll reland for the third time the benchmarks. It is hard because they are not checked by the CI, so bugs slided two times and I got tired/traumatized of getting things reverted. Then I forgot, but I'll do it again shortly.

I also have no idea why they failed last time. Will see what happens locally.

Thanks @bernaferrari. I appreciate you volunteering your time to help with this change. 🙏

Since this was closed, I filed #146211 to follow up on this.

This (finally) got merged! 🥳