Refactor _List and _ImmutableList to have shared accessors

[dcharkes]

I expected it should not matter if _data was polymorphic for kArrayCid and kImmutableArrayCid because CHA would notice it is the same operator[] target in both cases, but I was surprised on checking that kImmutableArrayCid is not a subclass of kArrayCid and they do not share operator[].

That was my thought - why is there not a shared abstract base class between _List and _ImmutableList? (It could be called _Array)
It would solve some problems like this, and remove a few methods that need to be recognized.

https://dart-review.googlesource.com/c/sdk/+/231243/9..13/sdk/lib/_internal/vm/lib/compact_hash.dart#b676

33e170e sped up key and value iteration by 20% for mutable and 40-50% for immutable maps. It achieved this by duplicating the iterators so that they do not have a polymorphic call inside.

However, it also regressed the where iterator by ~10%.

-- with change
CollectionSieves-where-List.from(RunTime): 9255.718894009216 us.
CollectionSieves-where-List.from(RunTime): 8020.564 us.
CollectionSieves-where-List.from(RunTime): 8434.20588235294 us.
-- change reverted
CollectionSieves-where-List.from(RunTime): 7539.289473684211 us.
CollectionSieves-where-List.from(RunTime): 7251.532608695652 us.
CollectionSieves-where-List.from(RunTime): 7719.107692307693 us.

This is caused by the where iterator now being more polymorphic and refusing to inline now that there's one extra case.

==== dart:_internal_WhereIterator_moveNext (RegularFunction)
...
v5 <- PolymorphicInstanceCall:14( moveNext<0>, v3 Targets[4: ListIterator cid 650 cnt:5634 trgt:'ListIterator.moveNext' | _CompactIterator@3220832 cid 413 cnt:24 trgt:'_CompactIterator@3220832.moveNext' | MappedIterator cid 653 cnt:24 trgt:'MappedIterator.moveNext' | _TypedListIterator@7027147 cid 824 cnt:24 trgt:'_TypedListIterator@7027147.moveNext']) T{bool}

==== dart:_internal_WhereIterator_moveNext (RegularFunction)
...
v5 <- PolymorphicInstanceCall:14( moveNext<0>, v3 Targets[5: ListIterator cid 652 cnt:6168 trgt:'ListIterator.moveNext' | _TypedListIterator@7027147 cid 826 cnt:147 trgt:'_TypedListIterator@7027147.moveNext' | _CompactIterator@3220832 cid 413 cnt:114 trgt:'_CompactIterator@3220832.moveNext' | _CompactIteratorImmutable@3220832 cid 415 cnt:53 trgt:'_CompactIteratorImmutable@3220832.moveNext' | MappedIterator cid 655 cnt:42 trgt:'MappedIterator.moveNext']) T{bool}

Related issues:

• [vm] Map key/value iterable performance #48280
• Incorrect behaviour of keys and values iterables of VM LinkedHashMaps #48282

The common super type in Dart is ListBase:

sdk/lib/collection/list.dart

abstract class ListBase<E> extends Object with ListMixin<E> {
  // ...
}

[dcharkes]

cc @rmacnak-google, @mkustermann mentioned you might want to look at this.

[mkustermann]

/cc @rakudrama Once fixed it should improve the new benchmark.

[rakudrama]

This would definitely be helpful in carefully written code!

I'm glad to see this issue filed, but I think we should go much further, and include _GrowableList in the refactoring.

The most important List iteration benchmark for most users is Iterators.mono.List.int.growable.and.const.{1,100}.
User-level code often flows const [] and a growable list to the same place.

[mkustermann]

I'm glad to see this issue filed, but I think we should go much further, and include _GrowableList in the refactoring.

We have talked about that as well. Though it would require GC support due to one object having the data in payload vs other in an object pointed to by a field. We have done something similar for typed - by introducing inner pointers, maybe it would be feasible to extend that logic to lists as well.