Array.Sort() 分配大量内存

Question

我正在开发一个以 60fps 运行的可视化。该可视化的一部分是根据项目的位置对屏幕上的项目进行排序。我在用着

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

每秒分配近 1MB 的内存Comparison<T>，这会导致 GC 频繁运行，从而导致帧速率出现问题。

我已经尝试了几种变体Array.Sort，它们都在分配，包括接受的变体Comparison<T>（这也是不够的，因为它缺少index和length参数）。

有没有办法在 C# (.NET 5) 中对数组进行排序而不分配大量内存？

更新：这是一个重现，

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);
            }
        }
    }
}

以及旧机器上 30 秒后的分配，

Answer 1

我能够重现你的观察结果。Array.Sort在我的机器以及 dotnetfiddle.net 上，每个操作分配 64 个字节：

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");

输出：

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");

现场演示。

在我看来，这就像可以在 .NET 标准库中优化的东西。作为解决方法，您可以使用Sort下面的扩展方法，该方法不会分配。它接受 aComparison<T>而不是 a IComparer<T>while：

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);
}

使用示例。和以前一样，有这两个变化：

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

输出：

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

现场演示。

似乎也快了一些。

更新：我在 GitHub 上打开了一个关于这个问题的新线程，我得到了以下反馈：

分配跟踪显示分配是 delegate Comparison<int>。

分配在这里。

由于缺少价值委托，恐怕我们现在无能为力。

我的建议是使用Comparison<T>代替IComparer<T>，并通过 lambda 或字段缓存委托。