- Notifications
You must be signed in to change notification settings - Fork5.2k
Replace LINQ's ArrayBuilder, LargeArrayBuilder, and SparseArrayBuilder with new SegmentedArrayBuilder#96570
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
ghost commentedJan 5, 2024
Tagging subscribers to this area: @dotnet/area-system-linq Issue DetailsFollowing up on#90459 (comment). FYI,@neuecc. There's a lot of code involved in these, some of which we special-case to only build into some of the targets. We can get most of the benefit with a simpler solution, which this attempts to provide. This commit removes those three types and replaces them with a SegmentedArrayBuilder. It uses stack space for the first N items (currently 8, hopefully that won't be an issue if some value type T is ridiculously large), and then uses an InlineArray of T[]s to store pool-rented arrays for each new segment it needs to allocate. Calling ToArray then produces an array of the exact right size, copying in the elements from the stack-allocated span and each of the constiuent arrays, then returning everything necessary to the pool. The changes to ToArray also obviate the need for the old Buffer type. It existed to avoid one array allocation at the end of loading an enumerable, where we'd doubled and doubled and doubled in size, and then eventually have an array with all the data but some extra space. Now that we don't have such an array, we don't need Buffer, and can just the normal Enumerable.ToArray. The one thing the new scheme doesn't handle as well is when there are multiple sources being added (specifically in Concat / SelectMany). Previously, the code used a complicated scheme to reserve space in the output for partial sources known to be ICollections, so it could use ICollection.CopyTo for each consistuent source. But CopyTo doesn't support partial copies, which means we can only use it if there's enough room available in an individual segment. The implementation thus tries to use it, and falls back to normal enumeration if it can't. For larger enumerations where the cost would end up being more apparent, the expectation is we'd quickly grow to a segment size where the subsequent appends are able to fit into the current segment and can thus still use the ICollection.CopyTo path. Hopefully. My main motivation here was to reduce the complexity of having all of the various builders.
usingBenchmarkDotNet.Attributes;usingBenchmarkDotNet.Running;BenchmarkSwitcher.FromAssembly(typeof(Tests<>).Assembly).Run(args);publicpartialclassTests<T>whereT:new(){privateT_value=new();[Benchmark][Arguments(1)][Arguments(5)][Arguments(50)]publicT[]Iterator_ToArray(intcount)=>GetItems(count).ToArray();privateIEnumerable<T>GetItems(intcount){for(inti=0;i<count;i++)yieldreturn_value;}}[HideColumns("Error","StdDev","Median","RatioSD","Job")][MemoryDiagnoser(false)]publicclassInt32Tests:Tests<int>{}[HideColumns("Error","StdDev","Median","RatioSD","Job")][MemoryDiagnoser(false)]publicclassObjectTests:Tests<object>{}
|
There's a lot of code involved in these, some of which we special-case to only build into some of the targets, and it's unnecessarily complicated. We can get most of the benefit with a simpler solution, which this attempts to provide. This commit removes those three types and replaces them with a SegmentedArrayBuilder.The changes to ToArray also obviate the need for the old Buffer type. It existed to avoid one array allocation at the end of loading an enumerable, where we'd doubled and doubled and doubled in size, and then eventually have an array with all the data but some extra space. Now that we don't have such an array, we don't need Buffer, and can just the normal Enumerable.ToArray.The one thing the new scheme doesn't handle as well is when there are multiple sources being added (specifically in Concat / SelectMany). Previously, the code used a complicated scheme to reserve space in the output for partial sources known to be ICollections, so it could use ICollection.CopyTo for each consistuent source. But CopyTo doesn't support partial copies, which means we can only use it if there's enough room available in an individual segment. The implementation thus tries to use it, and falls back to normal enumeration if it can't. For larger enumerations where the cost would end up being more apparent, the expectation is we'd quickly grow to a segment size where the subsequent appends are able to fit into the current segment. Hopefully.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
eiriktsarpalis left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Good candidate for this year's perf blog it seems? :-)
eerhardt commentedJan 10, 2024
@stephentoub, we are seeing a slight app size regression in the ASP.NET benchmarks that I think might be caused by this change.
The regression happened between1063fc2...b4ec422. I got the
Is this expected? The size regression is about 2% (roughly 200KB of 10MB). Here are the the mstat files I got from the benchmark server, in case someone wants to take a look. |
stephentoub commentedJan 10, 2024
I actually expected the opposite. Do you know where those additional interface implementations are coming from? The array pool ones are expected, in that we're renting arrays as part of ToArray, so we'll get ArrayPool types for T[]s being created by ToArray. |
stephentoub commentedJan 10, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Ah, looked at your sizeoscope files... they're all because of using ArrayPool in ToArray now. ArrayPool itself has this, for example: runtime/src/libraries/System.Private.CoreLib/src/System/Buffers/SharedArrayPool.cs Line 298 ine5bab5f
so for every distinct T used with the pool, you also get a distinctSharedArrayPool<T>.Partitions.Partition[] type and all of the interfaces it implements. |
stephentoub commentedJan 11, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
@MichalStrehovsky, is there any way (in corelib) to say "i promise this T[] will never be cast to any of the interfaces it implements, feel free not to keep that code around if it wouldn't otherwise be needed"? Or is there any kind of analysis we could be doing to automatically see that it's never used in that capacity? |
MichalStrehovsky commentedJan 11, 2024
We don't have that. We could build that; it sounds a bit like it would open a can of worms though. A different can of worms (with different problems) for consideration: staticT[]AllocateNewFrugalArray<T>(intcount)=>typeof(T).IsValueType?newT[count]:Unsafe.As<T[]>(newobject[count]);
We already do this analysis, but interfaces on reference type arrays are difficult to get rid of due to array covariance. The app might not be using |
stephentoub commentedJan 11, 2024
Thanks. I should be able to just use object[]. |
neuecc commentedJan 12, 2024
thanks for great implementation! |
Following up on#90459 (comment). FYI,@neuecc.
There's a lot of code involved in these, some of which we special-case to only build into some of the targets. We can get most of the benefit with a simpler solution, which this attempts to provide. This commit removes those three types and replaces them with a SegmentedArrayBuilder. It uses stack space for the first N items (currently 8, hopefully that won't be an issue if some value type T is ridiculously large), and then uses an InlineArray of T[]s to store pool-rented arrays for each new segment it needs to allocate. Calling ToArray then produces an array of the exact right size, copying in the elements from the stack-allocated span and each of the constiuent arrays, then returning everything necessary to the pool.
The changes to ToArray also obviate the need for the old Buffer type. It existed to avoid one array allocation at the end of loading an enumerable, where we'd doubled and doubled and doubled in size, and then eventually have an array with all the data but some extra space. Now that we don't have such an array, we don't need Buffer, and can just the normal Enumerable.ToArray.
The one thing the new scheme doesn't handle as well is when there are multiple sources being added (specifically in Concat / SelectMany). Previously, the code used a complicated scheme to reserve space in the output for partial sources known to be ICollections, so it could use ICollection.CopyTo for each consistuent source. But CopyTo doesn't support partial copies, which means we can only use it if there's enough room available in an individual segment. The implementation thus tries to use it, and falls back to normal enumeration if it can't. For larger enumerations where the cost would end up being more apparent, the expectation is we'd quickly grow to a segment size where the subsequent appends are able to fit into the current segment and can thus still use the ICollection.CopyTo path. Hopefully.
My main motivation here was to reduce the complexity of having all of the various builders.