c# - .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 中的边界检查，我找到的最好的文章是 Array Bounds Check Elimination in the CLR在 MSDN 上(也在关于启用优化的重要性的 stack overflow answer 中引用)。

这是从 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%，值得关心。我在这个问题上做了更多调查，Why does adding extra check in loop make big difference on some machines, and small difference on others? .有趣的是，边界检查的成本似乎在不同的机器上差异很大。

Answer 1

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

• 边界检查由 cmp/jae 指令对组成，在现代 CPU 架构上被融合到单个微操作中(术语是“宏操作融合”)。比较和分支经过高度优化。

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

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

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