Linq's TryGetNonEnumeratedCount() should check for IReadOnlyCollection<T>

[KPixel]

IReadOnlyCollection<T> can provide a Count without enumerating in:

runtime/src/libraries/System.Linq/src/System/Linq/Count.cs

Line 95 in d687544

public static bool TryGetNonEnumeratedCount<TSource>(this IEnumerable<TSource> source, out int count)

Note: This request was already mentioned in #52775. However, since that issue started as something much bigger, I am concerned that this specific request will be missed.

[ghost]

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

Issue Details

---

IReadOnlyCollection<T> can provide a Count without enumerating in:

runtime/src/libraries/System.Linq/src/System/Linq/Count.cs

Line 95 in d687544

public static bool TryGetNonEnumeratedCount<TSource>(this IEnumerable<TSource> source, out int count)

Note: This request was already mentioned in #52775. However, since that issue started as something much bigger, I am concerned that this specific request will be missed.

Author:	KPixel
Assignees:	-
Labels:	area-System.Linq, untriaged
Milestone:	-

[huoyaoyuan]

#42254

[teo-tsirpanis]

This change would regress F#'s lists.

For those that don't know, they are implemented as single-linked lists, and their length is computed in linear time by traversing the entire list. They implement IReadOnlyCollection but not ICollection, which means that with the existing behavior, the TryGetNonEnumeratedCount method does not actually enumerate over the entire collection, which would happen if the method special-cased IReadOnlyCollections.

[eiriktsarpalis]

This was considered in the implementation PR but ultimately we went with reflecting the checks that exist in Enumerable.Count(). The decision was informed by the fact that most BCL types implementing IReadOnlyCollection<T> usually also implement ICollection<T>. I'm on the fence on this one, it's probably fair to assume that callers of this particular method might prefer one additional runtime check over not knowing the count. @stephentoub thoughts?

[stephentoub]

@stephentoub thoughts?

If we're going to start adding checks for IReadOnlyCollection<T>, I would like us to do so holistically across LINQ; that doesn't mean we need to add such checks everywhere, but we should evaluate all the places we look at ICollection<T> and decide whether a corresponding check for IReadOnlyCollection<T> makes sense, not just in this one method (especially since if this method successfully gives you the count, that might suggest subsequent LINQ operations would also be able to optimize by getting the count as part of the implementation, such that we actually make things worse if it's not the case). Also, historically we shied away from IROC<T> because its covariant nature made it a much more expensive type check to perform. We believe we've reduced those costs significantly, but any decision here would need to factor in the performance impact of the check.

[eiriktsarpalis]

This change would regress F#'s lists.

For those that don't know, they are implemented as single-linked lists, and their length is computed in linear time by traversing the entire list.

@teo-tsirpanis I see your point but I wouldn't consider it a regression. It is assumed that callers of TryGetNonEnumeratedCount need to know the count of the enumerable ahead of enumeration and the only way to achieve this in F# lists is via linear traversal. Note however that the IROC implementation uses the Length property which is substantially faster compared to using an enumerator. Thus technically speaking, the "NonEnumerated" part of TryGetEnumeratedCount is still being honored since no enumerator is being created.

[eiriktsarpalis]

If we're going to start adding checks for IReadOnlyCollection, I would like us to do so holistically across LINQ

That's probably covered by #42254. I'm going to close this issue in favor of that.