c# - C#中内联方法的成本

Question

我最近在 C# 中实现了 QuickSort 算法。对包含数百万项的整数数组进行排序，代码的性能比 .NET 的实现落后大约 10%。

private static void QS(int[] arr, int left, int right)
{
    if (left >= right) return;

    var pIndex = Partition(arr, left, right);
    QS( arr, left, pIndex);
    QS( arr, pIndex + 1, right);
}

在包含 500 万个项目的数组中，此代码比 .NET 慢约 60 毫秒。

随后，我创建了另一个具有 Partition() 的方法。内联到 QS() 中的方法(消除方法调用和 return 语句)。然而，这导致性能下降到比 .NET 的排序方法慢约 250 毫秒。

为什么会发生这种情况？

编辑:这是 Partition() 的代码方法。在 QS() 的内联版本中，该方法的全部内容，除了 return语句替换了 var pIndex = Partition(arr, left, right);线。

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[left];
    int leftPoint = left - 1;
    int pIndex = right + 1;
    int temp = 0;

    while (true)
    {
        do { pIndex--; } while (arr[pIndex] > pivot);
        do { leftPoint++; } while (arr[leftPoint] < pivot);

        if (leftPoint < pIndex)
        {
            temp = arr[leftPoint];
            arr[leftPoint] = arr[pIndex];
            arr[pIndex] = temp;
        }
        else { break; }
    }
    return pIndex;
}

编辑#2:
如果有人对编译感兴趣，这里是调用算法的代码:

编辑#3:
来自 Haymo 建议的新测试代码。

private static void Main(string[] args)
{
    const int globalRuns = 10;
    const int localRuns = 1000;

    var source = Enumerable.Range(1, 200000).OrderBy(n => Guid.NewGuid()).ToArray();
    var a = new int[source.Length];

    int start, end, total;

    for (int z = 0; z < globalRuns; z++)
    {
        Console.WriteLine("Run #{0}", z+1);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Array.Sort(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", ".NET", total, total / localRuns);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Quicksort.SortInline(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", "Inlined", total, total / localRuns);

        total = 0;
        for (int i = 0; i < localRuns; i++)
        {
            Array.Copy(source, a, source.Length);
            start = Environment.TickCount;
            Quicksort.SortNonInline(a);
            end = Environment.TickCount;
            total += end - start;
        }
        Console.WriteLine("{0}\tTtl: {1}ms\tAvg: {2}ms\n", "Not inlined", total, total / localRuns);
    }
}

Answer 1

根据问题中提供的信息，人们只能猜测并说出一些想法。

你测量对了吗？请记住，为了获得可靠的性能结果，应该(至少)

运行不带调试器的发布版本

经常重复测试并对结果取平均值

使测试公平，即。为所有测试对象提供相同的“资源配置”

为了确保(假设的)性能下降的根源确实与函数内联有关，可以调查生成的 IL 代码。甚至更好:JIT 编译器生成的机器指令。

对于 ILNumerics我们实现了自定义快速排序并进行了很多性能测量。最终的算法比 CLR 版本快几倍。手动内联只是一项改进，这是提高性能所必需的。其他有:

不使用递归

使用不安全的比较/交换

对较小的分区使用插入排序

优化临时(堆栈替换)阵列的有限大小

很多时候，奇怪的性能结果的来源是通过算法(错误)使用内存的方式找到的。另一个可能存在于不同的指令流中，这些指令流最终或多或少地成功地被任何涉及的编译器/处理器优化。整体执行性能是一个高度复杂的野兽，很难确定性地猜测，因此 分析器是您最好的 friend !

@编辑:通过查看您的主要测试例程，您似乎主要测量处理器/主内存的内存带宽。长度为 5*10e6 的 int[] 数组大小约为 19 MB。这很可能超出了您的缓存范围。因此，大多数情况下，由于强制缓存未命中，处理器将等待内存。这使得难以猜测任何代码重构的影响的度量。我建议尝试以这种方式衡量:(伪代码)

生成测试数据

为副本分配数组

迭代全局重复次数(假设为 10)

Array.Sort 的内部重复(例如 1000)

复制(未排序的)测试数据

排序 复制 按 Array.Sort

添加时间

Array.Sort 的平均时间

Quicksort.Sort 的内部重复(例如 1000)

复制(未排序的)测试数据

排序 复制 通过 Quicksort.Sort

添加时间

Quicksort.Sort 的平均时间

Quicksort.Sort2 的内部重复(例如 1000)

复制(未排序的)测试数据

排序 复制 通过 Quicksort.Sort2

添加时间

Quicksort.Sort2 的平均时间

目标是让快速排序只使用缓存中的数据。因此，请确保不要从新内存重新创建副本，而是只有两个全局实例:原始实例和要排序的副本。两者都必须同时适合您的(最后一级)缓存!有一些空间(对于系统上的其他进程)，一个很好的猜测是只使用两个阵列可用的最后一级缓存大小的一半。根据您的真实缓存大小，250k 的测试长度似乎更合理。

@Edit2:我运行了你的代码，得到了相同的结果，并在 VS 调试器中查看了(优化的)机器指令。这是两个版本的相关部分:

Not inlined: 
    69:                 do { pIndex--; } while (arr[pIndex] > pivot);
00000017  dec         ebx 
00000018  cmp         ebx,esi 
0000001a  jae         00000053 
0000001c  cmp         dword ptr [ecx+ebx*4+8],edi 
00000020  jg          00000017 
    70:                 do { leftPoint++; } while (arr[leftPoint] < pivot);
00000022  inc         edx 
00000023  cmp         edx,esi 
00000025  jae         00000053 
00000027  cmp         dword ptr [ecx+edx*4+8],edi 
0000002b  jl          00000022 


Inlined: 
    97:                 do { pIndex--; } while (arr[pIndex] > pivot);
00000038  dec         dword ptr [ebp-14h] 
0000003b  mov         eax,dword ptr [ebp-14h] 
0000003e  cmp         eax,edi 
00000040  jae         00000097 
00000042  cmp         dword ptr [esi+eax*4+8],ebx 
00000046  jg          00000038 
    98:                 do { leftPoint++; } while (arr[leftPoint] < pivot);
00000048  inc         ecx 
00000049  cmp         ecx,edi 
0000004b  jae         00000097 
0000004d  cmp         dword ptr [esi+ecx*4+8],ebx 
00000051  jl          00000048 

可以看出，“非内联”版本确实更好地利用了寄存器来递减运行索引(第 69/97 行)。显然 JIT 决定不压栈和弹出栈上的相应寄存器，因为同一函数中的其他代码正在使用相同的寄存器。由于这是一个热循环(并且 CLR 无法识别)，因此整体执行速度会受到影响。因此，在这种特定情况下，手动内联 Partition 函数是无利可图的。

但是，如您所知，不能保证其他版本的 CLR 也会这样做。 64 位甚至可能会出现差异。