Commits on Jul 3, 2024

1. Optimize LINQ sinks for IList<T>s …

   We've debated such an optimization several times over the years: rather than always enumerating via IEnumerable, special-case IList<T> to iterate via the indexer, which avoids allocating the enumerator and cuts the number of interface calls in half. We've avoided doing so in part because it adds some extra complexity, but more so because it adds some fixed overhead that doesn't yield benefits when the source isn't an `IList<T>`, such as the `IEnumerable<T>` produced by an iterator in C#.
   
   However, a variety of circumstances have changed over the last few years that I think shift the balance to the point where adding in these special-cases make sense. Casts to interfaces have been made cheaper over the last few years, including an improvement in .NET 9 that enables dynamic PGO to work better with `is` type checks. Moreover, Visual Studio analyzers now encourage simplifying expressions like `Where(predicate).First()/Any()/etc` to instead be `First(predicate)`/`Any(predicate)`/etc: we have these optimizations in the former, but we lack them today in the latter, so while following the analyzer suggestion does simplify the code, it may actually deoptimize the code given how LINQ is currently implemented.  Finally, custom `IList<T>`s just became much more common with collection expressions in C# 12. In order to ensure readonly-ness for types folks may expect to be readonly, if you have a method like `static IEnumerable<int> M() => [1, 2, 3, 4, 5]` or `static IReadOnlyList<int> M() => [1, 2, 3, 4, 5]`, the compiler will synthesize a custom type that implements `IList<T>` (and other interfaces) but with `IsReadOnly` returning true and throwing NotSupportedException from the various mutating methods, so even in places where we special-case `List<T>` and where `List<T>` may have been used before, when someone switches such a method to use collection expressions instead, by default they'll end up with something `IList<T>` but not `List<T>` or `T[]`.
   
   Given all of that, I've updated cases where a simple loop was being used in the Enumerable sinks taking a predicate (e.g. Any, First, Count, etc.) to special-case `IList<T>`, and then further to specialize `T[]`/`List<T>` as two of the most popular types (this also ends up being impactful today with PGO, because PGO today can't devirtualize `IList<T>` over arrays).
   
   This significantly improves throughput when inputs are in fact `IList<T>`. It slightly regresses inputs that aren't; on my machine, on average it's adding a 1-3ns for the operation due to the extra type check/code.
   
   I also augmented tests based on some gaps in code coverage.

   

   stephentoub committed Jul 3, 2024
   Configuration menu

   • View commit details
   • Copy full SHA for e769879
   • Browse repository at this point

   Copy the full SHA

   e769879 View commit details

   Browse the repository at this point in the history