Improve SortedSet<T>.TreeSubSet.Clear

[prozolic]

Summary

This PR specify Count as the initial capacity of List<T> to avoid unnecessary heap reallocations while collecting items via BreadthFirstTreeWalk, and replace the while loop that called RemoveAt(Count - 1) after each removal with a simple reverse for loop over the list by index.

Benchmark Results

Method	Job	Toolchain	Count	Mean	Error	StdDev	Median	Min	Max	Ratio	RatioSD	Code Size	Allocated	Alloc Ratio
TreeSubSet_Clear	Job-WYLMTD	\main\corerun.exe	10	10.650 us	1.1232 us	1.2935 us	10.350 us	9.100 us	13.20 us	1.00	0.00	267 B	640 B	1.00
TreeSubSet_Clear	Job-SHTHJF	\pr\corerun.exe	10	8.856 us	0.5452 us	0.5833 us	8.800 us	8.000 us	10.20 us	0.84	0.11	267 B	520 B	0.81
TreeSubSet_Clear	Job-WYLMTD	\main\corerun.exe	100	23.930 us	1.6118 us	1.8562 us	23.850 us	21.100 us	28.10 us	1.00	0.00	267 B	2752 B	1.00
TreeSubSet_Clear	Job-SHTHJF	\pr\corerun.exe	100	24.790 us	1.7995 us	2.0723 us	24.800 us	21.100 us	28.50 us	1.04	0.11	267 B	2024 B	0.74
TreeSubSet_Clear	Job-WYLMTD	\main\corerun.exe	1000	186.237 us	10.4397 us	11.6037 us	188.900 us	164.800 us	207.10 us	1.00	0.00	267 B	17384 B	1.00
TreeSubSet_Clear	Job-SHTHJF	\pr\corerun.exe	1000	185.722 us	12.6666 us	13.5531 us	193.500 us	162.600 us	200.10 us	1.00	0.09	267 B	13016 B	0.75
TreeSubSet_Clear	Job-WYLMTD	\main\corerun.exe	10000	1,113.750 us	20.5663 us	18.2315 us	1,111.300 us	1,069.700 us	1,141.80 us	1.00	0.00	267 B	197776 B	1.00
TreeSubSet_Clear	Job-SHTHJF	\pr\corerun.exe	10000	1,145.594 us	34.4062 us	33.7915 us	1,145.000 us	1,103.200 us	1,216.40 us	1.03	0.03	267 B	106432 B	0.54

    [MemoryDiagnoser]
    [BenchmarkCategory(Categories.Libraries, Categories.Collections, Categories.GenericCollections)]
    public class Perf_SortedSet_TreeSubSet_Clear
    {
        private SortedSet<int> viewSet;

        [Params(10, 100, 1000, 10000)]
        public int Count;

        [GlobalSetup]
        public void Setup()
        {
            var set = new SortedSet<int>(Enumerable.Range(0, Count));
            viewSet = set.GetViewBetween(0, Count - 1);
        }

        [IterationSetup]
        public void IterationSetup()
        {
            var set = new SortedSet<int>(Enumerable.Range(0, Count));
            viewSet = set.GetViewBetween(0, Count - 1);
        }

        [Benchmark]
        public int TreeSubSet_Clear()
        {
            viewSet.Clear();
            return viewSet.Count;
        }
    }

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[Copilot]

Pull request overview

This PR optimizes SortedSet<T>.TreeSubSet.Clear() in System.Collections by reducing List<T> growth overhead during item collection and simplifying the removal loop, aiming to lower allocations and improve clear-time performance for subset views.

Changes:

• Pre-allocate the removal buffer with Count as the initial List<T> capacity to avoid repeated internal array growth.
• Replace the while loop that repeatedly removed the last list element with a reverse index-based for loop.

[Copilot]

Pull request overview

Copilot reviewed 1 out of 1 changed files in this pull request and generated 1 comment.

[danmoseley]

seems ok. @eiriktsarpalis any concerns?

[Copilot]

Copilot's findings

• Files reviewed: 1/1 changed files
• Comments generated: 1

[eiriktsarpalis]

Thanks!