謝辞
今回、このまとめを上梓するに当たり、多くの方からベンチマークデータの提供を受けました。
これらの提供がない限りこのまとめを書くことは出来なかったので、ここで心からお礼申し上げます。
何をしたのか
とっても簡単。
.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になっているので1 、先の推測よりこちらの理由の方が確度が高いかと考えた。
Assemblyを素朴に眺めてわかること ～とりあえずのまとめに変えて～
さて、このようにIntSumforeachの方が、レジスタへの代入とは言え、冗長な処理を行っている。それもこのベンチマークではその冗長な処理が900,000,000回も発生するので、IntSumForeachの方が遅く、IntSumForの方が速いのではないかと考えた2。
次回以降で、先の通り、実際に提供を受けたベンチマークデータを元に考察していこうかと思います。