我对 .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%,这值得关注。我在这个问题上进行了更多的调查,为什么在某些机器上添加额外的循环检查会有很大的差别,在其他机器上则有很小的差别?有趣的是,在不同的机器上,边界检查的成本似乎存在显著差异。
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