低レベルのアルゴリズムが .net でどれほど効率的になるかに興味があります。将来的には、C++ ではなく C# でより多くのコードを記述できるようにしたいと考えていますが、1 つの障害は、ループと配列へのランダム アクセスで発生する .net の境界チェックです。
動機付けとなる例は、2 つの配列内の対応する要素の積の合計を計算する関数です (これは 2 つのベクトルの内積です)。
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 での境界チェックに関して、私が見つけた最良の記事は、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++ で、境界チェックを 1 回行う SumProduct の時間を比較しました
for(int i=0; i<n; ++i) sum += v1[i]*v2[i];
2 つの境界チェックを行う別のバージョンに対して
for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];
2 番目のバージョンの方が遅いことがわかりましたが、約 3.5% (Visual Studio 2010、最適化されたビルド、既定のオプション) だけでした。しかし、C# では、境界チェックが 3 つある可能性があることに気付きました。1 つは明示的 (この質問の冒頭のi < length
関数内)、2 つは暗黙的 ( and ) です。そこで、3 つの境界チェックを使用して 3 つ目の C++ 関数をテストしました。static void SumProduct(double[] X, double[] Y)
X[i]
Y[i]
for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];
これは最初のものより 35% 遅くなりましたが、これは気にする価値があります。この質問でさらに調査を行いました。追加のチェックインループを追加すると、一部のマシンでは大きな違いが生じ、他のマシンでは小さな違いが生じるのはなぜですか? . 興味深いことに、境界チェックのコストはマシンによって大きく異なるようです。