c# - for ループでの配列境界チェックの最適化

Question

        var ar = new int[500000000];

        var sw = new Stopwatch();
        sw.Start();

        var length = ar.Length;
        for (var i = 0; i < length; i++)
        {
            if (ar[i] == 0);
        }

        sw.Stop();

sw.ElapsedMilliseconds: ~2930ms

        var ar = new int[500000000];

        var sw = new Stopwatch();
        sw.Start();

        for (var i = 0; i < ar.Length; i++)
        {
            if (ar[i] == 0);
        }

        sw.Stop();

sw.ElapsedMilliseconds: ~3520ms

Win8x64、VS12、.NET4.5、リリースビルド、「コードの最適化」オン。

私の知る限り、配列境界チェックの最適化により、2 番目のアプローチの方が高速です。何か不足していますか？

Answer 1

また、デバッガーの外部でWin8 x64、.NET 4.5、リリースビルドを使用しています（これは重要なものです）。私は得る：

0: 813ms vs 421ms
1: 439ms vs 420ms
2: 440ms vs 420ms
3: 431ms vs 429ms
4: 433ms vs 427ms
5: 424ms vs 437ms
6: 427ms vs 434ms
7: 430ms vs 432ms
8: 432ms vs 435ms
9: 430ms vs 430ms
10: 427ms vs 418ms
11: 422ms vs 421ms
12: 434ms vs 420ms
13: 439ms vs 425ms
14: 426ms vs 429ms
15: 426ms vs 426ms
16: 417ms vs 432ms
17: 442ms vs 425ms
18: 420ms vs 429ms
19: 420ms vs 422ms

最初のものはJIT/「融合」コストを支払いますが、全体的にはほぼ同じです（各列のいくつかはより速く見えますが、全体的に話すことはあまりありません）。

using System;
using System.Diagnostics;
static class Program
{
    static void Main()
    {
        var ar = new int[500000000];

        for (int j = 0; j < 20; j++)
        {
            var sw = Stopwatch.StartNew();
            var length = ar.Length;
            for (var i = 0; i < length; i++)
            {
                if (ar[i] == 0) ;
            }

            sw.Stop();
            long hoisted = sw.ElapsedMilliseconds;

            sw = Stopwatch.StartNew();
            for (var i = 0; i < ar.Length; i++)
            {
                if (ar[i] == 0) ;
            }
            sw.Stop();
            long direct = sw.ElapsedMilliseconds;

            Console.WriteLine("{0}: {1}ms vs {2}ms", j, hoisted, direct);
        }
    }
}

Answer 2

これをさらに調査したところ、境界チェック除去の最適化の効果を実際に示すベンチマークを作成するのは非常に難しいことがわかりました。

まず、古いベンチマークの問題:

• 逆アセンブリは、JIT コンパイラが最初のバージョンも最適化できることを示しました。それは私にとって驚きでしたが、分解は嘘をつきません。もちろん、これはこのベンチマークの目的を完全に無効にします。修正:長さを関数の引数として取ります。
• 配列が大きすぎるため、キャッシュ ミスが発生し、信号に多くのノイズが追加されます。修正:短い配列を使用しますが、複数回ループします。

しかし今、本当の問題:あまりにも巧妙なことをしているのです。ループの長さが関数の引数に由来する場合でも、内側のループには配列境界テストはありません。生成されるコードは異なりますが、内側のループは基本的に同じです。完全ではありませんが (異なるレジスターなど)、同じパターンに従います。

_loop: mov eax, [somewhere + index]
       add index, 4
       cmp index, end
       jl _loop

生成されたコードの最も重要な部分に大きな違いがないため、実行時間に大きな違いはありません。

Answer 3

答えは、ガベージコレクターが実行されており、タイミングが変更されていることだと思います。

免責事項:コンパイル可能な例を投稿していないため、OP コードのコンテキスト全体を確認できません。配列を再利用するのではなく、再割り当てしていると思います。そうでない場合、これは正解ではありません。

次のコードを検討してください。

using System;
using System.Diagnostics;

namespace Demo
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var ar = new int[500000000];
            test1(ar);
            //ar = new int[500000000]; // Uncomment this line.
            test2(ar);
        }

        private static void test1(int[] ar)
        {
            var sw = new Stopwatch();
            sw.Start();

            var length = ar.Length;
            for (var i = 0; i < length; i++)
            {
                if (ar[i] == 0);
            }

            sw.Stop();                
            Console.WriteLine("test1 took " + sw.Elapsed);
        }

        private static void test2(int[] ar)
        {
            var sw = new Stopwatch();
            sw.Start();

            for (var i = 0; i < ar.Length; i++)
            {
                if (ar[i] == 0);
            }

            sw.Stop();
            Console.WriteLine("test2 took " + sw.Elapsed);
        }
    }
}

私のシステムでは、次のように出力されます。

test1 took 00:00:00.6643788
test2 took 00:00:00.3516378

マークされた行のコメントを外すと// Uncomment this line.、タイミングが次のように変わります。

test1 took 00:00:00.6615819
test2 took 00:00:00.6806489

これは、GC が前の配列を収集するためです。

[編集] JIT の起動コストを回避するために、テスト全体をループに入れました。

for (int i = 0; i < 8; ++i)
{
    test1(ar);
    ar = new int[500000000]; // Uncomment this line.
    test2(ar);
}

そして、2番目の配列割り当てをコメントアウトした結果は次のとおりです。

test1 took 00:00:00.6437912
test2 took 00:00:00.3534027
test1 took 00:00:00.3401437
test2 took 00:00:00.3486296
test1 took 00:00:00.3470775
test2 took 00:00:00.3675475
test1 took 00:00:00.3501221
test2 took 00:00:00.3549338
test1 took 00:00:00.3427057
test2 took 00:00:00.3574063
test1 took 00:00:00.3566458
test2 took 00:00:00.3462722
test1 took 00:00:00.3430952
test2 took 00:00:00.3464017
test1 took 00:00:00.3449196
test2 took 00:00:00.3438316

2 番目の配列割り当てを有効にすると、次のようになります。

test1 took 00:00:00.6572665
test2 took 00:00:00.6565778
test1 took 00:00:00.3576911
test2 took 00:00:00.6910897
test1 took 00:00:00.3464013
test2 took 00:00:00.6638542
test1 took 00:00:00.3548638
test2 took 00:00:00.6897472
test1 took 00:00:00.4464020
test2 took 00:00:00.7739877
test1 took 00:00:00.3835624
test2 took 00:00:00.8432918
test1 took 00:00:00.3496910
test2 took 00:00:00.6471341
test1 took 00:00:00.3486505
test2 took 00:00:00.6527160

GC のため、test2 は一貫して時間がかかることに注意してください。

残念ながら、GC はタイミングの結果をほとんど意味のないものにします。

たとえば、テスト コードを次のように変更するとします。

for (int i = 0; i < 8; ++i)
{
    var ar = new int[500000000];
    GC.Collect();
    test1(ar);
    //ar = new int[500000000]; // Uncomment this line.
    test2(ar);
}

行をコメントアウトすると、次のようになります。

test1 took 00:00:00.6354278
test2 took 00:00:00.3464486
test1 took 00:00:00.6672933
test2 took 00:00:00.3413958
test1 took 00:00:00.6724916
test2 took 00:00:00.3530412
test1 took 00:00:00.6606178
test2 took 00:00:00.3413083
test1 took 00:00:00.6439316
test2 took 00:00:00.3404499
test1 took 00:00:00.6559153
test2 took 00:00:00.3413563
test1 took 00:00:00.6955377
test2 took 00:00:00.3364670
test1 took 00:00:00.6580798
test2 took 00:00:00.3378203

そして、コメントを外して：

test1 took 00:00:00.6340203
test2 took 00:00:00.6276153
test1 took 00:00:00.6813719
test2 took 00:00:00.6264782
test1 took 00:00:00.6927222
test2 took 00:00:00.6269447
test1 took 00:00:00.7010559
test2 took 00:00:00.6262000
test1 took 00:00:00.6975080
test2 took 00:00:00.6457846
test1 took 00:00:00.6796235
test2 took 00:00:00.6341214
test1 took 00:00:00.6823508
test2 took 00:00:00.6455403
test1 took 00:00:00.6856985
test2 took 00:00:00.6430923

このテストの教訓は次のとおりだと思います。この特定のテストの GC は、コードの残りの部分と比較して非常に大きなオーバーヘッドであるため、タイミングの結果を完全にゆがめており、何の意味も信頼できません。

Answer 4

2番目のプロパティを呼び出しているため、遅くなりますar.Length