謝辞

今回、このまとめを上梓するに当たり、多くの方からベンチマークデータの提供を受けました。

これらの提供がない限りこのまとめを書くことは出来なかったので、ここで心からお礼申し上げます。

何をしたのか

とっても簡単。

.NET Core上のC#で配列のループ処理に対して、for使うが速いかforeach使うが速いかどっちなの?と言う話。

御託は良いから、結果よこせって人はこっからジャンプ

今回考察していること

このセクションでは以下の考察を行った。

ベンチマークコードの提示
上記コードのILの考察
そのILがJITでAssemblyになった結果の考察

また、提供を受けた様々なCPUでベンチマークを実行した結果の提示を元に考察した。

ベンチマークコード

BenchmarkDotNetで以下のコードを書き、多くの方から、様々なCPUの結果を頂きました。

using BenchmarkDotNet.Attributes;
using System.Linq;

namespace ArrayLoopSurvey
{
    [CsvMeasurementsExporter]
    [CsvExporter]
    [DisassemblyDiagnoser]
    public class IntArrayAccessBenchmark
    {
        private readonly int[] _array = Enumerable.Range(0, 900_000_000).ToArray();

        [Benchmark]
        public int IntSumFor()
        {
            int[] ary = _array;
            int accum = 0;
            for (int i = 0; i < ary.Length; i++) accum += ary[i];
            return accum;
        }


        [Benchmark]
        public int IntSumForeach()
        {
            int accum = 0;
            foreach (var i in _array) accum += i;
            return accum;
        }
    }
}

使ってる配列のサイズがバカみたいにでかいのは、BenchmarkDotNetでIterationを1にしたかったからだけど、正直やりすぎたと思うし、もしかしたらこれが擾乱要因担ったかも知れないと反省。

ILだとどうなるか

IntSumForメソッドをコンパイルした結果は以下の通り。

    .method public hidebysig 
        instance int32 IntSumFor () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 31 (0x1f)
        .maxstack 3
        .locals init (
            [0] int32[],
            [1] int32,
            [2] int32
        )

        IL_0000: ldarg.0
        IL_0001: ldfld int32[] IntArrayAccessBenchmark::_array
        IL_0006: stloc.0
        IL_0007: ldc.i4.0
        IL_0008: stloc.1
        IL_0009: ldc.i4.0
        IL_000a: stloc.2
        // sequence point: hidden
        IL_000b: br.s IL_0017
        // loop start (head: IL_0017)
            IL_000d: ldloc.1
            IL_000e: ldloc.0
            IL_000f: ldloc.2
            IL_0010: ldelem.i4
            IL_0011: add
            IL_0012: stloc.1
            IL_0013: ldloc.2
            IL_0014: ldc.i4.1
            IL_0015: add
            IL_0016: stloc.2

            IL_0017: ldloc.2
            IL_0018: ldloc.0
            IL_0019: ldlen
            IL_001a: conv.i4
            IL_001b: blt.s IL_000d
        // end loop

        IL_001d: ldloc.1
        IL_001e: ret
    } // end of method IntArrayAccessBenchmark::IntSumFor

また、IntSumForeachは以下の通り。

   .method public hidebysig 
        instance int32 IntSumForeach () cil managed 
    {
        // Method begins at RVA 0x207c
        // Code size 33 (0x21)
        .maxstack 2
        .locals init (
            [0] int32,
            [1] int32[],
            [2] int32,
            [3] int32
        )

        IL_0000: ldc.i4.0
        IL_0001: stloc.0
        IL_0002: ldarg.0
        IL_0003: ldfld int32[] IntArrayAccessBenchmark::_array
        IL_0008: stloc.1
        IL_0009: ldc.i4.0
        IL_000a: stloc.2
        // sequence point: hidden
        IL_000b: br.s IL_0019
        // loop start (head: IL_0019)
            IL_000d: ldloc.1
            IL_000e: ldloc.2
            IL_000f: ldelem.i4
            IL_0010: stloc.3
            IL_0011: ldloc.0
            IL_0012: ldloc.3
            IL_0013: add
            IL_0014: stloc.0
            // sequence point: hidden
            IL_0015: ldloc.2
            IL_0016: ldc.i4.1
            IL_0017: add
            IL_0018: stloc.2

            IL_0019: ldloc.2
            IL_001a: ldloc.1
            IL_001b: ldlen
            IL_001c: conv.i4
            IL_001d: blt.s IL_000d
        // end loop

        IL_001f: ldloc.0
        IL_0020: ret
    } // end of method IntArrayAccessBenchmark::IntSumForeach

ここで注目すべきなのは、IntSumForeachの方が、int32型のローカル変数が多い。

これは、foreach(var i in _array)のiに相当していて、1度iに代入してからそれをaccumに加算している形になる。

x64ASMだとどうなるか

さて、ILを検証してきたけど、実際問題ILが直接解釈されて実行されるわけじゃなく、最終的にJITされた結果、x64アセンブリになる。

ここでは、JITされた実際の実行コードを検証してみたい。

IntSumForは以下の通り。

; ArrayLoopSurvey.IntArrayAccessBenchmark.IntSumFor()
       mov     rax,qword ptr [rcx+8]
       xor     edx,edx
       xor     ecx,ecx
       mov     r8d,dword ptr [rax+8]
       test    r8d,r8d
       jle     M00_L01
M00_L00:
       movsxd  r9,ecx
       add     edx,dword ptr [rax+r9*4+10h]
       inc     ecx
       cmp     r8d,ecx
       jg      M00_L00
M00_L01:
       mov     eax,edx
; Total bytes of code 34

また、IntSumforeachは以下の通り。

; ArrayLoopSurvey.IntArrayAccessBenchmark.IntSumForeach()
       xor     eax,eax
       mov     rdx,qword ptr [rcx+8]
       xor     ecx,ecx
       mov     r8d,dword ptr [rdx+8]
       test    r8d,r8d
       jle     M00_L01
M00_L00:
       movsxd  r9,ecx
       mov     r9d,dword ptr [rdx+r9*4+10h]
       add     eax,r9d
       inc     ecx
       cmp     r8d,ecx
       jg      M00_L00
M00_L01:
       ret
; Total bytes of code 36

さて、ここで、気になるのは、先のILであった、SumForeachのiへの代入が実際JITされたらどうなるのか?ってことだけど、実はしっかり残ってる。

IntSumForを眺めると、add edx,dword ptr [rax+r9*4+10h]で、直接配列の要素をedxレジスタに加算してる。

他方、IntSumforeachの場合、mov r9d,dword ptr [rdx+r9*4+10h]と、r9dレジスタに1度配列の要素を代入した後、add eax,r9dでeaxレジスタに加算している。

Intermission : ecxがコピーされてる件

今回の考察には全く関係ないけど、forでもforeachでも、カウンタ相当のレジスタはecxとなってる。けれど、どちらの例でも、movsxc (r8/r9),ecxと他のレジスタへコピーされてから、コピー先の値を伴って配列の要素へのアクセスを行っている。

このようなことをなぜするのか、知人と議論したところ、1度コピーしてそれをアドレス指定に使うことで、続く、inc ecxと操作が独立となって、パイプラインにうまく収まるコトを企図しているのではないかという知見を得た。

従って、メモリへのアクセスはキャッシュにヒットするか否かで大きくアクセスコストが変化するので、レジスタ間のコピーコストを支払ってでも独立させておいた方が有利なのではなかろうかと考えた。

追記

このエントリを公開後、知人から、
ループカウンタは32bit、アドレスのインデックスアクセスは64bitなので、別管理にする必要があるのでは無いかと言う指摘を受けた。

指摘を受けた後、確かにmovでは無く、movsxdになっているので¹ 、先の推測よりこちらの理由の方が確度が高いかと考えた。

Assemblyを素朴に眺めてわかること～とりあえずのまとめに変えて～

さて、このようにIntSumforeachの方が、レジスタへの代入とは言え、冗長な処理を行っている。それもこのベンチマークではその冗長な処理が900,000,000回も発生するので、IntSumForeachの方が遅く、IntSumForの方が速いのではないかと考えた²。

次回以降で、先の通り、実際に提供を受けたベンチマークデータを元に考察していこうかと思います。

そりゃ、ecxは32bit転送先のr~は64bitなので、拡張転送は必須じゃある。 ↩
そして、その考えはもろくも崩れ去るわけだけどw ↩

C#で配列に対してforとforeachどっちが速いの? ～コンパイル結果を考察する～

謝辞