Andrzej Więckowski, Ph.D.

To Sort or Not to Sort, That Is the Allocation

In this short blog entry, we will continue the previous investigation into GC allocation: Dr. GCAlloc or: How I Learned to Stop Worrying and Love List<T>, and further explore the potential issues with GC allocation when using List<T>.

Let’s consider a simple struct with a single field, just for demonstration purposes

public readonly struct MyStruct
{
    public readonly int Value;
    public MyStruct(int value) => Value = value;
    public static implicit operator MyStruct(int v) => new(v);
    public override string ToString() => Value.ToString();
}

Then let’s consider a List of structs and built-in Sort method.

var list = new List<MyStruct> { 1, 5, 2, 8, 5, 3, 9, 0, 4, 2, 6, 6, 3, 1 };
list.Sort();

Using Unity’s profiler, we can investigate whether the Sort method causes any GC allocation.

IComparable

List<>.Sort has a few overloads. However, the code above will throw an exception at runtime. The type T has to implement IComparable, and unfortunately, this can be detected only at runtime. This is rather unfortunate, since C# is generally considered a strongly typed language, and this issue should, and arguably could, be detected before compilation.

public readonly struct MyStruct : IComparable<MyStruct>
{
    public readonly int Value;
    public MyStruct(int value) => Value = value;
    public int CompareTo(MyStruct other) => Value.CompareTo(other.Value);
    public static implicit operator MyStruct(int v) => new(v);
    public override string ToString() => Value.ToString();
}

...

list.Sort(); // 128 B GC alloc!

In Unity’s profiler, we can immediately see that this Sort call allocates 128 B of GC memory!

IComparer

Another option is to use a custom comparer implementation using a class

public class MyStructComparer : IComparer<MyStruct>
{
    public static readonly MyStructComparer Instance = new();
    public int Compare(MyStruct x, MyStruct y) => x.Value.CompareTo(y.Value);
}

or readonly struct

public readonly struct MyStructComparer : IComparer<MyStruct>
{
    public static readonly MyStructComparer Instance = new();
    public int Compare(MyStruct x, MyStruct y) => x.Value.CompareTo(y.Value);
}

and we can then call Sort using the custom comparer.

list.Sort(MyStructComparer.Instance);

Unfortunately, with both implementations, we again get GC allocations: 128 B and 145 B for the class and struct, respectively. I guess that the increased allocation in the struct implementation is related to boxing.

Comparison

Finally, another option for Sort is to use a Comparison delegate.

public readonly struct MyStruct
{
    public static Comparison<MyStruct> Comparison = (a, b) => a.Value.CompareTo(b.Value);
    public readonly int Value;
    public MyStruct(int value) => Value = value;
    public static implicit operator MyStruct(int v) => new(v);
    public override string ToString() => Value.ToString();
}

...

list.Sort(MyStruct.Comparison);

Surprisingly, this is the only solution presented here that is completely free of GC allocations!

Summary

To sum up, default GC allocation can be surprising in C#. It is very useful to debug and explore your code, especially when working with runtime applications that require top performance. Below is a table comparing GC allocation values for all possible Sort calls.

[Top]