SortedList allocates memory due to boxing of TKey

[PetrAltman]

Description

SortedList<TKey, TValue> with struct TKey allocates memory due to boxing of TKey.

Configuration

Net 8,0

Analysis

Several methods in SortedList (e.g., Add, Remove, IndexOf) verify that the key is not null by invoking ArgumentNullException.ThrowIfNull(key);. ThrowIfNull expects an object parameter, causing TKey to be boxed when it is a struct type. This behavior should be avoided for struct types. It might be beneficial to add a generic overload to ArgumentNullException that does not allocate memory for struct types. This change could be useful as similar scenarios might occur in other generic classes within .NET.

[stephentoub]

Are you actually seeing that boxing happening in release with optimized code? The boxing associated with that ThrowIfNull gets optimized away by the JIT.

[PetrAltman]

Oh, I didn't think of JIT could optimize that.

I had a naive benchmark:

var l = new SortedList<int, int>();

for (int it = 0; it < 100; it++)
{
    var a0 = GC.GetAllocatedBytesForCurrentThread();

    for (int i = 0; i < 1000; i++)
    {
        l.Remove(i);
    }

    var a1 = GC.GetAllocatedBytesForCurrentThread();

    Console.WriteLine(a1 - a0);
}

Where the number of iterations matters... This version returns on my machine:
24000
24000
24000
24000
24000
24000
24000
24000
24000
23520
0
0
0
0
0
0
0

It probably depends on when tiered JIT generates optimal code.
After switching TieredCompilation to false, it always returns 0.

[stephentoub]

Yes, in tier 0, almost all optimization is disabled (including but definitely not limited to boxing elimination). For ThrowIfNull, inlining needs to be enabled for the JIT to be able to see that the boxed object isn't actually needed, and inlining is one of the many optimizations disabled in tier 0, too.

[MichalPetryka]

The boxing associated with that ThrowIfNull gets optimized away by the JIT.

Is Mono able to remove it too or is it just with CoreCLR?

[huoyaoyuan]

I'm concerned about how this would affect relatively cold methods. The impact of one particular method is limited by the threshold of Tier 0, but invoking many different methods may be impacted more.

[EgorBo]

#104815 removed this boxing from Tier0 as well