Sdk: Improve performance of allocating a List with a known length with null safety

[jonahwilliams]

A common pattern when allocating a large list where the length is known ahead of time is to use the default List constructor. This avoids needing to repeatedly grow the internal buffer, though there might have been other optimizations that applied too.

var result = List<int>(1000);
for (var i = 0; i < 1000; i++) {
  result[i] = i;
}

In a null-safe world, this API has been removed since it required filling the list with nulls . There are several alternative APIs that could be used.

1. List.add

var result = <int>[];
for (var i = 0; i < 1000; i++) {
  result.add(i);
}

1. Collection for

var result = <int>[
  for (var i = 0; i < 1000; i++) i
];

1. List.generate

int fill(int x) => x;
var result = List<int>.generate(1000, fill);

Preallocating the list is between 2 - 4x faster than any of these alternative methods unfortunately. This _feels_ bad because it will only impact users that already needed to look for performance. Whether or not that performance is needed is hard to say, but it would be nice to have a good replacement for this optimization.

Looking at the kernel output for the Collection for, it essentially de-sugars into repeated calls to List.add:

  static method generateWithElement() → core::List<core::int*>* {
    return block {
      final core::List<core::int*>* #t1446 = <core::int*>[];
      for (core::int* i = 0; i.{core::num::<}(1000); i = i.{core::num::+}(1))
        [@vm.call-site-attributes.metadata=receiverType:InterfaceType(List<int*>*)] #t1446.{core::List::add}(i);
    } =>#t1446;
  }

And while List.generate) does preallocate the right size, it also requires a closure and seems to be running marginally slower than List.add in AOT

It seems like the easiest way (though I really have no idea) to get some performance back here would be to set an initial capacity in the collection for, if a some minimal length is known. This could apply if a collection for is used with a loop or List with no nested collection ifs.

The performance measurement was done with this benchmark running a flutter release build on android-arm64. Note: its not a very good benchmark, the best way to work around that is to comment out all but one of the methods for testing.

FYI @leafpetersen @yjbanov

[MichaelFenwick]

I'm curious if List.filled() happens to be any better than List.generate in this regard. The core/lib code for List shows it as an external factory, rather than for-loop containing function that List.generate() is, so that might be enough difference to return the performance you're wanting?

[jonahwilliams]

I did not measure List.filled since it does not work for types without a meaningful zero value, nor does it allow the values themselves to vary.

If you click on the link above for List.generate and scroll up, you can see the implementation of List.filled. this works by preallocating the list length and then filling in each element, the sane way you would write pre null-safety

[mraleph]

I think we should force inlining of List.generate(n, () => ...) and the closure invocation itself - the only problem would be potential impact on the code size. Though closure allocation should disappear (and with it the closure metadata and body) so maybe it will be okay.

I think we should tweak inlining heuristics in general to force inlining of local closures with a single call site.

@alexmarkov Alex would you like to look at this, given that you dealt with other NNDB related performance issues?

@sstrickl FYI (related to inlining heuristics).

[mraleph]

We can separately look at optimizing collection-for syntax to preallocate resulting array of the right size - should not be that hard to do that even on already desugared code, e.g.

var list = [];
for (var i = 0; i < n; i++) {
  list.add(i);
}

If we know that list does not escape in the loop and we know the loop boundary then we can preallocate list to have capacity of n.

[leafpetersen]

cc @a-siva

[alexmarkov]

After https://dart-review.googlesource.com/c/sdk/+/151082 and https://dart-review.googlesource.com/c/sdk/+/151466 the code

  var result = List<int>.generate(1000, (int x) => x, growable: false);

is now on par with

  var result = List<int>(1000);
  for (var i = 0; i < 1000; i++) {
    result[i] = i;
  }