[Perf -22%] System.Collections.AddGivenSize<Int32>.SortedList

[DrewScoggins]

Run Information

Architecture	x64
OS	ubuntu 18.04
Changes	diff

Regressions in System.Collections.AddGivenSize

Benchmark	Baseline	Test	Test/Base	Modality	Baseline Outlier
SortedList	36.19 μs	43.51 μs	1.20		False

Related Issue on x86 Windows

[Perf -12%] System.Collections.AddGivenSize.SortedList

Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Collections.AddGivenSize<Int32>*';

Histogram

System.Collections.AddGivenSize.SortedList(Size: 512)

[33468.100 ; 34241.363) | @
[34241.363 ; 35597.511) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[35597.511 ; 36860.074) | @@@@@@@@@@
[36860.074 ; 38381.947) | 
[38381.947 ; 40025.831) | @@@@@@@@@@@@@
[40025.831 ; 41613.940) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[41613.940 ; 42970.089) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[42970.089 ; 44360.270) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[44360.270 ; 46060.324) | @

Docs

Profiling workflow for dotnet/runtime repository
Benchmarking workflow for dotnet/runtime repository

[ghost]

Tagging subscribers to this area: @eiriktsarpalis
Notify danmosemsft if you want to be subscribed.

[danmoseley]

This test primarily stresses Array.Copy.

runtime/src/libraries/System.Collections/src/System/Collections/Generic/SortedList.cs

Lines 670 to 671 in d40d32b

	Array.Copy(keys, index, keys, index + 1, _size - index);
	Array.Copy(values, index, values, index + 1, _size - index);

The regression apparently occurred between Oct 29 and Nov 4th . On Nov 2nd, we rewrote Array.Copy in C# (dotnet/coreclr#27634)

There was actually a followup PR to replace some overloads of Array.Copy with others that touched SortedList on Nov 4th (dotnet/corefx#42343) but it does not affect the tested codepath.

cc @jkotas

[danmoseley]

Duped a bunch of tests that all stress Array.Copy and regressed at the same time.

Per comments from @stephentoub in some of these, it may be bimodal, or configuration dependent.

[jkotas]

Memory copying has very complex perf characteristics. Any change will make some cases faster in some situations and some other cases slower in other situations.

I do not think there is much we can do here.

[danmoseley]

OK, I am going to close this. Realistically if you are doing this in a hot code path, you would want to consider using a different datastructure . Instead of SortedList/SortedList<K,V>, which is array backed, SortedDictionary<K,V>, which would give you faster insert/remove at the cost of some memory. (details). Similarly for List<T>/Array you might use SortedSet<T> depending on what you want.

cc area owners @layomia @eiriktsarpalis