SortedList performance

[caz162]

Description

I am currently migrating my Xamarin.iOS app to .Net for iOS. During testing of this we noticed a performance hit when loading data. Drilling into this we noticed that it was coming from doing a deep copy of SortedLists.

What we do is copy one SortedList to another via its constructor (https://learn.microsoft.com/en-us/dotnet/api/system.collections.sortedlist.-ctor?view=net-9.0#system-collections-sortedlist-ctor(system-collections-idictionary)).
While this does create a deep copy of the SortedList it is significantly slower than it was in our old Xamarin App.

I have created 2 dummy projects to investigate, one in .Net Framework 4.8 and another in .Net 8.
Both are console apps that create a SortedList<Datetime, string> with 1000 dates, then measures the ticks it takes to copy this to a new SortedList. I run this 100 times to get an average.

Here is the example code I used in both the .Net Framework 4.8 and .Net 8 versions.

public void Run()
{
	for (int i = 0; i < 100; I++)
	{
		var originalSortedList = new SortedList<int, string>();

		for (int j = 0; j < 1000; j++)
		{
			var newDate = DateTime.Today.AddDays(j);
			originalSortedList.Add(j, j.ToString());
		}

		var sw = new Stopwatch();
		sw.Restart();

		var newSortedList = new SortedList<int, string>(originalSortedList);

		sw.Stop();

		Console.WriteLine(sw.ElapsedTicks);

		originalSortedList.Clear();
		newSortedList.Clear();
	}
}

Framework	.Net framework 4.8	.Net 8
Average ticks	1988.9	41223.36
Median ticks	1165	25063

Are the default comparers slower in the .Net 8 and later versions than they previously were or are there other operations going on that previously weren't?
Are there any reasons why the performance has changed so much and is there any way we can get it performing as well as it previously did?

Configuration

The code is running on both .Net Framework 4.8 and .Net 8 for comparison.
I am running a MacBook Pro M1 Max, which will have an ARM64 architecture.
Current OS version is macOS Sonoma 14.6.1.

This is also being experienced on a number of iPads.

Regression?

The code is running on both .Net Framework 4.8 and .Net 8 for comparison.

Data

Below is the data from a run of both versions

Framework	.Net framework 4.8	.Net 8
Average ticks	1988.9	41223.36
Median ticks	1165	25063
Run: 1	69290	989125
Run: 2	7020	33792
Run: 3	1220	19500
Run: 4	1093	18875
Run: 5	1087	20625
Run: 6	1092	19833
Run: 7	1368	19875
Run: 8	1165	23833
Run: 9	1170	26000
Run: 10	1188	573875
Run: 11	1229	29833
Run: 12	1156	32625
Run: 13	1088	33209
Run: 14	1286	29500
Run: 15	1181	30334
Run: 16	1178	28917
Run: 17	1091	31875
Run: 18	1086	31209
Run: 19	1095	26708
Run: 20	1094	26042
Run: 21	1110	28000
Run: 22	1302	35959
Run: 23	1129	26875
Run: 24	1158	27417
Run: 25	1156	27750
Run: 26	1143	28000
Run: 27	1137	29542
Run: 28	1174	26625
Run: 29	1251	26459
Run: 30	1148	27875
Run: 31	1162	27458
Run: 32	1123	27709
Run: 33	1170	27875
Run: 34	1117	26500
Run: 35	1087	25084
Run: 36	1250	25417
Run: 37	1099	32125
Run: 38	1087	26500
Run: 39	1090	26000
Run: 40	1155	28000
Run: 41	1103	30583
Run: 42	1087	26666
Run: 43	1148	26459
Run: 44	1365	25292
Run: 45	1091	24875
Run: 46	1082	56958
Run: 47	1150	25791
Run: 48	1302	25084
Run: 49	1091	24750
Run: 50	1086	24792
Run: 51	1071	24791
Run: 52	1090	23417
Run: 53	1081	23458
Run: 54	1167	22792
Run: 55	1177	27792
Run: 56	1270	26583
Run: 57	1192	24084
Run: 58	1177	24916
Run: 59	1395	23875
Run: 60	1657	27042
Run: 61	3800	23458
Run: 62	1586	26625
Run: 63	1299	24250
Run: 64	4292	25000
Run: 65	1606	25042
Run: 66	1282	23916
Run: 67	1245	22833
Run: 68	1204	23042
Run: 69	1175	22959
Run: 70	1172	22958
Run: 71	1180	23417
Run: 72	1437	22584
Run: 73	1180	23916
Run: 74	1202	24708
Run: 75	1263	22958
Run: 76	1177	24292
Run: 77	1185	23834
Run: 78	1431	23958
Run: 79	1163	28083
Run: 80	1136	22833
Run: 81	1192	24833
Run: 82	1205	23042
Run: 83	1203	22958
Run: 84	1150	22708
Run: 85	1241	22709
Run: 86	1226	22917
Run: 87	1169	23208
Run: 88	1097	27541
Run: 89	1141	23875
Run: 90	1078	23791
Run: 91	1083	23625
Run: 92	1076	25208
Run: 93	1072	26500
Run: 94	2121	23625
Run: 95	1118	23750
Run: 96	1120	23209
Run: 97	1146	24166
Run: 98	1112	23834
Run: 99	1153	42625
Run: 100	1165	24791

[dotnet-policy-service]

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

[huoyaoyuan]

The performance measurement is not in a correct way.

.NET Core employs more optimizations than .NET Framework, and requires much more loops to achieve a steady state performance. Using Stopwatch to measure one invocation is also incorrect - it's effectively measuring the overhead of Stopwatch itself and other debugging/performance tracing techniques. Further more, both Xamarin.iOS and .NET 8 for iOS uses the Mono runtime, which has significant performance difference. BenchmarkDotNet is

With a proper benchmark set up on Windows like this:

    [SimpleJob(RuntimeMoniker.Net48)]
    [SimpleJob(RuntimeMoniker.Net90)]
    public class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Program>();
        }

        private SortedList<int, string> originalSortedList;

        [GlobalSetup]
        public void Setup()
        {
            originalSortedList = new SortedList<int, string>();

            for (int j = 0; j < 1000; j++)
            {
                var newDate = DateTime.Today.AddDays(j);
                originalSortedList.Add(j, j.ToString());
            }
        }

        [Benchmark]
        public SortedList<int, string> Copy() => new SortedList<int, string>(originalSortedList);
    }

The result shows better performance on .NET 9:

Method	Job	Runtime	Mean	Error	StdDev
Copy	.NET 9.0	.NET 9.0	8.186 us	0.0315 us	0.0263 us
Copy	.NET Framework 4.8	.NET Framework 4.8	12.051 us	0.1361 us	0.1863 us

Even when running your original code on Windows x64, I'm only seeing an 2x performance difference during startup stage.