Array.Sort() allocating a large amount of memory

Question

I'm working on a visualization that runs at 60fps. Part of that visualization is sorting the items on screen based on their position. I'm using

Array.Sort<T>(T[] array, int index, int length, IComparer<T> comparer)

which is allocating almost 1MB of Comparison<T> per second, which causes the GC to run frequently, which causes framerate hiccups.

I've tried several variations of Array.Sort and they're all allocating, including the one that accepts Comparison<T> (which is also insufficient because it lacks index and length parameters).

Is there any way to sort an array in C# (.NET 5) without allocating large amounts of memory?

Update: Here's a repro,

using System;
using System.Collections.Generic;

namespace New_folder
{
    public class EmptyClass
    {
        // Empty
    }

    public class EmptyClassComparer : IComparer<EmptyClass>
    {
        public int Compare(EmptyClass x, EmptyClass y)
        {
            return 0;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            EmptyClass[] emptyClasses = new EmptyClass[100];
            for (int i = 0; i < 100; i++)
            {
                emptyClasses[i] = new EmptyClass();
            }
            EmptyClassComparer emptyClassComparer = new EmptyClassComparer();
            while (true)
            {
                Array.Sort(emptyClasses, 0, 50, emptyClassComparer);
            }
        }
    }
}

and the allocations after 30 seconds on an old machine,

Answer 1

I was able to reproduce your observations. 64 bytes are allocated per Array.Sort operation on my machine, as well as on dotnetfiddle.net:

var random = new Random(0);
var array = Enumerable.Range(1, 12).OrderBy(_ => random.Next()).ToArray();
Console.WriteLine($"Before Sort: [{String.Join(", ", array)}]");
var comparer = Comparer<int>.Create((x, y) => y - x); // Descending
const int loops = 1_000_000;
var mem0 = GC.GetTotalAllocatedBytes(true);
for (int i = 0; i < loops; i++)
{
    Array.Sort(array, 1, 10, comparer);
}
var mem1 = GC.GetTotalAllocatedBytes(true);
Console.WriteLine($"After Sort:  [{String.Join(", ", array)}]");
Console.WriteLine($"Allocated:   {(mem1 - mem0) / (double)loops:#,0} bytes per loop");

Output:

Before Sort: [5, 10, 11, 8, 12, 4, 6, 1, 3, 2, 7, 9]
After Sort:  [5, 12, 11, 10, 8, 7, 6, 4, 3, 2, 1, 9]
Allocated:   64 bytes per loop

Live demo.

It seems to me like something that could be optimized in the .NET standard libraries. As a workaround you could use the Sort extension method below, that doesn't allocate. It accepts a Comparison<T> instead of an IComparer<T> though:

public static void Sort<T>(this T[] array, int index, int length,
    Comparison<T> comparison)
{
    Span<T> span = new(array, index, length);
    MemoryExtensions.Sort(span, comparison);
}

Usage example. Like before, with these two changes:

Comparison<int> comparison = (x, y) => y - x; // Descending
//...
array.Sort(1, 10, comparison);

Output:

Before Sort: [5, 10, 11, 8, 12, 4, 6, 1, 3, 2, 7, 9]
After Sort:  [5, 12, 11, 10, 8, 7, 6, 4, 3, 2, 1, 9]
Allocated:   0 bytes per loop

Live demo.

It seems that it's also a little bit faster.

---

Update: I opened a new thread on GitHub about this issue, and I got the feedback below:

Allocation tracking shows that allocation is delegate Comparison<int>.

Allocated here.

Due to the lack of value delegate, I'm afraid there's nothing we can do now.

My suggestion is to use Comparison<T> instead of IComparer<T>, and cache the delegate via lambda or field.