[前提] C# のコンパイルと JIT コンパイル
C# --> [コンパイル] --> IL -> [JIT] --> バイナリ の流れを知ってる人は読み飛ばしてください
for
の最適化の話をする前に、C#のソースコードが実行可能バイナリ (アセンブリ) にコンパイルされるまでの流れをおさえておきます。
C# はJava等と同じで中間言語にコンパイルされます。Java が Java 仮想マシン (JVM; Java Virtual Machine) 上で動く Java バイトコードにコンパイルされるように、C# は .NET 上で動く MSIL (通称 IL; Microsoft Intermediate Language) にコンパイルされます。その後、実行時に実行プラットフォーム (OSとかCPUのアーキテクチャ) に合わせた実行可能バイナリに再度コンパイルされることで実行されます。
この IL からアセンブリへのコンパイルのことを JIT コンパイル (Just in Time Compile) と呼びます。
C# で作られたソフトウェア (Windows の場合 exe ファイル) はこの IL の状態であるため、プラットフォームによらず同一のプログラムファイルで実行できます。つまりC#製の exe の場合、Windows で動かしている exe ファイルをそのまま Mac にコピーすれば動きます。(まあモノに依りますが。monoだけに)
で、なぜかと言うと IL は .NET という仮想マシン向けの命令だからです。プラットフォーム間の差異は .NET が吸収してくれるので IL はプラットフォーム非依存になります。(Javaバイトコードが JVM という仮想マシン上で動くのと全く同じです。と言うか C# は Java の真似して作られた)
わざわざ JIT コンパイルという二度手間を踏んでまで中間言語にコンパイルする意味は、いろいろメリットがあるからなんですが、ここではその話は省略します。
あと余談ですが、Unity の iOS 向けビルド(など)で行われる IL2CPP は 事前コンパイル (AOT: Ahead of Time compile) の一種で、本来実行時に JIT コンパイルされる IL を、あらかじめアセンブリまでコンパイルしてしまうものです。メリット・デメリット双方あります。
for
の配列アクセスの最適化
本題です。
以下に簡単なサンプルコードを書きました。2種類のやり方でint
配列の合計をfor
で回して計算しているだけのメソッドです。
public class C { public int L = 10000000; public int M1() { var array = new int[L]; int sum = 0; for(int i = 0; i < array.Length; i++) { sum += array[i]; } return sum; } public int M2() { var array = new int[L]; int sum = 0; for(int i = 0; i < L; i++) { sum += array[i]; } return sum; } }
配列の要素は全て0なのでどっちも答えは0ですが、計算に特に意味はありません。2つのメソッドの違いはfor
の終了条件に配列のLength
プロパティを使うか否かだけです。
結果から言うと、M1()
メソッドの方が実行速度が速いです。JIT コンパイル時に最適化がかかるからです。
実際に逆アセンブルしてアセンブリを見てみましょう。(C#のコンパイルは Release ビルド、アセンブリはAMD64)。逆アセンブルツールはいろいろありますが、パッと簡単なコードの結果を見たいだけの時は sharplab がすごく簡単です。ソースをコピペして2秒で見れます。今回もこれを使いました。
; Core CLR v4.700.19.51502 (coreclr.dll) on amd64. C..ctor() L0000: mov dword [rcx+0x8], 0x989680; L = 10000000 L0007: ret ; return C.M1() L0000: sub rsp, 0x28 ; L0004: mov edx, [rcx+0x8] ; L0007: movsxd rdx, edx ; L000a: mov rcx, 0x7ffec35ef000 ; L0014: call 0x7fff230847e0 ; array = new int[L] L0019: xor edx, edx ; sum = 0 L001b: xor ecx, ecx ; i = 0 L001d: mov r8d, [rax+0x8] ; L0021: test r8d, r8d ; if (i >= L) L0024: jle L0035 ; goto -------┐ L0026: movsxd r9, ecx ; <----|--┐ L0029: add edx, [rax+r9*4+0x10] ; sum += array[i] | | L002e: inc ecx ; i += 1 | | L0030: cmp r8d, ecx ; if (i < L) | | L0033: jg L0026 ; goto -------|--┘ L0035: mov eax, edx ; <----┘ L0037: add rsp, 0x28 ; L003b: ret ; return sum C.M2() L0000: push rsi ; L0001: sub rsp, 0x20 ; L0005: mov esi, [rcx+0x8] ; L0008: movsxd rdx, esi ; L000b: mov rcx, 0x7ffec35ef000 ; L0015: call 0x7fff230847e0 ; array = new int[L] L001a: xor edx, edx ; sum = 0 L001c: xor ecx, ecx ; i = 0 L001e: test esi, esi ; if (i >= L) L0020: jle L0039 ; goto ---------------┐ L0022: mov r8d, [rax+0x8] ; | L0026: cmp ecx, r8d ; if (i < 0 or i >= L) <--|--┐ L0029: jae L0041 ; goto ----------┐ | | L002b: movsxd r9, ecx ; | | | L002e: add edx, [rax+r9*4+0x10] ; sum += array[i] | | | L0033: inc ecx ; i += 1 | | | L0035: cmp ecx, esi ; if (i < L) | | | L0037: jl L0026 ; goto ----------|----|--┘ L0039: mov eax, edx ; <------|----┘ L003b: add rsp, 0x20 ; | L003f: pop rsi ; | L0040: ret ; return sum | L0041: call 0x7fff231aef00 ; throw Exception <--┘ L0046: int3 ;
アセンブリを眺めてスラスラ読める宇宙人の方はいいですが、人間には厳しいので、隣に高級言語的に意味ある部分に疑似コードを書き足しておきました。あくまで左はアセンブリなので高級言語の命令と1対1には対応しません、だいたいです。
処理の流れは右の疑似コードを見てもらえば、きちんと元のC#のソースと同じことをしているのが理解できます (当たり前だけど)。2つのメソッドの違いは、M2()
メソッドの L0026
, L0029
の部分の有無です。
これは配列の境界チェックです。C#では配列外のインデックスにアクセスすると、必ずIndexOutOfRangeException
の例外が発生します。
var array = new int[10]; array[15] = 4; // ← throw new IndexOutOfRangeException()
C++とかだとこの辺の境界外アクセスは未定義なので色々と危険なことが起こります (起こせます) が、C#はメモリの安全性が言語として担保されてます。ここで、例外が発生するということは内部的にはインデックスが0以上かつ配列長未満であるかをチェックしているということで、これがM2()
メソッドの L0026
, L0029
の部分です。
安全性が担保されているのはいいことですが、これは実行速度とトレードオフで、このチェックはループ毎にインデックスアクセスで行われるため、オーバーヘッドが発生します。
ではなぜM1()
メソッドの方はこのチェックがないのかと言うと、M1()
のfor
の条件は初期値がi=0
で終了条件がi < array.Length
、更新条件がi++
なため、原理的に配列の境界外にアクセスが発生せず、JIT コンパイラがそれを認識して高速化のために境界値チェックを削除したためです。
ならばM2()
メソッドの方も境界外アクセスが発生しないのは自明な気がしますが、この最適化が行われるのは終了条件にarray.Length
プロパティを使った時のみ行われます。L
がpublicだから、あるいはクラスフィールドだから途中で非同期から変更される可能性があるためチェックを排除できない、というのもありますが、これに関してはメソッド内のローカル変数にL
を置いてもチェックは消えません。あくまでarray.Length
の時のみ高速化されます。
一応補足しておきますが、この最適化が行われるのは JIT コンパイル時です。JIT コンパイラがもう少し頑張って処理の流れを追って解析すればarray.Length
プロパティ以外でも必ず安全性が保たれる場合なら最適化できそうな気もします。が、JIT コンパイルは実行時に行われるため、処理の解析と最適化に時間をかけることができないという理由もあって、たぶん行われていません。IL の状態では、上記2つのインデックスアクセスの部分は全く同じ IL 命令にコンパイルされています。
ベンチマーク
最後に上記の2つのメソッドが本当に速度差があるのかベンチマークを取っておきましょう。測定はいつも通り Benchmark.NET を使います。github から取ってこなくても Nuget からパッケージを取ってこられます。
BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362 Intel Core i5-4300U CPU 1.90GHz (Haswell), 1 CPU, 4 logical and 2 physical cores .NET Core SDK=3.0.100 [Host] : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT
Method | Mean | Error | StdDev | Ratio | RatioSD |
---|---|---|---|---|---|
M1 | 34.59 ms | 0.805 ms | 2.374 ms | 1.00 | 0.00 |
M2 | 35.14 ms | 1.013 ms | 2.971 ms | 1.02 | 0.09 |
……誤差の範囲では……?思ったよりも差が出なかったです。最後の最後で話の腰を折られてしまった気がする。
が、事実としてLength
プロパティをfor
の終了条件として使うか否かだけでJITコンパイルの最適化結果のアセンブリが異なりますよ、という記事でした。
[追記] この話は2020/01月現在、 .NET Core 3.0 (およびそれ以前の .NET のバージョン) での JIT の話です。将来的にはJITがもっと賢くなって変わる可能性もあります。可能性は低いと思いますが。