Slow linear scan when instantiating types / unlimited size type instantiation cache

[mkustermann]

Right now we have a linear cache stored on uninstantiated TypeArguments objects that is consulted when code wants to instantiate it with instance/function type arguments vectors. The linear cache doesn't have a limit, see TypeArguments::InstantiateAndCanonicalizeFrom

For most classes this is not a problem due to the limited number of actual instantiated TAVs.

Though for some classes that are instantiated with many different types, this linear search can become a performance issue. One issue identified is in our Future implementation:

class _FutureListener<S, T> { }

class _Future<T> {
  FutureOr<T> handleValue(S sourceResult) {
    return _zone.runUnary<FutureOr<T>, S>(_onValue, sourceResult);
  }
}

There can be many different values for T and S (~ as many different return types there are for async functions). This can cause significant slowdown of larger apps.

Though this is of course not limited to Future related code - it's an issue for any class that is used with many different types. I imagine HashMap suffering from the same, which uses

class _HashMap<K, V>  {
  void _addEntry(...) {
    buckets[index] = new _HashMapEntry<K, V>(...)
}