Proposal for improving the performances of ChangeNotifier

[letsar]

Hi 👋

We (@escamoteur, @knaeckeKami, and me, but also with the help of @mraleph and @Kavantix ) found a new implementation for ChangeNotifier which would improve its performances, especially when notifyListeners is called.

We created multiple benchmarks to see how our implementation behaves in multiple conditions.
These benchmarks are available here: https://github.com/knaeckeKami/changenotifier_benchmark

We measured the performances in terms of CPU time, but also the Memory Footprint, for 3 different implementations:

• The Initial implementation, which is the ChangeNotifier implementation before this PR: Use a LinkedList to improve the performances of ChangeNotifier #62330.
• The Current implementation, which is the one available on the flutter master branch as of today.
• The Proposed implementation, which is our implementation.

CPU Time

Our Benchmark

You will find below the results of our main benchmark:

┌───────────────────────────────────────────────────────────────────────────────┐
│                            ValueNotifier benchmark                            │
├─────────────┬─────────────────────┬─────────────────────┬─────────────────────┤
│             │       Initial       │       Current       │      Proposed       │
│  Listeners  ├─────────┬───────────┼─────────┬───────────┼─────────┬───────────┤
│             │ Updates │ Time [µs] │ Updates │ Time [µs] │ Updates │ Time [µs] │
├─────────────┼─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │      10 │         2 │      10 │         1 │      10 │         0 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │     100 │       114 │     100 │         1 │     100 │         1 │
│           1 ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │    1000 │        82 │    1000 │        14 │    1000 │        12 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │   10000 │      1194 │   10000 │       162 │   10000 │       225 │
├─────────────┼─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │      10 │         6 │      10 │         6 │      10 │         1 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │     100 │        26 │     100 │        14 │     100 │         2 │
│           2 ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │    1000 │       266 │    1000 │       146 │    1000 │        22 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │   10000 │      3346 │   10000 │      1459 │   10000 │       255 │
├─────────────┼─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │      10 │        18 │      10 │         3 │      10 │         1 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │     100 │        68 │     100 │        22 │     100 │         3 │
│           4 ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │    1000 │       743 │    1000 │       209 │    1000 │        28 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │   10000 │      7556 │   10000 │      2240 │   10000 │       309 │
├─────────────┼─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │      10 │        22 │      10 │         5 │      10 │         1 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │     100 │       153 │     100 │        37 │     100 │        56 │
│           8 ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │    1000 │      1557 │    1000 │       372 │    1000 │        58 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │   10000 │     15599 │   10000 │      4559 │   10000 │       532 │
├─────────────┼─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │      10 │        81 │      10 │         8 │      10 │         1 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │     100 │       320 │     100 │        68 │     100 │         9 │
│          16 ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │    1000 │      3238 │    1000 │       939 │    1000 │        90 │
│             ├─────────┼───────────┼─────────┼───────────┼─────────┼───────────┤
│             │   10000 │     31379 │   10000 │      8216 │   10000 │      1041 │
├─────────────┼─────────┴───────────┼─────────┴───────────┼─────────┴───────────┤
│ Total Time: │               65770 │               18481 │                2647 │
└─────────────┴─────────────────────┴─────────────────────┴─────────────────────┘

The code of this benchmark is the following, and you can find it here.

Future<int> runBenchmark({
  required ValueNotifierFactory creator,
  required final int updates,
  required final int listeners,
}) {
  final c = Completer<int>();
  final notifier = creator(0);
  final timer = Stopwatch()..start();

  for (var i = 0; i < listeners - 1; i++) {
    notifier.addListener(() {});
  }
  notifier.addListener(() {
    if (updates == notifier.value) {
      timer.stop();
      c.complete(timer.elapsedMicroseconds);
    }
  });

  for (var i = 0; i <= updates; i++) {
    notifier.value = i;
  }
  return c.future;
}

This benchmark has been run on my OnePlus 8 Pro (with Android 11) with the following command:

flutter run --release lib/benchmark.dart

As you can see, the Proposed implementation seems to be much faster than the previous ones.

Flutter microbenchmark

We also ran the flutter microbenchmark, for ChangeNotifier, available here in which we made some modifications to be able to test our 3 implementations, with 100,000 iterations for each one.

We normalized the results to see how much other implementations are slower than the fastest (the implementation with a score of 1).

Here are our results:

As you can see, the Proposed implementation is the fastest for almost all iterations in this benchmark as well.

Memory Footprint

We also wanted to compare the memory footprint of these different implementations.

We didn't find an automatic way to measure this so we took an approach based on Heap Snapshots with Dart DevTools.

We created a simple app which will instantiate 1000 notifiers with 1000 listeners for each one of them:

const name = 'Proposed';
const notifierCount = 1000;
const listenerCount = 1000;

main() => runApp(const MyApp());

class MyApp extends StatefulWidget {
  const MyApp({
    Key? key,
  }) : super(key: key);

  @override
  _MyAppState createState() => _MyAppState();
}

class _MyAppState extends State<MyApp> {
  late final List<ValueNotifier<int>> notifiers;

  @override
  void initState() {
    super.initState();
    notifiers = List.generate(notifierCount, (index) {
      final notifier = factories[name]!(0);
      for (var i = 0; i < listenerCount; i++) {
        notifier.addListener(() {});
      }
      return notifier;
    });
  }

  @override
  Widget build(BuildContext context) {
    return const SizedBox();
  }
}

The protocol to measure the memory footprint can be reproduced by following these steps:

1. Set the name constant to the implementation for which you want to measure the memory footprint (Initial, Current or Proposed).
2. Launch the app with this command flutter run --profile lib/main.dart.
3. Copy the Observatory Uri.
4. Launch Dart DevTools and connect it to your app with the Observatory Uri you copied before.
5. Go to the Memory tab.
6. Wait a couple of seconds and click on GC.
7. Wait a couple of seconds and click on Take Heap Snapshot
8. Expand the Snapshot item and copy the Shallow value of External, Filtered, package and src into a spreadsheet
9. Go to 1. and change the name.

We also measure the memory footprint of the same app with 0 notifiers to have a reference.

These are our results:

┌──────────┬─────────────┬─────────┬─────────┬──────────┐
│          │ 0 notifiers │ Initial │ Current │ Proposed │
├──────────┼─────────────┼─────────┼─────────┼──────────┤
│ External │       3.01K │   3.01K │   3.01K │    3.01K │
│ Filtered │       1,99M │   74,3M │    114M │    74,2M │
│ package  │          16 │     32K │      16 │      64K │
│ src      │       4,64M │   4,64M │   4,64M │    4,64M │
│ Total    │       6.63M │  78,98M │ 118,64M │   78,91M │
└──────────┴─────────────┴─────────┴─────────┴──────────┘

We can see that Initial and Proposed implementations have about the same memory footprint, but the Current implementation's footprint is higher.

By removing the total memory footprint of the 0 notifiers iteration, we can compute that the Proposed implementation consumes 1.55 times less than the Current one.

We also think that this proposed implementation allocates fewer temporary objects because it doesn't create a new list for each call to notifyListener.

Proposed implementation

You will find below the proposed implementation which lays on a custom growable list:

class ProposedChangeNotifier implements Listenable {
  int _length = 0;
  List<VoidCallback?>? _listeners = List<VoidCallback?>.filled(0, null);
  int _notificationCallStackDepth = 0;
  int _removedListeners = 0;

  bool _debugAssertNotDisposed() {
    assert(() {
      if (_listeners == null) {
        throw FlutterError('A $runtimeType was used after being disposed.\n'
            'Once you have called dispose() on a $runtimeType, it can no longer be used.');
      }
      return true;
    }());
    return true;
  }

  bool get hasListeners {
    assert(_debugAssertNotDisposed());
    return _length > 0;
  }

  void addListener(VoidCallback listener) {
    assert(_debugAssertNotDisposed());

    if (_length == _listeners!.length) {
      if (_length == 0) {
        _listeners = List<VoidCallback?>.filled(1, null);
      } else {
        final newListeners =
            List<VoidCallback?>.filled(_listeners!.length * 2, null);
        for (int i = 0; i < _length; i++) {
          newListeners[i] = _listeners![i];
        }
        _listeners = newListeners;
      }
    }
    _listeners![_length++] = listener;
  }

  void _removeAt(int index) {
    for (int i = index; i < _length - 1; i++) {
      _listeners![i] = _listeners![i + 1];
    }
    _length--;
  }

  void removeListener(VoidCallback listener) {
    assert(_debugAssertNotDisposed());

    for (int i = 0; i < _length; i++) {
      final _listener = _listeners![i];
      if (_listener == listener) {
        if (_notificationCallStackDepth > 0) {
          _listeners![i] = null;
          _removedListeners++;
        } else {
          _removeAt(i);
        }
        break;
      }
    }
  }

  void dispose() {
    assert(_debugAssertNotDisposed());
    _listeners = null;
  }

  void notifyListeners() {
    assert(_debugAssertNotDisposed());

    if (_length == 0) {
      return;
    }
    _notificationCallStackDepth++;

    final int end = _length;
    for (int i = 0; i < end; i++) {
      try {
        _listeners![i]?.call();
      } catch (exception, stack) {
        FlutterError.reportError(FlutterErrorDetails(
          exception: exception,
          stack: stack,
          library: 'foundation library',
          context: ErrorDescription(
              'while dispatching notifications for $runtimeType'),
          informationCollector: () sync* {
            yield DiagnosticsProperty<ProposedChangeNotifier>(
              'The $runtimeType sending notification was',
              this,
              style: DiagnosticsTreeStyle.errorProperty,
            );
          },
        ));
      }
    }

    _notificationCallStackDepth--;

    if (_notificationCallStackDepth == 0 && _removedListeners > 0) {
      // We really remove the listeners when all notifications are done.
      final newLength = _length - _removedListeners;
      final newListeners = List<VoidCallback?>.filled(newLength, null);

      int newIndex = 0;
      for (int i = 0; i < _length; i++) {
        final listener = _listeners![i];
        if (listener != null) {
          newListeners[newIndex++] = listener;
        }
      }

      _removedListeners = 0;
      _length = newLength;
      _listeners = newListeners;
    }
  }
}

This implementation passes all current tests.

The main drawback of this implementation can be the source code which is more complicated than the previous ones.

But the benchmark results show a lot of benefits and we think that it could be a good opportunity to change the current implementation to this one.

If you think that's a good idea, we can do a PR ourselves and also add some tests to ChangeNotifier.

[goderbauer]

Those numbers look impressive. I guess, adding listeners is the only place where the proposal doesn't outshine the other implementations?

Is it an oversight that the list only shrinks if a listener is removed during notifyListeners and never when it is removed outside of that?

/cc @Hixie @dnfield

[letsar]

For adding listeners we saw something different in our benchmark:

┌─────────────────────────────────────────────────┐
│              addListener benchmark              │
├─────────────┬───────────┬───────────┬───────────┤
│             │  Initial  │  Current  │ Proposed  │
│  Listeners  ├───────────┼───────────┼───────────┤
│             │ Time [µs] │ Time [µs] │ Time [µs] │
├─────────────┼───────────┼───────────┼───────────┤
│           1 │         0 │         0 │         0 │
├─────────────┼───────────┼───────────┼───────────┤
│           2 │         0 │         0 │         1 │
├─────────────┼───────────┼───────────┼───────────┤
│           4 │         0 │         8 │         0 │
├─────────────┼───────────┼───────────┼───────────┤
│           8 │         0 │         8 │         0 │
├─────────────┼───────────┼───────────┼───────────┤
│          16 │         0 │         3 │         0 │
├─────────────┼───────────┼───────────┼───────────┤
│ Total Time: │         0 │        19 │         1 │
└─────────────┴───────────┴───────────┴───────────┘

I don't really know why there is so much difference between our benchmark and the official one for now, but I can look into it.

Yes, good point about the removing of listeners. If an app creates a lot of listeners it could look like a memory leak.
Maybe we should shrink it as well when the _length is half the size of the list. @escamoteur , @mraleph , @knaeckeKami, what do you think?

[knaeckeKami]

True, we didn't think of that. I hope this does not cost of much of our gains.
Maybe something like:

void removeAt(int index){
  
  _length--;
  if(_length *2 < _listeners!.length){
    final newListeners  = List.filled(_length, null);
    newListeners.replaceRange(0, index -1, _listeners! );
    newListeners.replaceRange(index, _length -1, _listeners!.skip(index) );
    _listeners = newListeners;
    
  }else{
     for (int i = index; i < _length; i++) {
      _listeners![i] = _listeners![i + 1];
    }
  }
  
}

(did not actually check if that works, probably there are off-by-one errors, just an idea). It might also be faster just to use two for loops instead of replaceRange.

[dnfield]

I wonder if you'd get some better performance out of making _listeners non-nullable and having a separate bool flag for disposal, and just calling clear on the list in disposal - it would avoid the need for a null check everytime the list is accessed. Probably pretty small though.

I think at some point you would need to shrink the list if it grew too big, but I'd expect that not to happen too much in a real usage - these are really designed to have a relatively small number of listeners, though listeners may be added and removed over time, I would not expect the actual list size to grow much beyond say 16, which shouldn't normally be a problem.

I'd suggest adding the benchmark to our microbenchmarks suite as a starting point. But this seems like a reasonable approach to me overall.

[dnfield]

It'd also be interesting to see if it has any impact on, e.g., the transitions perf benchmarks for gallery/new gallery.

[escamoteur]

@letsar @knaeckeKami we already use the removeAt() function if not during a notify. So I don't see the problem with removeListener but maybe I'm just overlooking something. what could be that if our List grew before and then a lot of listeneres where removed the array could still be too big, so we could add a check in removeAt and allocate a smaller List again.

@dnfield If we want to use a ´bool´ flag we can't store the handler at the same place so we would need an aditional node object, which was how my first implementation lookked like. @mraleph then recommended using only the list without addional objects which indeed was faster, so I don't expect that null safe with objects is any faster.

[letsar]

@escamoteur the removeAt actually never shrinks the list, it only shift things so that all null are at the end of the list. But yes, we have to make sure that in the case a lot of listeners had been added, we shrink the list when it makes sense.
I add some code to do it and update the benchmarks to see where we go.

For the bool flag, I think there is a misunderstanding. It would be only for making the list not nullable. I did something like that in a previous version but I can compare the two approaches.

[knaeckeKami]

I think @dnfield meant that instead of

  List<VoidCallback?>? _listeners = List<VoidCallback?>.filled(0, null);

we use

  List<VoidCallback?> _listeners = List<VoidCallback?>.filled(0, null);
  bool _isDisposed = false; 

and change dispose() to

void dispose() {
    assert(_debugAssertNotDisposed());
    _listeners.clear();
    _isDisposed = true;
  }

and also change _debugAssertNotDisposed() accordingly and change all the !. accesses to . accesses.