c# - このループをより速く実行するにはどうすればよいですか?

Question

私はこの単純なループを持っています:

int[] array = new int[100000000];
int sum = 0;
for (int i = 0; i < array.Length; i++)
    sum += array[i];

そのパフォーマンスを C++ バージョンと比較しました。非常に単純なコードであり、その場合は範囲チェックが省略されているため、パフォーマンスはほぼ同じになるはずです。しかし、C++ バージョンの方がほぼ 3 倍高速であることが判明しました。そのため、C# の安全でないバージョンを実装しましたが、パフォーマンスはさらに低下しました。Resharper は、次のようにループを linq 式に変換することを提案しています。

sum = array.Sum();

そのコードは、C# の元のループより何倍も遅い

このループのパフォーマンスを改善するためにできることが他にあるかどうか誰か教えてもらえますか~~(64 ビットバージョンにコンパイルすることなく - 2 倍高速です)。~~

すべてのテストは 32 ビットリリースバージョンで行われ、デバッガーなしで実行されます。

編集：小さな修正。64ビットバージョンは、intではなくdoubleで2倍高速です

score 15 · Accepted Answer

var watch = new Stopwatch();

int[] array = new int[100000000];
for (int i = 0; i < array.Length; i++)
{
    array[i] = 1;
}

watch.Restart();
int sum = 0;
for (int i = 0; i < array.Length; i++)
    sum += array[i];
Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

sum = 0;
watch.Restart();
sum = array.Sum();
Console.WriteLine("linq sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

sum = 0;
watch.Restart();
int length = array.Length;
for (int i = 0; i < length; i++)
    sum += array[i];
Console.WriteLine("for loop fixed:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

sum = 0;
watch.Restart();
foreach (int i in array)
{
    sum += i;
}
Console.WriteLine("foreach sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

sum = 0;
watch.Restart();
sum = array.AsParallel().Sum();
Console.WriteLine("linq parallel sum:" + watch.ElapsedMilliseconds + "ms, result:" + sum);

Linq Parallel は、少なくとも私のマシンでは高速になっているようです。

長さを固定しても大した問題ではありませんが、約 10% 改善されます

実際にできることはあまりありません。アンマネージ C コードの方が常に高速です。

私のPCでの結果は次のとおりです。

for loop:      241ms, result:100000000
linq sum:      559ms, result:100000000
for loop fixed:237ms, result:100000000
foreach sum:   295ms, result:100000000
linq parallel: 205ms, result:100000000

score 10 · Accepted Answer

ループを 2 ～ 8 回ほど広げます。どれが最適かを測定します。.NET JIT は最適化が不十分なため、その作業の一部を行う必要があります。

unsafeJIT は配列境界チェックを最適化できなくなるため、おそらく同様に追加する必要があります。

複数の合計変数に集計することもできます。

int sum1 = 0, sum2 = 0;
for (int i = 0; i < array.Length; i+=2) {
    sum1 += array[i+0];
    sum2 += array[i+1];
}

addすべての命令が独立しているため、命令レベルの並列性が向上する可能性があります。

は自動的i+0に最適化されiます。

私はそれをテストし、約30％削りました。

繰り返すとタイミングが安定します。コード：

        Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;

        var watch = new Stopwatch();

        int[] array = new int[500000000];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = 1;
        }

        //warmup
        {
            watch.Restart();
            int sum = 0;
            for (int i = 0; i < array.Length; i++)
                sum += array[i];
        }

        for (int i2 = 0; i2 < 5; i2++)
        {
            {
                watch.Restart();
                int sum = 0;
                for (int i = 0; i < array.Length; i++)
                    sum += array[i];
                Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
            }

            {
                watch.Restart();
                fixed (int* ptr = array)
                {
                    int sum = 0;
                    var length = array.Length;
                    for (int i = 0; i < length; i++)
                        sum += ptr[i];
                    Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + sum);
                }
            }

            {
                watch.Restart();
                fixed (int* ptr = array)
                {
                    int sum1 = 0;
                    int sum2 = 0;
                    int sum3 = 0;
                    int sum4 = 0;
                    var length = array.Length;
                    for (int i = 0; i < length; i += 4)
                    {
                        sum1 += ptr[i + 0];
                        sum2 += ptr[i + 1];
                        sum3 += ptr[i + 2];
                        sum4 += ptr[i + 3];
                    }
                    Console.WriteLine("for loop:" + watch.ElapsedMilliseconds + "ms, result:" + (sum1 + sum2 + sum3 + sum4));
                }
            }

            Console.WriteLine("===");
        }

さらにいじってみると、複数の集計変数は何もしないことがわかります。ただし、ループを展開すると大幅に改善されました。Unsafe は何もしませんでした (それがかなり必要とされるアンロールの場合を除いて)。2 回の展開は 4 回と同じです。

これを Core i7 で実行します。

score 7 · Accepted Answer

最初に、次のようなマイクロベンチマークに関するいくつかの一般的な注意事項を示します。

ここでのタイミングは非常に短いため、JIT 時間が重要になる可能性があります。並列ループには、最初に呼び出されたときにのみ JIT される匿名のデリゲートが含まれているため、これは重要です。ForEachそのため、JIT 時間は、ベンチマークが初めて実行されるタイミングに含まれます。
コードのコンテキストも重要です。JITter は、小さな関数を最適化することで、より良い仕事をすることができます。ベンチマークコードを独自の関数に分離すると、パフォーマンスに大きな影響を与える可能性があります。

コードを高速化するための 4 つの基本的な手法があります (純粋な CLR を維持する場合)。

それを並列化します。これは明らかです。
ループを展開します。これにより、2 回以上の繰り返しごとに比較を行うだけで、命令の数が削減されます。
安全でないコードの使用。この場合、主な問題 (アレイの範囲チェック) が最適化されているため、これはあまりメリットがありません。
コードをより最適化できるようにします。これを行うには、実際のベンチマークコードを別のメソッドに配置します。

並列コードは次のとおりです。

var syncObj = new object();
Parallel.ForEach(Partitioner.Create(0, array.Length),
    () => 0,
    (src, state, partialSum) => {
        int end = src.Item2;
        for (int i = src.Item1; i < end; i++)
            partialSum += array[i];
        return partialSum;
    },
    partialSum => { lock (syncObj) { s += partialSum; } });

Partitionerクラスは名前System.Collections.Concurrent空間に存在します。

私のマシン (i7 950、8 つの論理コア) では、得られたタイミングは次のとおりです。

For loop: 196.786 ms
For loop (separate method): 72.319 ms
Unrolled for loop: 196.167 ms
Unrolled for loop (separate method): 67.961 ms
Parallel.Foreach (1st time): 48.243 ms
Parallel.Foreach (2nd time): 26.356 ms

32 ビットコードと 64 ビットコードの間に大きな違いはありませんでした。

score 0 · Accepted Answer

安全でない並列コードもパフォーマンスを向上させるはずです。詳細については、この記事をご覧ください。

それを最適化します。

c# - このループをより速く実行するにはどうすればよいですか?

7 に答える 7

Related

Reference