Runtime: Linq (Enumerable.cs) should provide overloads for functions that can benefit heavily from knowing the static type of the receiver.

[CyrusNajmabadi]

Methods like Enumerable.Last work terribly if you pass in something that implements IReadOnlyList but not IList. We could provide additional overloads like: public static T Last<T>(this IReadOnlyList<T> list) { ... } so that we now had optimized implementations for these types.

This would also be beneficial so we can have codepaths that avoid having to dynamically check the type of the receiver at runtime when the compiler already knows statically what it can dispatch to.

[stephentoub]

We should update these methods to be be fast for people using immutable collections, not just mutable ones.

Which immutable collections are you referring to? The System.Collections.Immutable collections like ImmutableArray<T> and ImmutableList<T> already implement IList<T>.

If you have an IReadOnlyList

I'm not against updating LINQ to special-case additional interfaces (we have added some more in System.Linq.dll in CoreFx), but each time we add such a check, we pay the additional generic interface cast checking cost for the common case of not implementing that interface, which means we need to really weigh the value of it, because it's not free, e.g. https://github.com/dotnet/coreclr/issues/603

[CyrusNajmabadi]

Alternatively, can you just provide linq overloads for these types? It seems really unfortunate that there are these hidden perf pitfalls.

which means we need to really weigh the value of it, because it's not free

Neither is an O(n) traversal over a collection :)

Right now we're solving this by adding our own extension method on IReadOnlyList. However, we have to make sure it's in scope.

It feels somehow wrong that we both publish linq and a bunch of Interfaces, but linq may perform poorly on them.

[stephentoub]

Neither is an O(n) traversal over a collection :)

I understand. But that's existing behavior/perf. You're suggesting adding a check that could potentially be expensive and that would only have benefits for a subset of inputs. I'm simply pointing out that requires weighing how likely those inputs are and the associated wins that would come with them against the costs incurred for every other input.

[CyrusNajmabadi]

Actually, i retract my initial request. My request is now:

Please provide fast implementations of linq methods when the type is statically known. i.e., please provide things like:

c# public static T Last<T>(this IReadOnlyList<T> list) {...} public static T Last<T>(this IList<T> list)

Now there is no overhead of a type check at runtime. The compiler can statically dispatch to the best method. And that best method can do the O(1) operation instead of hte O(n) operation.

We seem to have ended up in this mismash world. We wanted an API that worked on a lowest common denominator API (i.e. IEnumerable), but we didn't like that perf could be bad (so we added special cases inside the code when we see _some_ types enter). But perf can still be bad because we only check for some interfaces (despite us shipping numerous other APIs in the fx).

ImmutableArray seems to have done the right thing here by making sure it provided good extension methods to prevent this pitfall. I think the Fx should do the same here for the types that they have also released :)

[CyrusNajmabadi]

Do you want me to change my title to reflect my new ask @stephentoub ?

[stephentoub]

Do you want me to change my title to reflect my new ask

Sure. And just to be clear, your request is to add to LINQ ~170 overloads for each of IReadOnlyList, IList, and other interfaces?

[CyrusNajmabadi]

Only the overloads that would benefit from knowing the static type of the collection. from looking at Enumerable.cs, it looks like we only optimize IList for First/FirstOrDefault/Last/LastOrDefault/Single/SingleOrDefault/ElementAt

I'd be happy if those guys just had overloads for the .net collections they can be optimized on.

[CyrusNajmabadi]

Done. Thanks!

[JonHanna]

What version of Enumerable.cs are you looking at? Those methods are no longer in that file, and those methods are optimised for; IList<T>, the results of OrderBy(), the results of Repeat(), the results of Range(), and the results of Take(), Skip() and Select() on any any of those (recursively, so including e.g. the results of Take(…).Select(…) on one of those).

Overloads based on static typing would offer convenience, but not performance. Consider:

C# public static TSource Last<TSource>(this IReadOnlyList<TSource> source) { if (source == null) { throw Error.ArgumentNull(nameof(source)); } int count = source.Count; if (count == 0) { throw Error.NoElements(); } return source[count - 1]; }

That's about as tight as that method could be. But if we knew statically that the type of source was IReadOnlyList<TSource> then, why would we call Last() and not source[source.Count - 1]?

1. At best everything here has to be done and it's equally as performant.
2. The method call may not get inlined, so we're slower than we could be.
3. We may know statically that the collection isn't null, so that check is a waste.
4. We may know statically that the collection isn't empty, so that check is a waste.
5. We may already know the size statically (e.g. from a previous need to find it), so that lookup is a waste.
6. We may know statically the concrete type and be able to avoid the two interface calls.

To the caller who knows statically that they have an IReadOnlyList<T>, such a Last() is a convenience, but the convenience has a cost in performance. That's not to say that the convenient approach shouldn't ideally be more performant, but when we consider that the convenience of Last() over source[source.Count - 1] isn't great and the performance of it can't be beaten, it's hard to see what is really gained.

And that's on top of the added inconvenience that we can't just do .Last() on a variable typed as ImmutableList<T> now, because the call is ambiguous between the two added overloads, so we have to cast it to either IList<T> or IReadOnlyList<T>.

(I have mused on the idea of a separate library that offered the same operations as Linq on immutable collections (specifically, those in S.C.Immutable) returning immutable types (a Select() on an IReadOnlyList<TSource> could return an IReadOnlyList<TResult>) and so both passing the benefits down the line, and also retaining immutability for contexts where immutability is important. I've not been convinced enough to actually go ahead and do so, but when it comes to static typing I think that if that is done, it should be done in that manner).

[JonHanna]

Indeed, it would break the code .ToList().Last() and similar, because the need to cast the list to either IList<T> or IReadOnlyList<T> would mean that chaining was broken.

[MgSam]

Yes I don't think adding the overloads are possible because of what JonHanna mentions.

It seems to me a better solution would be to make an IIndexable interface (or something similar), that both IList and IReadOnlyList implement. The existing runtime checks already performed by Linq could then check for IIndexable instead, and thus work on both use cases without an addition perf cost.

[JonHanna]

It would be a breaking change to IList and IReadOnlyList to make them derive from a newly-defined interface.

[JonHanna]

(Indeed, if that weren't the case, we could just have had IList derive from IReadOnlyList in the first place).

[MgSam]

If my understanding is correct, it's a breaking change because of:

• Binary backwards compatibility
• Explicit interface implementation

This is probably a bigger discussion than the scope of this thread, but keeping binary backwards compatibility forever seems like an unrealistic and very limiting goal. To remain relevant vs newer frameworks the BCL needs to be able to evolve.

Explicit interface implementation could easily be solved with an analyzer/code fix that ships with newer versions of the framework and makes the relevant tweaks to explicit interface implementations for you. The C# team has already expressed some interest in exploring doing this sort of thing- after all Swift continuously ships breaking changes but uses a similar method to address them. (And it seems to be growing immensely in popularity so what they're doing seems to work)

To get back to the original issue; I think trying to fix these sorts of problems with hacks on top of hacks over time is making the BCL into a mess.

[CyrusNajmabadi]

That's about as tight as that method could be. But if we knew statically that the type of source was IReadOnlyList then, why would we call Last() and not source[source.Count - 1]?

Because source[source.Count - 1] is verbose, ugly, and unclear. "Last" perfectly conveys what i want. If that's hte impl of Last, then that's fin with me. I just don't want to have that code scattered all over the codebase when we already provided Last (albeit in an O(n) form).

[CyrusNajmabadi]

It does not appear to be a break. C# has no problem compiling this code;

``` c#
class Test
{
static void Main(string[] args)
{
System.Linq.Enumerable.ToList(args).Last();
}
}

public static class Extensions
{
    public static int Last<T>(this IEnumerable<T> sequence) => 0;
    public static int Last<T>(this IReadOnlyList<T> list) => 0;
}

```

It picks the IReadOnlyList<T> overload.

[CyrusNajmabadi]

ImmutableList is also not a problem:

``` c#
class Test
{
static void Main(string[] args)
{
ImmutableList i = ImmutableList.Create();
i.Last();
}
}

public static class Extensions
{
    public static int Last<T>(this IEnumerable<T> sequence) => 0;
    public static int Last<T>(this IReadOnlyList<T> list) => 0;
}

```

[CyrusNajmabadi]

Overloads based on static typing would offer convenience

That's why i use a base class library in the first place. So there is a single place where all this stuff is defined, and it's actually got good performance. Instead of having to write it myself in all my libraries. Otherwise i either have to:

1. provide my own .Last in every project. yuck.
2. know to _not_ call .Last on an IReadOnlyList because of the perf problem. yuck.

Right now the BCL provides all these methods and provides some level of perf optimization for some types. So it can be a major pitfall when you use another BCL interface and you don't get good perf.

[JonHanna]

Your examples there are not what you were proposing, in which IList<T> was also specialised. Have an overload for IList<T> _and_ for IReadOnlyList<T> and you've got problems.

A big question here is how common are types that implement IReadOnlyList<T> but don't implement IList<T>, and how common are they likely to become. If they're an obscure case, then the people who create that case should probably deal with them themselves. If however they're a common case, or likely to become so in the near future, then the original proposal is a good one (and there are other ways that we could optimise beyond that, though the question of how often those types would also not have O(1) indexing affects just which of them would indeed be gains.

[JonHanna]

@MgSam would IIndexable be covariant?

[CyrusNajmabadi]

What version of Enumerable.cs are you looking at? Those methods are no longer in that file, and those methods are optimised for; IList, the results of OrderBy(), the results of Repeat(), the results of Range(), and the results of Take(), Skip() and Select() on any any of those (recursively, so including e.g. the results of Take(…).Select(…) on one of those).

To me, i would only care about this mainly for methods that would get a big-O boost from teh optimization. i.e. if the impl can go from O(n) to O(1) then those are the methods i care about.

[jamesqo]

I don't know if this has been mentioned before, but we would still have to check for the interfaces in the callee anyhow; it's very common the caller has an IList<T>, IReadOnlyList<T>, etc. but it's statically typed as an IEnumerable<T>. So the only thing we would be saving are a couple of typecasts.

Also IMO since the type is named Enumerable, it should have methods that accept/return IEnumerables and not other types. We don't want to leak the abstraction.

[NickStrupat]

Hi all,

So, we all agree that there are optimizations which can be made for IEnumerable<T> types. The roadblock to making that happen appears to be made up of the following realities:

• the current LINQ implementation makes some attempt to optimize based on a few interfaces the IEnumerable<T> might implement (IList<T>, ICollection<T>, IReadOnlyList<T>, etc.) by querying the type at runtime with the as operator
• overloads for specific types, known at compile time, are easily added but are never called if the LINQ operator is called through IEnumerable<T>
• we shouldn't break the current functionality so that we stay backward-compatible
• we shouldn't introduce a runtime type check for each optimized type because:
  
  
  
  • the cost to the binary size, JIT compile time, and runtime performance grows with each additional check + optimization
  
  
  • the implementation grows in complexity independently of which types are actually used by the calling code
  
  
• we shouldn't introduce a new interface into the middle of the inheritance hierarchy since that could break some user code which depends on that exact hierarchy being in place

In summary, while the current approach is a fair balance of complexity and performance, it is restrictive in that types implementing IEnumerable<T> can't inject their own optimized implementations of the LINQ operators.

I have a couple of ideas that offer a balanced solution, but I thought I'd first make this introduction.

[ryantrem]

Couple of comments on this:

1. One problem with having overloads for more specific types (e.g. IReadOnlyList and IList) is that this becomes "infectious" for anything built on top of it. For example, say we have ElementAt(IEnumerable), ElementAt(IList), and ElementAt(IReadOnlyList), and now on top of this I want to build a Median extension method. Well, I now have to implement three of these as well, and if a new collection related interface is added in the future, I'll have to come back and implement a fourth. Seems like this aspect should at least be considered.

2. Somewhat tangential, but why doesn't IList inherit from IReadOnlyList? If this were the case, then the various Enumerable extension methods could just be switched from checking for IList to checking for IReadOnlyList.

[jamesqo]

Now that there is a dedicated CollectionExtensions class, maybe some of these methods (specifically eagerly-evaluated onces, like Any() or First()) would be a good candidate for putting there.

[jamesqo]

@ryantrem

1. No, not necessarily. You only need to program against IEnumerable; you can program against IList / IReadOnlyList if you need better perf in your codebase, but it's not required.

2. Having IList inherit from IReadOnlyList would be a breaking change for people who implement the IList<T> indexer explicitly via T IList<T>.this[int index]. They would have to change such declarations to T IReadOnlyList<T>.this[int index]

[stephentoub]

I understand the motivation here, but this hasn't received attention in the last few years and I don't see that changing in the foreseeable future, so I'm going to close this. If there are specific places where performance is demonstrably poor in real-world scenarios and where additional APIs would help, those could certainly be considered; in such a case, please open an issue with the specifics of the APIs being proposed. (For the read-only variants specifically, though, there are already several issues discussing if/when the LINQ implementation should special-case implementations that implement a read-only interface and not one of the others.)