Introduce size-optimized IListSelect iterator #118156
Conversation
This lets us keep some of the constant-time indexing advantages of the IList iterator, without the GVM overhead of Select. There is a small size increase here, but nowhere near the cost of the GVM. In a pathological generated example for GVMs the cost was: 1. .NET 9: 12 MB 2. .NET 10 w/out this change: 2.2 MB 3. .NET 10 w/ this change: 2.3 MB In a real-world example (AzureMCP), the size attributed to System.Linq was: 1. .NET 9: 1.2 MB 2. .NET 10 w/out this change: 340 KB 3. .NET 10 w/ this change: 430 KB This seems like a good tradeoff. We mostly keep the algorithmic complexity the same across the size/speed-opt versions, and just tradeoff on the margins. We could probably continue to improve this in the future.
|
Tagging subscribers to this area: @dotnet/area-system-linq |
There was a problem hiding this comment.
Pull Request Overview
This PR introduces a size-optimized IList-based Select iterator to reduce binary size while maintaining constant-time indexing advantages. The change removes the size-optimized variants of Take and Skip operations in favor of a more targeted optimization for Select operations on IList collections.
Key changes:
- Introduces
SizeOptIListSelectIteratorfor size-optimized Select operations on IList collections - Removes size-optimized Take and Skip iterator implementations
- Updates Take and Skip to always use speed-optimized variants
Reviewed Changes
Copilot reviewed 7 out of 7 changed files in this pull request and generated 2 comments.
Show a summary per file
| File | Description |
|---|---|
| src/libraries/System.Linq/src/System/Linq/Take.cs | Removes conditional size optimization, always uses speed-optimized iterator |
| src/libraries/System.Linq/src/System/Linq/Take.SizeOpt.cs | Removes size-optimized Take iterator implementation |
| src/libraries/System.Linq/src/System/Linq/Skip.cs | Removes conditional size optimization, always uses speed-optimized iterator |
| src/libraries/System.Linq/src/System/Linq/Skip.SizeOpt.cs | Completely removes file containing size-optimized Skip iterator |
| src/libraries/System.Linq/src/System/Linq/Select.cs | Adds IList detection and uses new size-optimized IList iterator |
| src/libraries/System.Linq/src/System/Linq/Iterator.SizeOpt.cs | New file implementing size-optimized IList Select iterator |
| src/libraries/System.Linq/src/System.Linq.csproj | Updates project to include new Iterator.SizeOpt.cs and remove Skip.SizeOpt.cs |
Co-authored-by: Copilot <[email protected]>
Co-authored-by: Stephen Toub <[email protected]>
|
/azp run runtime-nativeaot-outerloop |
|
Azure Pipelines successfully started running 1 pipeline(s). |
Co-authored-by: Stephen Toub <[email protected]>
This takes a more aggressive direction and removes the size optimized versions of iterators for Skip and Take. As far as I can tell these are relatively small size increases, but using them preserves the O(1) optimizations in the ' speed' version.
|
Fixed to be slightly more aggressive -- while doing more thorough testing I found more code paths that went from O(1) to O(n) with sizeopt enabled. I've fixed them by just removing sizeopt for Take and Skip. This doesn't seem to seriously hurt the binary size. I bet there some small improvements we can make (trying to fold array and IList into the same codepath), but this seems like a pretty good middle ground. |
|
Also, I added a unit test for the Select().Count() case you mentioned. Couldn't find an existing one. |
|
There are similar complexity issues with |
Yes. I haven't tried to walk through every scenario in this PR, just one Select/Take/Skip scenario. |
|
Also, surprised |
HashSet<int> x = [...];
HashSet<int> y = [...];
bool contains = x.Union(y).Contains(100);
|
|
If the complexity has to be fixed for all of those methods, there isn't much left in Iterator.SpeedOpt.cs: just I think the biggest issue here is the quadratic growth with |
I agree, but I’d still rather do the other ones in a different PR.
Ah I didn’t realize there was special support for sets. |
I think we'd want to evaluate the overall tradeoff here instead of doing several individual papercuts. Take all the changes we'd want to make here, evaluate if it still makes the difference between sizeopt/speedopt meaningful, and whether we reached the stated goal (no differences in algorithmic complexity between sizeopt and speedopt). The changes can still go in through individual PRs for reviewability, but the full scope of the regression and achievability of the stated goal is important. If we cannot achieve 100% same algorithmic complexity or if the sizeof/speedopt size difference becomes insignificant, it is a very different conversation. For example the first iteration of this PR was a 0.3% size regression for WebApiAot. The second iteration is already at 1.3%. How much more can we expect? We know the impact to throughput is going to be zero, because I measured it in the past. We'd want similar numbers for Mono iDevices/Android/WASM, since this is regressing those too and that regression would be a version-to-version regression. It might also be a tougher sell because we received zero TP complaints over the years this was the default and in .NET 10 we make it possible for the user to just disable this (it was not even possible to disable in the past so if someone raised this, we'd not be able to offer a solution). |
We have those numbers for native AOT in various places. If you're in the pathological case, the GVM impact is the biggest contributor: #109978 (comment). If you're in the non-pathological case the non-GVM expansion dominates (e.g. #109978 (comment) is Avalonia without the GVM fix - about 1 MB; the GVM bypass saves another 300 kB). For non-Native AOT scenarios, I don't think GVM bypass does anything because Mono doesn't try to analyze GVMs and falls back to universal slow generic code. We could reconsider placing the GVM bypass behind a separate feature switch but that runs into problems discussed in #109978 (comment). The GVM bypass has interactions with SizeOpt, so an app will behave differently if you enable one, the other, or both. And I don't know how we'd doc two feature switches that do various tradeoffs to LINQ (and set different defaults based on platforms). Sometimes simpler is just better. I'd not lose sleep over won't fixing #115033 despite the heated conversation. |
|
I tested out my suggestion above: folding List, Array, and IList for Select all into IList seems to have significant benefits. It seems to win back ~30% of the difference. I'd still rather do those changes in a separate PR: if we have to revert any of these PRs, I'd rather revert only one. I'm still looking at the other places where we separate List/Array/IList, like |
These are more (relatively common) cases where you could end up with an O(n) implementation instead of O(1) even when the backing enumerable is capable of doing O(1) index access.
|
Added a number of commits here:
My local testing is that the webaot project goes from ~100 KB extra to only ~40 KB extra. I haven't yet re-run the test for azure MCP |
This lets us keep some of the constant-time indexing advantages of the IList iterator, without the GVM overhead of Select. There is a small size increase here, but nowhere near the cost of the GVM.
In a pathological generated example for GVMs the cost was:
In a real-world example (AzureMCP), the size attributed to System.Linq was:
This seems like a good tradeoff. We mostly keep the algorithmic complexity the same across the size/speed-opt versions, and just tradeoff on the margins. We could probably continue to improve this in the future.
Fixes #115033