优化C# Unsafe快速排序代码，缩小与C++的性能差距

当前你的C# unsafe快速排序处理1000万条int数据耗时550ms，逻辑一致的C++版本仅需230ms，差距远超预期，以下是针对性的优化建议：

现有代码 #

using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace EditorPlayer
{
    internal static class Program
    {
        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        public unsafe static void UnsafeQuickSort(int[] data)
        {
            fixed(int* pData = data)
            {
                UnsafeQuickSortRecursive(pData, 0, data.Length - 1);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveOptimization | MethodImplOptions.AggressiveInlining)]
        private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
        {
            int i = left - 1;
            int j = right;

            while (true)
            {
                int d = data[left];
                do i++; while (data[i] < d);
                do j--; while (data[j] > d);

                if (i < j)
                {
                    int tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
                else
                {
                    if (left < j) UnsafeQuickSortRecursive(data, left, j);
                    if (++j < right) UnsafeQuickSortRecursive(data, j, right);
                    return;
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        internal static void Main(string[] args)
        {
            int[] array = new int[10000000];
            Random rnd = new Random();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = rnd.Next(100000);
            }

            Stopwatch stopwatch = new Stopwatch();

            stopwatch.Start();
            UnsafeQuickSort(array);
            stopwatch.Stop();

            Console.WriteLine($"Time took: {stopwatch.Elapsed.TotalMilliseconds}");
            Console.ReadLine();
        }
    }
}

优化建议 #

1. 优化基准值选择，避免最坏情况 #

当前代码固定选left位置的元素作为基准，在数组已排序/接近排序的场景下，会导致递归深度达到O(n)，性能暴跌。改用三数取中（取left、mid、right的中位数）作为基准，能大幅降低最坏情况的概率，同时提升平均性能：

private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
{
    // 小数据量改用插入排序，减少递归开销
    if (right - left < 16)
    {
        UnsafeInsertionSort(data, left, right);
        return;
    }

    // 三数取中选基准，调整位置简化边界判断
    int mid = left + (right - left) / 2;
    if (data[mid] < data[left]) { int tmp = data[left]; data[left] = data[mid]; data[mid] = tmp; }
    if (data[right] < data[left]) { int tmp = data[left]; data[left] = data[right]; data[right] = tmp; }
    if (data[right] < data[mid]) { int tmp = data[mid]; data[mid] = data[right]; data[right] = tmp; }
    
    int pivot = data[mid];
    int tmpVal = data[mid]; data[mid] = data[right - 1]; data[right - 1] = tmpVal;
    
    int i = left;
    int j = right - 1;

    while (true)
    {
        while (data[++i] < pivot);
        while (data[--j] > pivot);
        if (i < j)
        {
            tmpVal = data[i]; data[i] = data[j]; data[j] = tmpVal;
        }
        else
        {
            // 将基准移回正确分区位置
            tmpVal = data[i]; data[i] = data[right - 1]; data[right - 1] = tmpVal;
            // 递归处理左半部分，右半部分用循环消除尾递归
            if (left < i - 1) UnsafeQuickSortRecursive(data, left, i - 1);
            left = i + 1;
            if (left >= right) return;
        }
    }
}

// 小数据量插入排序实现
private unsafe static void UnsafeInsertionSort(int* data, int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int val = data[i];
        int j = i - 1;
        while (j >= left && data[j] > val)
        {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = val;
    }
}

2. 消除尾递归，减少栈开销 #

C#的递归调用栈开销比C++更明显，将第二个递归调用改为循环处理（尾递归消除），能减少栈帧创建的开销，提升性能。上面的代码已经实现了这一点：分区完成后仅递归处理左半部分，右半部分通过更新left变量在当前循环中继续处理。

3. 减少内存重复访问 #

原代码在while(true)循环内每次都重新读取data[left]作为基准，将基准值的读取和调整移到循环外，能减少不必要的内存访问次数，提升缓存命中率。

4. 编译与运行环境优化 #

• 确保项目以Release模式编译，开启所有优化选项（默认Release模式已开启）。
• 目标平台选择x64，避免32位环境的内存限制和性能损耗。
• 启用ReadyToRun编译：在项目文件中添加以下配置，提前将IL编译为机器码，减少JIT编译开销：

  <PropertyGroup>
    <PublishReadyToRun>true</PublishReadyToRun>
    <PublishTrimmed>true</PublishTrimmed>
  </PropertyGroup>
  

• 启用服务器GC：在runtimeconfig.json中添加配置，提升大内存场景的GC性能：

  {
    "runtimeOptions": {
      "configProperties": {
        "System.GC.Server": true
      }
    }
  }
  

5. 优化随机数组生成 #

原代码使用Random.Next生成随机数，Random不是线程安全的，循环中调用会产生锁开销。改用RandomNumberGenerator生成更高效的随机数组，避免影响排序计时：

int[] array = new int[10000000];
byte[] bytes = new byte[array.Length * 4];
using (var rng = System.Security.Cryptography.RandomNumberGenerator.Create())
{
    rng.GetBytes(bytes);
}
Buffer.BlockCopy(bytes, 0, array, 0, bytes.Length);
// 将数值范围限制到0-99999
for (int i = 0; i < array.Length; i++)
{
    array[i] = Math.Abs(array[i]) % 100000;
}

6. 尝试用Span替代Unsafe指针 #

.NET的Span<T>提供了接近unsafe指针的性能，同时更安全，编译器对Span的优化也非常充分。可以尝试将代码改为Span版本，性能可能接近甚至超过unsafe实现：

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
public static void SpanQuickSort(Span<int> data)
{
    if (data.Length <= 16)
    {
        InsertionSort(data);
        return;
    }

    // 三数取中选基准
    int mid = data.Length / 2;
    if (data[mid] < data[0]) Swap(ref data[0], ref data[mid]);
    if (data[^1] < data[0]) Swap(ref data[0], ref data[^1]);
    if (data[^1] < data[mid]) Swap(ref data[mid], ref data[^1]);
    
    int pivot = data[mid];
    Swap(ref data[mid], ref data[^2]);
    
    int i = 0;
    int j = data.Length - 2;
    while (true)
    {
        while (data[++i] < pivot);
        while (data[--j] > pivot);
        if (i < j)
        {
            Swap(ref data[i], ref data[j]);
        }
        else
        {
            Swap(ref data[i], ref data[^2]);
            SpanQuickSort(data[..i]);
            data = data[(i + 1)..];
            if (data.Length <= 1) return;
        }
    }
}

private static void InsertionSort(Span<int> data)
{
    for (int i = 1; i < data.Length; i++)
    {
        int val = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] > val)
        {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = val;
    }
}

private static void Swap(ref int a, ref int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

测试建议 #

优化后建议多次运行测试取平均值，避免单次运行的偶然性。同时可以对比.NET内置的Array.Sort方法性能，作为参考基准。

内容的提问来源于stack exchange，提问作者Barış Üçkardeş