数组边界检查.NET 4及以上的效率

我感兴趣的是如何有效的低级algorithm可以在.net。 我想让我们select在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边界检查。 我错了，还是有没有办法写我的代码，让编译器帮我？

更多细节

对于使用特定的语言有很多的效率论点和反对意见，最重要的是专注于“大O”algorithm成本而不是比例常数，而更高级别的语言可以帮助你做到这一点。 关于.net中边界检查的问题，我发现最好的文章是MSDN CLR中的数组边界检查消除 （在启用优化的重要性中还引用了堆栈溢出问题 ）。

这从2009年开始，所以我想知道自那以后事情是否发生了重大变化。 此外，文章揭示了一些真正的细微之处，如果仅仅是这个原因，我会欢迎一些专家的build议。

例如，看起来在上面的代码中，我最好写i< X.Length而不是i < length 。 另外，我还天真地认为，对于一个单一数组的algorithm，编写一个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)函数static void SumProduct(double[] X, double[] Y) i < length ）和两个隐式的（ X[i]和Y[i] ）。 所以我testing了第三个C ++函数，用三个边界检查

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

这比第一次慢了35％，值得关注。 我在这个问题上做了一些更多的调查， 为什么在循环中添加额外的检查在一些机器上有很大的差别，而在其他机器上有小的差别？ 。 有趣的是，似乎边界检查的代价在不同的机器上变化很大。

Answer 1

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

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

• 边界检查是一个前向分支，这将被静态预测为不被采用，也降低了成本。 该分支将永远不会被采取。 （如果有的话，反正也会抛出exception，所以误预测成本变得毫不相关）

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

内存访问可能会成为你的瓶颈，所以像去除边界检查这样的效果微观优化就会消失。

Answer 2

64位

64位抖动在消除边界检查方面做得很好（至less在简单的情况下）。 我加了return sum; 在方法的末尾，然后在Release模式下使用Visual Studio 2010编译程序。 在下面的反汇编（我用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位抖动并不那么聪明。 在下面的反汇编中，请注意：

• X没有边界检查，即使你的代码比较i length而不是X.Length 。 同样，这是对文章中描述的行为的改进。
• 主循环（偏移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年以来抖动得到了改善，64位抖动可以产生比32位抖动更高效的代码。

如果有必要的话，你总是可以通过使用不安全的代码和指针来完全绕过数组边界检查（如svick指出的那样）。 基本类库中的一些性能关键代码使用此技术。

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的向量的方法，运行方法10000次。

这个结果与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; }