在.NET 4及以上版本中，数组边界检查的效率如何？

Question

我对 .net 中低级算法的效率很感兴趣。我想让我们未来能够选择更多地使用 C# 而不是 C++ 来编写代码，但其中一个难点是在循环和随机访问数组时出现的 .net 边界检查。

一个激励人心的例子是一个计算两个数组中对应元素乘积之和（这是两个向量的点积）的函数。

static void SumProduct(double[] X, double[] Y)
{
    double sum = 0;
    int length = X.Length;
    if (length != Y.Length)
        throw new ArgumentException("X and Y must be same size");
    for (int i = 0; i < length; i++) // Check X.Length instead? See below
        sum += X[i] * Y[i];
}

根据我所知，并不熟悉IL或x86以进行检查，编译器不会优化X和Y的边界检查。我错了吗？或者有没有办法编写我的代码使编译器帮我优化？关于在.NET中进行边界检查的问题，有许多效率方面的争论，其中最重要的是集中精力关注“大O”算法成本而不是比例常数，并且高级语言有助于实现这一点。关于这个主题，在.NET中进行数组边界检查的最佳文章是MSDN上的Array Bounds Check Elimination in the CLR（也在Stack Overflow答案中提到过启用优化的重要性）。由于这篇文章发表于2009年，因此我想知道自那时以来是否有显着变化。此外，该文章揭示了一些真正微妙的问题，这些问题可能会使我困惑，因此我希望得到一些专家建议。例如，在上面的代码中，似乎最好写i<X.Length而不是i<length。此外，我也天真地认为，对于一个具有单个数组的算法，编写foreach循环将更好地声明您的意图，并给予它最好的优化边界检查的机会。根据MSDN文章，下面的SumForBAD，我认为肯定会被优化，但实际上不会。而SumFor将直接优化，而SumForEach也将被优化，但不是微不足道的（如果将该数组作为IEnumerable<int>传递给函数，则可能根本不会进行优化）。

static double SumForBAD(double[] X)
{
    double sum = 0;
    int length = X.Length; // better to use i < X.length in loop
    for (int i = 0; i < length; i++)
        sum += X[i];
    return sum;
}

static double SumFor(double[] X)
{
    double sum = 0;
    for (int i = 0; i < X.Length; i++)
        sum += X[i];
    return sum;
}

static double SumForEach(double[] X)
{
    double sum = 0;
    foreach (int element in X)
        sum += element;
    return sum;
}

我根据 doug65536 的回答进行了一些调查。在 C++ 中，我比较了一个执行一次边界检查的 SumProduct 的时间。

for(int i=0; i<n; ++i) sum += v1[i]*v2[i];

对抗另一个版本，该版本进行了两次边界检查

for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];

我发现第二个版本慢了一些，但只有大约3.5%（使用Visual Studio 2010进行优化构建，默认选项）。然而，我想到在C#中可能会有三个边界检查。其中一个是明确的（在本问题开头的函数static void SumProduct(double[] X, double[] Y)中的i < length），另外两个则是隐含的（X[i]和Y[i]）。因此，我测试了第三个C++函数，它有三个边界检查。

for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];

这比第一次慢了35％，这值得关注。我在这个问题上进行了更多的调查，为什么在某些机器上添加额外的循环检查会有很大的差别，在其他机器上则有很小的差别？有趣的是，在不同的机器上，边界检查的成本似乎存在显著差异。

- TooTone

Answer 1

边界检查并不重要，因为：

• 边界检查由cmp/jae指令对组成，在现代CPU架构中合并为单个微操作（术语为“宏操作融合”）。比较和分支非常高度优化。

• 边界检查是一个前向分支，将被静态预测为未采取，也降低了成本。该分支永远不会被采取。（如果有时被采取，异常将抛出，因此错误预测的成本变得无关紧要）

• 一旦有任何内存延迟，推测执行将排队许多次循环迭代，因此解码额外指令对的成本几乎消失。

内存访问可能成为瓶颈，因此去除边界检查等微观优化的效果将消失。

- doug65536

---

我刚在C++中尝试了一些性能测量。一个带有两个数组边界检查的点积函数，如for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];，比只有一个数组边界检查的等效代码for(int i=0; i<n; ++i) sum += v1[i]*v2[i];慢了约3.5%。然而，让我想到在C#中，你将承担3个边界检查的开销：一个明确地在循环条件中，还有每次数组访问时的两个隐式边界检查。我测量了类似的C++代码for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];，结果比前者慢了35%。 - TooTone

@TooTone 有些情况下编译器会省略掉不必要的边界检查。我的理解是，如果循环条件已经通过测试 i 与 v1.Length 和 v2.Length 的大小关系进行了边界检查，那么在访问时就可以省略边界检查。 - doug65536

其实我没有想到这一点，但是很有道理。我把我写的C++代码放到了另一个问题，那里已经有一个有趣的关于编译器优化的评论了。 - TooTone

我认为这个答案需要稍作修改，以使其不那么误导人。在特定的 CPU 上，由于循环中只是进行了求和操作且数据类型相当宽泛，因此边界检查开销可能并不重要。但在循环中，数组边界开销确实经常会对性能产生显著影响。应该进行测量以确保结果。 - jackmott

@jackmott 世界上所有的边界检查都无法与 C# 程序中典型的垃圾回收滥用相比。 - doug65536

Answer 2

64位

64位JIT编译器在消除边界检查方面表现良好（至少在简单情况下）。我在你的方法末尾添加了return sum;，然后使用Visual Studio 2010 Release模式编译程序。在下面的反汇编代码中（我用C#进行了注释），请注意：

• 对于X，没有任何边界检查，即使您的代码将i与length而不是X.Length进行比较。这比文章中描述的行为有所改进。
• 在主循环之前，只有一次检查确保Y.Length >= X.Length。
• 主循环（偏移00000032到00000052）不包含任何边界检查。

反汇编代码

; Register assignments:
;    rcx  := i
;    rdx  := X
;    r8   := Y
;    r9   := X.Length ("length" in your code, "XLength" below)
;    r10  := Y.Length ("YLength" below)
;    r11  := X.Length - 1 ("XLengthMinus1" below)
;    xmm1 := sum

; (Prologue)
00000000  push        rbx
00000001  push        rdi
00000002  sub         rsp,28h

; (Store arguments X and Y in rdx and r8)
00000006  mov         r8,rdx   ; Y
00000009  mov         rdx,rcx  ; X

; int XLength = X.Length;
0000000c  mov         r9,qword ptr [rdx+8]

; int XLengthMinus1 = XLength - 1;
00000010  movsxd      rax,r9d
00000013  lea         r11,[rax-1]

; int YLength = Y.Length;
00000017  mov         r10,qword ptr [r8+8]

; if (XLength != YLength)
;     throw new ArgumentException("X and Y must be same size");
0000001b  cmp         r9d,r10d
0000001e  jne         0000000000000060

; double sum = 0;
00000020  xorpd       xmm1,xmm1

; if (XLength > 0)
; {
00000024  test        r9d,r9d
00000027  jle         0000000000000054

;     int i = 0;
00000029  xor         ecx,ecx
0000002b  xor         eax,eax

;     if (XLengthMinus1 >= YLength)
;         throw new IndexOutOfRangeException();
0000002d  cmp         r11,r10
00000030  jae         0000000000000096

;     do
;     {
;         sum += X[i] * Y[i];
00000032  movsd       xmm0,mmword ptr [rdx+rax+10h]
00000038  mulsd       xmm0,mmword ptr [r8+rax+10h]
0000003f  addsd       xmm0,xmm1
00000043  movapd      xmm1,xmm0

;         i++;
00000047  inc         ecx
00000049  add         rax,8

;     }
;     while (i < XLength);
0000004f  cmp         ecx,r9d
00000052  jl          0000000000000032
; }

; return sum;
00000054  movapd      xmm0,xmm1

; (Epilogue)
00000058  add         rsp,28h
0000005c  pop         rdi
0000005d  pop         rbx
0000005e  ret

00000060  ...

00000096  ...

32位

不幸的是，32位JIT编译器并不太聪明。在下面的反汇编中，请注意:

• 虽然您的代码将i与length进行比较而不是X.Length，但X没有边界检查。再次强调，这比文章中描述的行为有所改善。
• 主循环（偏移量从00000018到0000002a）对Y进行了边界检查。

反汇编

; Register assignments:
;    eax  := i
;    ecx  := X
;    edx  := Y
;    esi  := X.Length ("length" in your code, "XLength" below)

; (Prologue)
00000000  push        ebp
00000001  mov         ebp,esp
00000003  push        esi

; double sum = 0;
00000004  fldz

; int XLength = X.Length;
00000006  mov         esi,dword ptr [ecx+4]

; if (XLength != Y.Length)
;     throw new ArgumentException("X and Y must be same size");
00000009  cmp         dword ptr [edx+4],esi
0000000c  je          00000012
0000000e  fstp        st(0)
00000010  jmp         0000002F

; int i = 0;
00000012  xor         eax,eax

; if (XLength > 0)
; {
00000014  test        esi,esi
00000016  jle         0000002C

;     do
;     {
;         double temp = X[i];
00000018  fld         qword ptr [ecx+eax*8+8]

;         if (i >= Y.Length)
;             throw new IndexOutOfRangeException();
0000001c  cmp         eax,dword ptr [edx+4]
0000001f  jae         0000005A

;         sum += temp * Y[i];
00000021  fmul        qword ptr [edx+eax*8+8]
00000025  faddp       st(1),st

;         i++;
00000027  inc         eax

;     while (i < XLength);
00000028  cmp         eax,esi
0000002a  jl          00000018
; }

; return sum;
0000002c  pop         esi
0000002d  pop         ebp
0000002e  ret

0000002f  ...

0000005a  ...

总结

自2009年以来，Jitter已经得到了改进，并且64位Jitter可以生成比32位Jitter更高效的代码。

然而，如果必要的话，您始终可以通过使用不安全的代码和指针（正如svick所指出的那样）完全绕过数组边界检查。一些性能关键的基类库代码就是使用这种技术。

- Michael Liu

---

x64并不比x86更好，尽管它知道如何消除边界检查。在x86上，您可以免费获得检查，因为检查的执行与FPU指令的执行重叠。这是现代超标量处理器核心的一个特性。 - Hans Passant

@HansPassant：在这种特定情况下可能是免费的，但通常呢？ - Michael Liu

一般来说，JIT编译器知道如何消除边界检查。大致上是这样。当它们失误时，由于检查非常便宜，内存非常慢，处理器非常强大，所以通常不会有太大的影响 :) - Hans Passant

Michael非常感谢你的努力。@HansPassant我开始欣赏现代处理器的强大之处了！我的印象是，现代处理器在原始速度方面无法达到的地方，它们通过保持流水线充满、乐观调度等方面来弥补。一般来说，有没有一个好的来源可以阅读关于现代处理器的强大之处，或者这最好通过经验/参与像这样的讨论来欣赏？ - TooTone

英特尔处理器手册是一种资源，但并不是很好的资源。请搜索“Agner Fog”，他是该领域的权威人士。 - Hans Passant

你的反汇编很酷。我一直没想明白如何为.NET程序集的x64 JIT版本创建x64汇编器。你是怎么做到的？ - Mark R

Answer 3

确保不执行边界检查的一种方法是使用指针，在 C# 中可以在不安全模式下实现（这需要在项目属性中设置一个标志）：

private static unsafe double SumProductPointer(double[] X, double[] Y)
{
    double sum = 0;
    int length = X.Length;
    if (length != Y.Length)
        throw new ArgumentException("X and Y must be same size");
    fixed (double* xp = X, yp = Y)
    {
        for (int i = 0; i < length; i++)
            sum += xp[i] * yp[i];
    }
    return sum;
}

我尝试测量你的原始方法、你使用 X.Length 的方法以及我的指针代码，将它们都编译成了 .Net 4.5 下的 x86 和 x64。具体来说，我尝试计算长度为 10,000 的向量的方法，并运行该方法 10,000 次。

结果与 Michael Liu 的答案基本一致：三种方法之间没有可衡量的差异，这意味着边界检查要么未执行，要么对性能的影响微不足道。但是在 x86 和 x64 之间确实有可测量的差异：x64 大约慢了 34%。

我使用的完整代码：

static void Main()
{
    var random = new Random(42);
    double[] x = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray();
    double[] y = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray();

    // make sure JIT doesn't affect the results
    SumProduct(x, y);
    SumProductLength(x, y);
    SumProductPointer(x, y);

    var stopwatch = new Stopwatch();
    stopwatch.Start();
    for (int i = 0; i < 10000; i++)
    {
        SumProduct(x, y);
    }
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
    stopwatch.Restart();
    for (int i = 0; i < 10000; i++)
    {
        SumProductLength(x, y);
    }
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
    stopwatch.Restart();
    for (int i = 0; i < 10000; i++)
    {
        SumProductPointer(x, y);
    }
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

private static double SumProduct(double[] X, double[] Y)
{
    double sum = 0;
    int length = X.Length;
    if (length != Y.Length)
        throw new ArgumentException("X and Y must be same size");
    for (int i = 0; i < length; i++)
        sum += X[i] * Y[i];
    return sum;
}

private static double SumProductLength(double[] X, double[] Y)
{
    double sum = 0;
    if (X.Length != Y.Length)
        throw new ArgumentException("X and Y must be same size");
    for (int i = 0; i < X.Length; i++)
        sum += X[i] * Y[i];
    return sum;
}

private static unsafe double SumProductPointer(double[] X, double[] Y)
{
    double sum = 0;
    int length = X.Length;
    if (length != Y.Length)
        throw new ArgumentException("X and Y must be same size");
    fixed (double* xp = X, yp = Y)
    {
        for (int i = 0; i < length; i++)
            sum += xp[i] * yp[i];
    }
    return sum;
}

- svick

---

测试代码非常好的想法！我在一台普通的PC上运行了您的代码（x86 Family 6 Model 30 Stepping 5 GenuineIntel ~2793 Mhz），在增加迭代次数10倍后，大约得到了1200/1000/1300的结果，在.net 4上。在我的现代笔记本电脑（Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz）上，我看到了与您完全相同的结果：970/970/970。对于笔记本电脑，我尝试了.net 4和4.5，并将代码放入单独的程序集中（以防止内联），但结果是相同的。我怀疑笔记本电脑更现代的架构正在发挥作用。 - TooTone

我将数组大小减小到100，迭代次数增加到10000000。使用Core i7-2600 CPU @ 3.40GHz，x86和x64的结果分别为844/839/920和1074/1074/1153（9次运行的中位数）。SumProduct和SumProductLength是共同获胜者（它们的本地代码几乎完全相同），而SumProductPointer则失败了。 - Michael Liu

@MichaelLiu 我刚在一台3.30GHz的Core i5-2500上运行了我的代码，没有看到任何明显的差异：所有三个运行时间大约为1100毫秒（多次运行）。我认为有趣的是，在我们看到差异的系统中，本地代码表现最差。在我写的模拟C++中边界检查问题中有一些相关评论。 - TooTone

Answer 4

首先，我想感谢在这篇文章中发表观点的每个人，从原始的OP到提供极其详细和深入解释的人。我真的非常喜欢阅读现有的答案。由于已经有了关于循环如何以及为什么以它们所做的方式的丰富理论，因此我想提供一些经验性（根据某些定义权威的）测量：

结论：

• foreach循环比for循环更快。
• 局部变量比数组.Length属性更快。
• 使用unsafe fixed进行GC固定并不比普通的for循环更快。

基准测试代码：

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

namespace demo
{
    class MainClass
    {
        static bool ByForArrayLength (byte[] data)
        {
            for (int i = 0; i < data.Length; i++)
                if (data [i] != 0)
                    return false;
            return true;
        }

        static bool ByForLocalLength (byte[] data)
        {
            int len = data.Length;
            for (int i = 0; i < len; i++)
                if (data [i] != 0)
                    return false;
            return true;
        }

        static unsafe bool ByForUnsafe (byte[] data)
        {
            fixed (byte* datap = data)
            {
                int len = data.Length;
                for (int i = 0; i < len; i++)
                    if (datap [i] != 0)
                        return false;
                return true;
            }
        }

        static bool ByForeach (byte[] data)
        {
            foreach (byte b in data)
                if (b != 0)
                    return false;
            return true;
        }

        static void Measure (Action work, string description)
        {
            GCSettings.LatencyMode = GCLatencyMode.LowLatency;
            var watch = Stopwatch.StartNew ();
            work.Invoke ();
            Console.WriteLine ("{0,-40}: {1} ms", description, watch.Elapsed.TotalMilliseconds);
        }

        public static void Main (string[] args)
        {
            byte[] data = new byte[256 * 1024 * 1024];
            Measure (() => ByForArrayLength (data), "For with .Length property");
            Measure (() => ByForLocalLength (data), "For with local variable");
            Measure (() => ByForUnsafe (data), "For with local variable and GC-pinning");
            Measure (() => ByForeach (data), "Foreach loop");
        }
    }
}

结果：（使用Mono运行时）

$ mcs Program.cs -optimize -unsafe
For with .Length property               : 440,9208 ms
For with local variable                 : 333,2252 ms
For with local variable and GC-pinning  : 330,2205 ms
Foreach loop                            : 280,5205 ms

- ArekBulski

---

那不是从指针开始循环遍历数组的正确方式。 - Orestis P.