Memory and performance optimization for large dynamically-sized array-based collections

[abnercpp]

Hey. This is my first interaction on this repo. I love the .NET project and I'd like to contribute with a suggestion.

What I'd like to suggest is basically an optimization for large lists / sets / collections backed by arrays in general. Basically these data structures re-allocate the backing array when we exceed the current capacity (we typically allocate double of what he had previously). For recurring creation of large collections this can strain the GC quite a lot, and considerably slow down the application. I figure if maybe we can somehow leverage ArrayPool<T> we can reuse some of these arrays and avoid the cost of re-allocating whenever possible.

We can make the collection return the last array upon garbage collection using their destructor (or make them IDisposable if that's more desirable).

I mostly just copy-pasted the current List<T> implementation, except my implementation now uses ArrayPool<T> under the hood for renting and returning arrays, and I think the following benchmark speaks for itself.

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
Intel Core i7-8565U CPU 1.80GHz (Whiskey Lake), 1 CPU, 8 logical and 4 physical cores
.NET SDK=6.0.400
  [Host]     : .NET 6.0.8 (6.0.822.36306), X64 RyuJIT
  DefaultJob : .NET 6.0.8 (6.0.822.36306), X64 RyuJIT

Method	NumElements	Mean	Error	StdDev	Ratio	RatioSD	Rank	Gen 0	Gen 1	Gen 2	Allocated
StandardListWithInitialCapacity	32	115.5 ns	2.30 ns	3.00 ns	1.00	0.00	1	0.0440	-	-	184 B
NaivePoolingListWithInitialCapacity	32	167.3 ns	3.20 ns	3.14 ns	1.44	0.05	2	0.0076	-	-	32 B
StandardList	32	182.3 ns	3.59 ns	5.49 ns	1.58	0.07	3	0.0880	-	-	368 B
NaivePoolingList	32	218.6 ns	4.00 ns	3.74 ns	1.88	0.07	4	0.0076	-	-	32 B
LinkedList	32	621.2 ns	12.18 ns	15.84 ns	5.38	0.17	5	0.3767	-	-	1,576 B
NaivePoolingListWithInitialCapacity	256	696.0 ns	7.05 ns	6.59 ns	0.95	0.02	1	0.0076	-	-	32 B
StandardListWithInitialCapacity	256	735.2 ns	14.14 ns	15.13 ns	1.00	0.00	2	0.2575	-	-	1,080 B
NaivePoolingList	256	963.8 ns	7.70 ns	7.20 ns	1.31	0.03	3	0.0076	-	-	32 B
StandardList	256	995.1 ns	12.43 ns	11.02 ns	1.36	0.03	4	0.5331	-	-	2,232 B
LinkedList	256	4,495.9 ns	49.28 ns	46.10 ns	6.12	0.16	5	2.9449	-	-	12,329 B
NaivePoolingListWithInitialCapacity	1048576	2,427,703.0 ns	47,859.33 ns	93,345.95 ns	0.77	0.02	1	-	-	-	35 B
NaivePoolingList	1048576	2,649,415.8 ns	20,492.80 ns	17,112.42 ns	0.82	0.01	2	-	-	-	35 B
StandardListWithInitialCapacity	1048576	3,223,056.3 ns	22,859.18 ns	21,382.49 ns	1.00	0.00	3	312.5000	312.5000	312.5000	4,194,459 B
StandardList	1048576	5,424,696.6 ns	68,473.94 ns	64,050.56 ns	1.68	0.02	4	1992.1875	1992.1875	1992.1875	8,389,903 B
LinkedList	1048576	101,643,822.6 ns	1,360,463.07 ns	1,206,015.07 ns	31.54	0.42	5	8833.3333	3500.0000	1166.6667	50,333,723 B

The only caveat is that the ArrayPool<T>-backed list, although allocating far less memory, seems to be slower on inserts in general if the capacity is smaller than 256, as shown in the benchmarks. We can still dynamically switch strategies based on that threshold though, allocating new arrays before we hit this limit and then start renting, or allow the user to specify a renting strategy (minimal - for small lists and lists of unknown size in general - or aggressive - if we know the list will be big and re-allocate the backing array a lot.)

Code for POC and benchmarks can be found here.

[333fred]

This is a suggestion for the runtime repo. Moving it over there.

[Clockwork-Muse]

Duplicate of #27023

[danmoseley]

Cc @dotnet/area-system-collections

[danmoseley]

Btw @abenaru welcome to the repo! Discussion is welcome in the existing issue.