[System.Linq] Consider adding runtime checks for IReadOnlyCollection<T> in input sources

[cmeyertons]

There are many places in the Linq / Collection code that leverage detecting if an IEnumerable<T> is an ICollection<T> to perform optimizations (e.g. presizing a new array, etc.)

List.cs

Because ICollection<T> implements IReadonlyCollection<T>, IReadonlyCollection<T> should be exclusively used in these scenarios to support custom IReadonlyCollection<T> implementations that don't necessary want to expose Add(T item)

Currently, collection authors have to implement ICollection to take advantage of the performance gains and leave Add throwing NotImplementedException to convey proper usage.

Tagging subscribers to this area: @eiriktsarpalis, @jeffhandley
See info in area-owners.md if you want to be subscribed.

[stephentoub]

Because ICollection<T> implements IReadonlyCollection<T>

It doesn't.

[EgorBo]

If I recall correctly such suggestions to add (not to replace ICollection) fast paths for IReadOnlyCollection here and there were rejected several times because such casts to covariant interfaces were super slow, however these performance issues were fixed as far as I know (cast caches, inlined checks) so maybe it worth checking if we can add them in some places?

[danmoseley]

@davidwrighton are these kinds of "optimistic checks for interfaces" indeed much cheaper now than in the past?

[EgorBo]

cc @VSadov

[cmeyertons]

Because ICollection<T> implements IReadonlyCollection<T>

It doesn't.

As I was! Egg on my face for sure. Apologies, i thought this would be a drop-in request. Thanks for the quick replies

[EgorBo]

@danmosemsft a quick benchmark:

static IEnumerable<string> strings = new List<string>();

[Benchmark]
public bool IsCollection() =>   strings is ICollection<string>;

[Benchmark]
public bool IsReadOnlyList() => strings is IReadOnlyCollection<string>;

.NET Core 2.2:

|          Method |      Mean |     Error |    StdDev |
|---------------- |----------:|----------:|----------:|
|   IsCollection  |  2.637 ns | 0.0038 ns | 0.0035 ns |
| IsReadOnlyList  | 41.492 ns | 0.0911 ns | 0.0808 ns |

.NET Core 3.0:

|          Method |      Mean |     Error |    StdDev |
|---------------- |----------:|----------:|----------:|
|   IsCollection  |  1.069 ns | 0.0008 ns | 0.0007 ns |
| IsReadOnlyList  | 40.578 ns | 0.0316 ns | 0.0264 ns |

.NET 5.0:

|          Method |      Mean |     Error |    StdDev |
|---------------- |----------:|----------:|----------:|
|   IsCollection  |  1.121 ns | 0.0010 ns | 0.0009 ns |
| IsReadOnlyList  |  2.976 ns | 0.0094 ns | 0.0088 ns |

Related PR: dotnet/coreclr#23548

[VSadov]

Covariant interfaces are not super slow now.

Cost can vary for both regular interface casts and for fancy ones. Regular interface cast is a linear search, but typically does not need to search far. Cached cast may need to deal with hash collisions, but typically just gets a cached value.

As a veeery rough estimate a fancy cast can be counted as a 2X of a regular interface cast.

In the past the cost of complicated casts was technically unbounded. As you nest variant generics, the cost would go up and considerably. Thus they were avoided by library owners.

[danmoseley]

Thanks @EgorBo that is indeed much faster.

[davidwrighton]

It is definitely faster than before, but there is still a non-zero cost to performance when making the suggested change.

I have a few possible concerns here.

1. What about customers that only implement ICollection<T> and not IReadOnlyCollection<T>?
2. If we mitigate concern WIP: repo consolidation scouting kick-off - make clr build locally on Windows #1 by having checks for both ICollection<T> and IReadOnlyCollection<T> how much of a penalty does making the LINQ functions larger have?
3. Do we have any concerns around customers who may have implemented IReadOnlyCollection<T> in such a way that it does not match with the behavior of IEnumerable<T>? My guess is that we would not treat such scenarios specially, but it is a real possibility that customers with custom written collections may have incorrect implementations of code that hasn't been tested.
4. As @VSadov notes, the performance impact is now much less severe, but its not nothing.

[EgorBo]

It is definitely faster than before, but there is still a non-zero cost to performance when making the suggested change.

I have a few possible concerns here.

1. What about customers that only implement ICollection<T> and not IReadOnlyCollection<T>?
2. If we mitigate concern WIP: repo consolidation scouting kick-off - make clr build locally on Windows #1 by having checks for both ICollection<T> and IReadOnlyCollection<T> how much of a penalty does making the LINQ functions larger have?
3. Do we have any concerns around customers who may have implemented IReadOnlyCollection<T> in such a way that it does not match with the behavior of IEnumerable<T>? My guess is that we would not treat such scenarios specially, but it is a real possibility that customers with custom written collections may have incorrect implementations of code that hasn't been tested.
4. As @VSadov notes, the performance impact is now much less severe, but its not nothing.

A good example is Linq's Count: https://github.com/dotnet/runtime/blob/master/src/libraries/System.Linq/src/System/Linq/Count.cs#L11-L46

IReadOnlyCollection<T> check used to apply a penalty for the O(N) foreach-based fallback (note other fast paths), but now that penalty ~15 times smaller.
But of course it depends on how often users have IROC there - I am not in charge to answer 🙂
Currently Count for IReadOnlyCollection<T> input leads to O(N) loop which can be quite slow for large collections.

[AndyAyersMS]

There were also perf issues with limited numbers of "fast" dictionary slots (see #11971) that should now be (largely) mitigated by the dynamic dictionary expansion added in 5.0.