数组边界检查.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.我错了和/或有没有办法编写我的代码以允许编译器帮助我？

更多详情

有许多效率论据支持和反对使用特定语言,尤其是最好专注于"大O"算法成本而不是比例常数,而更高级别的语言可以帮助您实现这一目标.关于.net中边界检查的主题,我发现的最好的文章是MSDN上的CLR中的数组边界检查消除(也在关于启用优化的重要性的堆栈溢出答案中引用).

这可以追溯到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#中可能有三个边界检查.一个显式(i < length在static void SumProduct(double[] X, double[] Y)这个问题开头的函数中)和两个隐式(X[i]和Y[i]).所以我测试了第三个C++函数,有三个边界检查

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

这比第一次慢了35%,值得关注.我在这个问题上做了一些调查,为什么在一些机器上添加额外的检查循环会产生很大的不同,而在其他机器上却有很小的不同？.有趣的是,似乎边界检查的成本在不同的机器上有很大差异.

Answer 1

边界检查无关紧要,因为:

• 边界检查包含一个cmp/ jae指令对,它融合到现代CPU架构上的单个微操作中(术语是"宏操作融合").比较和分支是非常高度优化的.

• 边界检查是一个前向分支,它将被静态预测为不被采用,也降低了成本.分支永远不会被采取.(如果它被采用,无论如何都会抛出异常,因此错误预测成本变得完全无关紧要)

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

内存访问可能是您的瓶颈,因此删除边界检查等微优化效果将消失.

Answer 2

64位

64位抖动可以很好地消除边界检查(至少在简单的场景中).我return sum;在您的方法结束时添加,然后在发布模式下使用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的向量的方法,并运行方法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;
}