はじめに
for や foreach でループを回して、配列やリストなどのデータ集合に処理をする。
基本的な処理ですが、ここにも最適化手法が眠っています。
本記事では、より高速なループを記述するためのテクニック、あるいはループを高速化teするために
言語仕様や標準ライブラリで使用されている最適化手法について解説します。
少し詳しい人だと、境界値チェックの最適化や配列の専用命令などを聞いたことがあるかもしれませんが、完全に理解している人は少ないのではないでしょうか。本記事ではそのへんもちゃんと解説したいと思います。
ベンチマーク
まずは、ここから先の解説の土台として、ベンチマークを実行してみます。
ベンチマークの内容は、0 から N-1 までの int 集合に N-1 が含まれるかどうか調べるというものです。つまり、N 回のループが回るようになっています。
Contains メソッドでできることですが、今回はループが回る処理の典型として見てください。
int 集合として
- 配列
int[] - リスト
List<int> - イテレーター
Enumerable.Range - 以上を
IEnumerable<int>でラップしたもの - 以上を
IList<T>でラップしたもの
を用意しています。
ループの回し方も
-
forループ -
foreachループ - Linq
-
Spanでfor
などなど色々検証しております。
ベンチマーク環境は、アーキテクチャの違うCPUを搭載した2つのPCで行っています。
テストサイズは、CPUのL3キャッシュに収まる N = 1M と、収まらない N = 100M をそれぞれ実行します。
結果は解説パートでつまみつまみ見ていきますが、私が解説するより先に内容と結果をすべて公開するほうがフェアだと思うので
すべて載せておきます。適宜見てください。
ベンチマークコード
コード全文を見る
public class Benchmark
{
const int testSize = 1_000_000;
const int target = testSize - 1;
const int helfSize = testSize / 2;
const int helfTarget = helfSize - 1;
private static readonly int[] array;
private static readonly List<int> list;
private static readonly IEnumerable<int> iterator;
private static readonly IEnumerable<int> wrappedArray;
private static readonly IEnumerable<int> wrappedList;
private static readonly IList<int> listWrappedArray;
private static readonly IList<int> listWrappedList;
static Benchmark()
{
array = Enumerable.Range(0, testSize).ToArray();
list = Enumerable.Range(0, testSize).ToList();
iterator = Enumerable.Range(0, testSize);
wrappedArray = array;
wrappedList = list;
listWrappedArray = array;
listWrappedList = list;
}
// 一般的な配列への for ループ。
// ローカル変数に置き直しているのでスレッドセーフ => 境界値チェックの最適化を想定。
[Benchmark]
public bool ArrayFor()
{
var _array = array;
for (int i = 0; i < _array.Length; i++)
{
if (_array[i] == target)
{
return true;
}
}
return false;
}
// 静的フィールド配列への for ループ。
// マルチスレッドで書き換えれる => 境界値チェックが入るかも。
[Benchmark]
public bool ArrayForField()
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return true;
}
}
return false;
}
// 引数配列への for ループ。
// これも境界値チェックの最適化が見込まれる。
[Benchmark]
public bool ArrayForArg()
{
return ArrayForInternal(array);
}
private bool ArrayForInternal(int[] _array)
{
for (int i = 0; i < _array.Length; i++)
{
if (_array[i] == target)
{
return true;
}
}
return false;
}
// ループ条件を定数 = コンパイラが解析しにくい にした for ループ。
// 境界値チェックの最適化が入らないだろうケース。
[Benchmark]
public bool ConstArrayFor()
{
for (int i = 0; i < testSize; i++)
{
if (array[i] == target)
{
return true;
}
}
return false;
}
// foreach による配列へのループ。
// C#コンパイラ時点で for 相当のコードに展開されるのでパフォーマンス差はほぼないはず。
[Benchmark]
public bool ArrayForeach()
{
foreach (var n in array)
{
if (n == target)
{
return true;
}
}
return false;
}
// List への for ループ。
// ldelem 命令じゃなくて関数呼び出しだし境界値チェック最適化できないし、で配列より遅いと思われる。
// とはいえ、foreach よりは早いと思われる。
[Benchmark]
public bool ListFor()
{
for (int i = 0; i < list.Count; i++)
{
if (list[i] == target)
{
return true;
}
}
return false;
}
// List への foreach ループ。
// 多分遅い。
[Benchmark]
public bool ListForeach()
{
foreach (var n in list)
{
if (n == target)
{
return true;
}
}
return false;
}
// 配列を Span<T> にしてみる。
// 何故か早い。
[Benchmark]
public bool SpanArray()
{
return SpanInternal(array);
}
// List<T> を Span<T> にしてみる。
// もともとList<T>遅いこともあり結構効く。
[Benchmark]
public bool SpanList()
{
return SpanInternal(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list));
}
private bool SpanInternal(Span<int> span)
{
for (int i = 0; i < span.Length; i++)
{
if (span[i] == target)
{
return true;
}
}
return false;
}
// ポインタでやる。
// 境界値チェックとかそもそも概念がないので最速になると思われる。
// オーバーヘッド計測用の叩き台に。
[Benchmark]
public unsafe bool PtrArray()
{
fixed (int* ptr = array)
{
for (int i = 0; i < testSize; i++)
{
if (ptr[i] == target)
{
return true;
}
}
}
return false;
}
// イテレータで舐める。
// 多分遅い。
[Benchmark]
public bool IteratorForeach()
{
foreach (var n in iterator)
{
if (n == target)
{
return true;
}
}
return false;
}
// IEnumerable で舐める。
// 多分遅い。
[Benchmark]
public bool IEnumerableArrayForeach()
{
foreach (var n in wrappedArray)
{
if (n == target)
{
return true;
}
}
return false;
}
// IEnumerable で舐める。
// 多分遅い。
[Benchmark]
public bool IEnumerableListForeach()
{
foreach (var n in wrappedList)
{
if (n == target)
{
return true;
}
}
return false;
}
// IList で舐める。
// IEnumerable よりマシかもしれない。
[Benchmark]
public bool IListArrayFor()
{
for (int i = 0; i < listWrappedArray.Count; i++)
{
if (listWrappedArray[i] == target)
{
return true;
}
}
return false;
}
// IList で舐める。
// foreachなので多分遅い。
[Benchmark]
public bool IListArrayForeach()
{
foreach (var n in listWrappedArray)
{
if (n == target)
{
return true;
}
}
return false;
}
// IList で舐める。
// IEnumerable よりマシかもしれない。
[Benchmark]
public bool IListListFor()
{
for (int i = 0; i < listWrappedList.Count; i++)
{
if (listWrappedList[i] == target)
{
return true;
}
}
return false;
}
// IList で舐める。
// foreachなので多分遅い。
[Benchmark]
public bool IListListForeach()
{
foreach (var n in listWrappedList)
{
if (n == target)
{
return true;
}
}
return false;
}
[Benchmark]
public bool ArrayIndexof()
{
return Array.IndexOf(array, target) != -1;
}
[Benchmark]
public bool ListContains()
{
return list.Contains(target);
}
[Benchmark]
public bool ArrayLinq()
{
return wrappedArray.Contains(target);
}
[Benchmark]
public bool ListLinq()
{
return wrappedList.Contains(target);
}
}
結果(N = 1M)
結果を見る
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 530.3 μs | 7.36 μs | 6.89 μs |
| ArrayForField | 543.6 μs | 8.33 μs | 7.79 μs |
| ArrayForArg | 524.3 μs | 2.52 μs | 2.24 μs |
| ConstArrayFor | 547.2 μs | 2.47 μs | 2.06 μs |
| ArrayForeach | 530.3 μs | 7.80 μs | 7.29 μs |
| ListFor | 625.0 μs | 10.18 μs | 9.03 μs |
| ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
| SpanArray | 294.9 μs | 5.61 μs | 5.25 μs |
| SpanList | 289.3 μs | 0.83 μs | 0.65 μs |
| PtrArray | 293.7 μs | 5.45 μs | 5.10 μs |
| IteratorForeach | 4,542.6 μs | 19.08 μs | 16.91 μs |
| IEnumerableArrayForeach | 4,570.1 μs | 24.51 μs | 21.73 μs |
| IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |
| IListArrayFor | 4,802.3 μs | 34.28 μs | 28.63 μs |
| IListArrayForeach | 4,553.1 μs | 30.93 μs | 24.15 μs |
| IListListFor | 623.8 μs | 11.22 μs | 10.49 μs |
| IListListForeach | 5,188.2 μs | 19.26 μs | 16.08 μs |
| ArrayIndexof | 173.2 μs | 1.10 μs | 0.86 μs |
| ListContains | 175.3 μs | 2.82 μs | 2.64 μs |
| ArrayLinq | 175.7 μs | 3.38 μs | 3.16 μs |
| ListLinq | 162.7 μs | 1.38 μs | 1.23 μs |
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 475.6 μs | 6.07 μs | 5.68 μs |
| ArrayForField | 508.9 μs | 6.57 μs | 5.83 μs |
| ArrayForArg | 470.9 μs | 6.06 μs | 5.67 μs |
| ConstArrayFor | 498.0 μs | 4.99 μs | 4.67 μs |
| ArrayForeach | 455.4 μs | 8.40 μs | 6.56 μs |
| ListFor | 510.3 μs | 2.11 μs | 1.87 μs |
| ListForeach | 976.1 μs | 4.88 μs | 4.07 μs |
| SpanArray | 256.6 μs | 3.18 μs | 2.97 μs |
| SpanList | 250.2 μs | 1.03 μs | 0.86 μs |
| PtrArray | 259.6 μs | 3.99 μs | 3.74 μs |
| IteratorForeach | 4,068.1 μs | 3.90 μs | 3.46 μs |
| IEnumerableArrayForeach | 4,084.7 μs | 13.40 μs | 11.87 μs |
| IEnumerableListForeach | 4,565.7 μs | 10.08 μs | 9.42 μs |
| IListArrayFor | 4,438.7 μs | 85.26 μs | 98.19 μs |
| IListArrayForeach | 4,087.7 μs | 15.02 μs | 14.05 μs |
| IListListFor | 522.5 μs | 2.87 μs | 2.68 μs |
| IListListForeach | 4,570.1 μs | 9.79 μs | 9.16 μs |
| ArrayIndexof | 160.9 μs | 1.60 μs | 1.34 μs |
| ListContains | 167.7 μs | 3.18 μs | 3.54 μs |
| ArrayLinq | 167.0 μs | 3.26 μs | 4.12 μs |
| ListLinq | 150.2 μs | 1.19 μs | 0.93 μs |
結果(N = 100M)
結果を見る
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 57.43 ms | 0.530 ms | 0.470 ms |
| ArrayForField | 57.57 ms | 0.089 ms | 0.070 ms |
| ArrayForArg | 57.03 ms | 0.107 ms | 0.084 ms |
| ConstArrayFor | 58.92 ms | 0.850 ms | 0.754 ms |
| ArrayForeach | 57.58 ms | 0.917 ms | 0.858 ms |
| ListFor | 66.11 ms | 0.823 ms | 0.730 ms |
| ListForeach | 111.49 ms | 0.242 ms | 0.215 ms |
| SpanArray | 38.52 ms | 0.137 ms | 0.128 ms |
| SpanList | 38.26 ms | 0.134 ms | 0.105 ms |
| PtrArray | 38.62 ms | 0.359 ms | 0.300 ms |
| IteratorForeach | 384.51 ms | 5.253 ms | 4.914 ms |
| IEnumerableArrayForeach | 408.73 ms | 0.963 ms | 0.804 ms |
| IEnumerableListForeach | 522.03 ms | 8.857 ms | 8.284 ms |
| IListArrayFor | 438.44 ms | 6.355 ms | 5.634 ms |
| IListArrayForeach | 408.31 ms | 0.170 ms | 0.151 ms |
| IListListFor | 65.05 ms | 0.874 ms | 0.818 ms |
| IListListForeach | 516.65 ms | 0.828 ms | 0.647 ms |
| ArrayIndexof | 27.41 ms | 0.194 ms | 0.162 ms |
| ListContains | 27.42 ms | 0.205 ms | 0.160 ms |
| ArrayLinq | 27.20 ms | 0.296 ms | 0.247 ms |
| ListLinq | 27.59 ms | 0.547 ms | 0.651 ms |
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev | Median |
|---|---|---|---|---|
| ArrayFor | 58.05 ms | 0.197 ms | 0.184 ms | 58.07 ms |
| ArrayForField | 59.52 ms | 0.552 ms | 0.516 ms | 59.61 ms |
| ArrayForArg | 58.74 ms | 0.160 ms | 0.150 ms | 58.72 ms |
| ConstArrayFor | 53.17 ms | 0.211 ms | 0.187 ms | 53.11 ms |
| ArrayForeach | 57.54 ms | 0.479 ms | 0.448 ms | 57.50 ms |
| ListFor | 53.74 ms | 0.259 ms | 0.243 ms | 53.73 ms |
| ListForeach | 100.57 ms | 0.760 ms | 0.711 ms | 100.71 ms |
| SpanArray | 43.20 ms | 0.348 ms | 0.326 ms | 43.20 ms |
| SpanList | 43.55 ms | 0.854 ms | 1.329 ms | 42.94 ms |
| PtrArray | 42.03 ms | 0.833 ms | 0.959 ms | 42.33 ms |
| IteratorForeach | 335.63 ms | 0.763 ms | 0.637 ms | 335.36 ms |
| IEnumerableArrayForeach | 363.98 ms | 1.358 ms | 1.204 ms | 363.33 ms |
| IEnumerableListForeach | 456.95 ms | 1.193 ms | 1.116 ms | 456.84 ms |
| IListArrayFor | 385.10 ms | 1.806 ms | 1.690 ms | 384.55 ms |
| IListArrayForeach | 363.89 ms | 0.604 ms | 0.472 ms | 363.96 ms |
| IListListFor | 53.51 ms | 0.331 ms | 0.309 ms | 53.55 ms |
| IListListForeach | 456.60 ms | 1.099 ms | 0.974 ms | 456.08 ms |
| ArrayIndexof | 30.07 ms | 0.583 ms | 0.818 ms | 29.63 ms |
| ListContains | 29.46 ms | 0.183 ms | 0.180 ms | 29.42 ms |
| ArrayLinq | 29.51 ms | 0.264 ms | 0.206 ms | 29.47 ms |
| ListLinq | 29.42 ms | 0.174 ms | 0.155 ms | 29.41 ms |
結果の概観
速度を比較すると、
- Linq や
IndexOfなどの「検索」に特化したメソッドを使用するケース -
Span(配列やリストより有意に高速といえる) - 配列
int[]。ただし、ループの実装によりややパフォーマンスに差がある。 -
List<T>。配列よりは低速だが、それでもインターフェイスを介した場合よりはかなり高速。 - インターフェイスを介する場合。
forを活用できるIList<T>の使用はList<T>に対しては有効だが配列に対しては効果がない。
それぞれの理由についてはこれから個別に取り上げて順に説明していきます。
配列とパフォーマンス
まず、配列は一般的なコレクションとしては最も高速であることがわかります。
では、なぜ配列は高速なのでしょうか。配列とパフォーマンスの関係を追ってみましょう。
配列と境界値チェックの挿入
C# の配列はメモリ安全性を確保したつくりになっています。ここでいうメモリ安全性とは以下の二点に代表されるでしょう。
- GCにより確実に解放される。
free()とかしなくてよい。もちろん忘れることもない。 - 未初期化領域への読み書きができない。1 でもインデックスが配列長を超えた操作を実行しようとした時点でプログラムが停止する。
これらは C# では当たり前のことですが、これらは原始的には当たり前ではないわけです。
したがって、これらは C# および .NETランタイムが頑張って保証しています。そして、そのコストはタダではないわけです。
特に、後者の配列として確保した領域をはみ出さないという特性が問題になります。
要は、array[array.Length] とかやると一瞬で IndexOutOfRangeException が飛んできて怒られるという仕組みの裏側なわけですが、
これは配列の読み書きの操作をするたびに、操作しようとしているインデックスが配列長を超えていないかをチェックし、超えていれば例外をスローするコードを、ランタイムが暗黙的に挿入することにより実現されており、配列への操作のパフォーマンスにクリティカルに影響します。本記事ではこの振る舞いを「境界値チェック」と呼ぶことにしましょう。
ところが、今回のベンチマークのような、一般的な配列へのループ操作が配列の範囲外を操作する可能性がないことは明らかでしょう。
ループ条件が i = 0 から i < _array.Length である以上、範囲外になる余地はありません。
public bool ArrayFor()
{
var _array = array;
for (var i = 0; i < _array.Length; i++)
{
if (_array[i] == target)
{
return true;
}
}
return false;
}
この事実を、ランタイムは多少考慮してくれる作りになっています。すなわち、ランタイムが境界外操作のリスクが絶対にないと判断した場合、境界値チェックをするコードの挿入をキャンセルしてくれます。
境界値チェックの最適化が入るケース・入らないケース
配列へのループ処理を最適化する場合、この境界値チェックが入らないようにランタイムが最適化してくれる書き方をすることが有効なわけですが、
この最適化はコードを局所的にしか見ておらず、大局的にフローを追って最適化とかはしてくれません。
また、ランタイムレベルで暗黙的に挿入されるため、目に触れることが少なく、最適化されているかどうかがわかりにくいです。
本記事では、ベンチマークおよび逆アセンブルによりこの境界値チェックの最適化の挙動に関して研究します。
今回検証したループの回し方は以下の 5 種です。
コード・結果は最初に載せたものの再掲になります。ベンチマーク中で、array は、クラスの静的フィールドであるテストデータです。
public class Benchmark
{
private const int testSize = 100_000_000;
private const int target = testSize - 1;
private static readonly int[] array;
}
1. 普通の for
ローカル変数を普通にループするものです。基準。
public bool ArrayFor()
{
int[] _array = array;
for (var i = 0; i < _array.Length; i++)
{
if (_array[i] == target)
{
return true;
}
}
return false;
}
2. フィールドを直接 for
フィールドを直接ループ処理します。ネタバレですが遅いです。
public bool ArrayForField()
{
for (var i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return true;
}
}
return false;
}
3. ループを関数に切り出し
ループ処理を関数に切り出したものです。これだけで結果が変わるのが難しいところ。
public bool ArrayForArg()
{
return ArrayForInternal(array);
}
private bool ArrayForInternal(int[] _array)
{
for (var i = 0; i < _array.Length; i++)
{
if (_array[i] == target)
{
return true;
}
}
return false;
}
4. ループ条件を定数に
Length プロパティをみる代わりに定数を使います。遅いです。
public bool ConstArrayFor()
{
for (var i = 0; i < testSize; i++)
{
if (array[i] == target)
{
return true;
}
}
return false;
}
5. foreach
foreach を使ってみます。
public bool ArrayForeach()
{
foreach (var n in array)
{
if (n == target)
{
return true;
}
}
return false;
}
ベンチマークには誤差もあるため、わかりにくいかもしれませんが、結論からいうと今回のベンチマークでは
- ArrayFor
- ArrayForArg
- ArrayForeach
が最適化されているケースです。一方
- ArrayForField
- ConstArrayFor
が最適化されておらず、境界値チェックが入っています。
結果は N = 1M の場合が見やすいでしょうか。該当部分を取り出すと以下のようになります。
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 530.3 μs | 7.36 μs | 6.89 μs |
| ArrayForField | 543.6 μs | 8.33 μs | 7.79 μs |
| ArrayForArg | 524.3 μs | 2.52 μs | 2.24 μs |
| ConstArrayFor | 547.2 μs | 2.47 μs | 2.06 μs |
| ArrayForeach | 530.3 μs | 7.80 μs | 7.29 μs |
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 475.6 μs | 6.07 μs | 5.68 μs |
| ArrayForField | 508.9 μs | 6.57 μs | 5.83 μs |
| ArrayForArg | 470.9 μs | 6.06 μs | 5.67 μs |
| ConstArrayFor | 498.0 μs | 4.99 μs | 4.67 μs |
| ArrayForeach | 455.4 μs | 8.40 μs | 6.56 μs |
差がついているのがわかるでしょうか。
マルチスレッド安全性
まず、最適化の有無を分けたのがマルチスレッド安全性です。
クラスの静的フィールドとして持っている配列をそのままループで処理した ArrayForField では、マルチスレッド安全性が担保できません。
クラスの静的フィールドは、別のスレッドから書き換えることができるためです。ループ処理中により長さの短い別の配列にフィールドが書き換えられると
範囲外の読み取りが発生することになり、この可能性を排除することはできません。したがって、境界値チェックを省略できないのです。
一方、ローカル変数に一旦代入したケースや関数の引数としたケースでは、これらはスレッド内で閉じているため安全であり、最適化がなされています。
実際、このようになっていることはアセンブラからわかります。
理解したい人のために読解のコツを書いておくと、まず先にループ本体をつかむことです。
Benchmark.ArrayFor ()
L0000 sub rsp, 0x28
L0004 mov rcx, 0x7ff847e3cea8
L000e mov edx, 1
L0013 call 0x00007ff8a709dae0
L0018 mov rax, [rax]
L001b xor edx, edx
L001d mov ecx, [rax+8]
L0020 test ecx, ecx
L0022 jle short L0038
L0024 movsxd r8, edx
L0027 cmp dword ptr [rax+r8*4+0x10], 0xf423f
L0030 je short L003f
L0032 inc edx
L0034 cmp ecx, edx
L0036 jg short L0024
L0038 xor eax, eax
L003a add rsp, 0x28
L003e ret
L003f mov eax, 1
L0044 add rsp, 0x28
L0048 ret
Benchmark.ArrayForField ()
L0000 push rsi
L0001 sub rsp, 0x20
L0005 xor esi, esi
L0007 mov rcx, 0x7ff847e3cea8
L0011 mov edx, 1
L0016 call 0x00007ff8a709dae0
L001b mov rdx, [rax]
L001e cmp dword ptr [rdx+8], 0
L0022 jle short L0043
L0024 mov rdx, [rax]
L0027 cmp esi, [rdx+8]
L002a jae short L0056
L002c movsxd rcx, esi
L002f cmp dword ptr [rdx+rcx*4+0x10], 0xf423f
L0037 je short L004b
L0039 inc esi
L003b mov rdx, [rax]
L003e cmp [rdx+8], esi
L0041 jg short L0024
L0043 xor eax, eax
L0045 add rsp, 0x20
L0049 pop rsi
L004a ret
L004b mov eax, 1
L0050 add rsp, 0x20
L0054 pop rsi
L0055 ret
L0056 call 0x00007ff8a709f120
L005b int3
後者では、L0024 ~ L002a の jae (~以上でジャンプ) で、インデックスが配列の長さ以上のときに制御を飛ばし、例外をスローする処理を call で呼び出しています。
これに相当する命令は前者の最適化が入ったアセンブラではないことがわかります。
わずか 3 命令ではありますが、これはループ内部に入っているため、そもそもループの中身が短い今回のケースではまぁまぁパフォーマンスに響きます。
また、ループ処理を関数に切り出した場合の、切り出した関数側を見てみましょう。
同様に最適化がかかっていることがわかります。このアセンブラは短いのでなんとなく読めるのではないでしょか。
Benchmark.ArrayForInternal (Int32[])
L0000 xor eax, eax
L0002 mov ecx, [rdx+8]
L0005 test ecx, ecx
L0007 jle short L001d
L0009 movsxd r8, eax
L000c cmp dword ptr [rdx+r8*4+0x10], 0xf423f
L0015 je short L0020
L0017 inc eax
L0019 cmp ecx, eax
L001b jg short L0009
L001d xor eax, eax
L001f ret
L0020 mov eax, 1
L0025 ret
Length 以外を条件にしない
この最適化は、愚直にループ条件が配列の Length プロパティかどうかを見ていると思われます。
そのため、ループ条件として整数リテラル(定数)などを使用すると最適化が入りません。
定数を使用するなど、わかりにくい書き方をすると最適化を阻害します。
Benchmark.ConstArrayFor ()
L0000 push rsi
L0001 sub rsp, 0x20
L0005 xor esi, esi
L0007 mov rcx, 0x7ff847e3cea8
L0011 mov edx, 1
L0016 call 0x00007ff8a709dae0
L001b mov rax, [rax]
L001e cmp esi, [rax+8]
L0021 jae short L004d
L0023 movsxd rdx, esi
L0026 cmp dword ptr [rax+rdx*4+0x10], 0xf423f
L002e je short L0042
L0030 inc esi
L0032 cmp esi, 0xf4240
L0038 jl short L0007
L003a xor eax, eax
L003c add rsp, 0x20
L0040 pop rsi
L0041 ret
L0042 mov eax, 1
L0047 add rsp, 0x20
L004b pop rsi
L004c ret
L004d call 0x00007ff8a709f120
L0052 int3
配列では foreach は for 相当に最適化
foreach は、C# 言語仕様的には、GetEnumerator() を呼び出して、MoveNext() ~ Current 参照、というパターンになるわけですが、これは遅いので C# コンパイラは、配列に対しては特殊扱いで for 相当のコードを生成します。そのため、今回のケースでは中間言語の時点で同じアセンブリです。
Benchmark.ArrayFor ()
IL_0000 ldsfld Benchmark.array
IL_0005 stloc.0 // _array
IL_0006 ldc.i4.0
IL_0007 stloc.1 // i
IL_0008 br.s IL_001A
IL_000A ldloc.0 // _array
IL_000B ldloc.1 // i
IL_000C ldelem.i4
IL_000D ldc.i4 FF E0 F5 05 // 99999999
IL_0012 bne.un.s IL_0016
IL_0014 ldc.i4.1
IL_0015 ret
IL_0016 ldloc.1 // i
IL_0017 ldc.i4.1
IL_0018 add
IL_0019 stloc.1 // i
IL_001A ldloc.1 // i
IL_001B ldloc.0 // _array
IL_001C ldlen
IL_001D conv.i4
IL_001E blt.s IL_000A
IL_0020 ldc.i4.0
IL_0021 ret
Benchmark.ArrayForeach ()
IL_0000 ldsfld Benchmark.array
IL_0005 stloc.0
IL_0006 ldc.i4.0
IL_0007 stloc.1
IL_0008 br.s IL_001A
IL_000A ldloc.0
IL_000B ldloc.1
IL_000C ldelem.i4
IL_000D ldc.i4 FF E0 F5 05 // 99999999
IL_0012 bne.un.s IL_0016
IL_0014 ldc.i4.1
IL_0015 ret
IL_0016 ldloc.1
IL_0017 ldc.i4.1
IL_0018 add
IL_0019 stloc.1
IL_001A ldloc.1
IL_001B ldloc.0
IL_001C ldlen
IL_001D conv.i4
IL_001E blt.s IL_000A
IL_0020 ldc.i4.0
IL_0021 ret
同じ中間言語コードなのですから、あえて掲載はしませんが生成されるx64アセンブリも同じです。
マルチスレッド安全性やループ条件で最適化されない可能性を考慮しなくてよい分だけ、foreach の方が楽でしょうか。
配列と中間言語(IL)専用命令
配列は、生成、読み取り、書き込み、長さの取得、それぞれに中間言語レベルでの専用命令が割り振られています。
| 操作 | 命令 |
|---|---|
| 生成 | newarr |
| 読み取り |
ldelem / ldelema
|
| 書き込み | stelem |
| 長さの取得 | ldlen |
実際に、今回のベンチマークコードの一部を見てみましょう。中間言語にもシンタックスハイライトがほしい
Benchmark.ArrayFor ()
IL_0000 ldsfld Benchmark.array
IL_0005 stloc.0 // _array
IL_0006 ldc.i4.0
IL_0007 stloc.1 // i
IL_0008 br.s IL_001A
IL_000A ldloc.0 // _array
IL_000B ldloc.1 // i
IL_000C ldelem.i4
IL_000D ldc.i4 FF E0 F5 05 // 99999999
IL_0012 bne.un.s IL_0016
IL_0014 ldc.i4.1
IL_0015 ret
IL_0016 ldloc.1 // i
IL_0017 ldc.i4.1
IL_0018 add
IL_0019 stloc.1 // i
IL_001A ldloc.1 // i
IL_001B ldloc.0 // _array
IL_001C ldlen
IL_001D conv.i4
IL_001E blt.s IL_000A
IL_0020 ldc.i4.0
IL_0021 ret
先程紹介したような、専用命令が使用されていることがわかります。
配列型の再現実験
中間言語レベルでの専用命令があれば高速、という話は結構聞く話なのではないでしょうか。
自分もずっとそう思っていたのですが、今回せっかくなので検証してみようと思います。
ということで、配列型を自作してみましょう。今回の検証環境は64bitなので、実装は64bit決め打ちになっています。
配列のメモリレイアウトに関しては、以前に書いた記事 をあわせて見ていただけると理解できると思います(宣伝)。
public unsafe sealed class MyArray<T> where T : unmanaged
{
private readonly void* ptr;
private readonly int headerSize = sizeof(nint) + sizeof(nint);
public MyArray(int length)
{
ptr = Marshal.AllocHGlobal(headerSize + length * sizeof(T)).ToPointer();
((nint*)ptr)[0] = (nint)0xDEADBEAF;
((nint*)ptr)[1] = length;
}
public T this[int index]
{
get => (uint)index < Length ? ((T*)((nint)ptr + 16))[index] : ThrowIndexOutOfRange();
set => _ = (uint)index < Length ? ((T*)((nint)ptr + 16))[index] = value : ThrowIndexOutOfRange();
}
private static T ThrowIndexOutOfRange()
{
throw new IndexOutOfRangeException();
}
public T GetUnsafe(int index)
{
return ((T*)((nint)ptr + 16))[index];
}
public void SetUnsafe(int index, T value)
{
((T*)((nint)ptr + 16))[index] = value;
}
public int Length
{
get => *(int*)((nint)ptr + 8);
}
}
簡単に実装を説明します。
Marshal.AllocHGlobal (要は malloc ) でヒープを確保し、その上に配列を再現します。
配列の先頭には、仮想関数テーブルのポインタと長さが入ります。今回は、仮想関数テーブルの部分は適当な値を入れておきます。
次に配列の要素数が入ります。それに続いて書く要素が並びます。
なお、この MyArray<T> クラスのインスタンス自体がポインタですので、本当の配列と比較して間接参照が1段階余計に入ります。
インデクサーによるアクセスでは境界値チェックを掛けています。最適化で境界値チェックがない状況は GetUnsafe 関数で再現できます。
結果
MyArraySafe は、境界値チェックが入っているテストケースで、ConstArrayFor 相当です。
MyArrayUnsafe は、境界値チェックを消したテストケースで、ArrayFor 相当です。
N=1M
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 532.6 μs | 7.21 μs | 6.02 μs |
| ConstArrayFor | 547.9 μs | 3.04 μs | 2.54 μs |
| MyArraySafe | 547.9 μs | 3.49 μs | 2.92 μs |
| MyArrayUnsafe | 526.0 μs | 1.44 μs | 1.28 μs |
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 471.3 μs | 8.96 μs | 8.80 μs |
| ConstArrayFor | 499.6 μs | 5.24 μs | 4.91 μs |
| MyArraySafe | 492.1 μs | 3.85 μs | 3.41 μs |
| MyArrayUnsafe | 456.1 μs | 7.52 μs | 7.04 μs |
N=100M
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 57.11 ms | 0.193 ms | 0.151 ms |
| ConstArrayFor | 58.88 ms | 0.195 ms | 0.163 ms |
| MyArraySafe | 59.54 ms | 0.294 ms | 0.260 ms |
| MyArrayUnsafe | 57.42 ms | 0.101 ms | 0.079 ms |
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22621
AMD Ryzen 7 4700U with Radeon Graphics, 1 CPU, 8 logical and 8 physical cores
.NET SDK=6.0.301
[Host] : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 56.82 ms | 1.122 ms | 1.049 ms |
| ConstArrayFor | 53.84 ms | 1.001 ms | 1.028 ms |
| MyArraySafe | 53.26 ms | 0.931 ms | 0.871 ms |
| MyArrayUnsafe | 51.00 ms | 0.650 ms | 0.608 ms |
専用命令はパフォーマンスに貢献するか
やはり多少誤差によるばらつきが発生していますが、以上の結果を見る限り、自作配列型と本当の配列型でほぼ同じ性能であることがわかります。ところが、
Benchmark2.MyArraySafe ()
IL_0000 ldc.i4.0
IL_0001 stloc.0 // i
IL_0002 br.s IL_001C
IL_0004 ldsfld Benchmark2.array2
IL_0009 ldloc.0 // i
IL_000A callvirt MyArray <Int32>.get_Item (Int32)
IL_000F ldc.i4 3F 42 0F 00 // 999999
IL_0014 bne.un.s IL_0018
IL_0016 ldc.i4.1
IL_0017 ret
IL_0018 ldloc.0 // i
IL_0019 ldc.i4.1
IL_001A add
IL_001B stloc.0 // i
IL_001C ldloc.0 // i
IL_001D ldsfld Benchmark2.array2
IL_0022 callvirt MyArray <Int32>.get_Length ()
IL_0027 blt.s IL_0004
IL_0029 ldc.i4.0
IL_002A ret
Benchmark2.MyArrayUnsafe ()
IL_0000 ldc.i4.0
IL_0001 stloc.0 // i
IL_0002 br.s IL_001C
IL_0004 ldsfld Benchmark2.array2
IL_0009 ldloc.0 // i
IL_000A callvirt MyArray <Int32>.GetUnsafe (Int32)
IL_000F ldc.i4 3F 42 0F 00 // 999999
IL_0014 bne.un.s IL_0018
IL_0016 ldc.i4.1
IL_0017 ret
IL_0018 ldloc.0 // i
IL_0019 ldc.i4.1
IL_001A add
IL_001B stloc.0 // i
IL_001C ldloc.0 // i
IL_001D ldsfld Benchmark2.array2
IL_0022 callvirt MyArray <Int32>.get_Length ()
IL_0027 blt.s IL_0004
IL_0029 ldc.i4.0
IL_002A ret
と、自作配列型では専用命令は全く使用されておらず、すべて callvirt 命令による普通の仮想関数呼び出しにコンパイルされています。
つまり、中間言語レベルでの専用命令は、必ずしもパフォーマンスに貢献はしません。
x64アセンブリをみると
Benchmark2.MyArraySafe ()
L0000 push ebp
L0001 mov ebp, esp
L0003 push edi
L0004 push esi
L0005 push ebx
L0006 xor esi, esi
L0008 mov ecx, 0xdfeca20
L000d mov edx, 2
L0012 call 0x04975760
L0017 mov edx, [eax+8]
L001a mov edx, [edx+4]
L001d cmp dword ptr [edx+8], 0
L0021 jle short L0051
L0023 mov edx, [eax+8]
L0026 xor ecx, ecx
L0028 mov edx, [edx+4]
L002b mov edi, [edx+8]
L002e mov ebx, edi
L0030 sar ebx, 0x1f
L0033 cmp esi, edi
L0035 sbb ecx, ebx
L0037 jge short L0062
L0039 mov edx, [edx+esi*4+0x10]
L003d cmp edx, 0xf423f
L0043 je short L0058
L0045 inc esi
L0046 mov edx, [eax+8]
L0049 mov edx, [edx+4]
L004c cmp esi, [edx+8]
L004f jl short L0023
L0051 xor eax, eax
L0053 pop ebx
L0054 pop esi
L0055 pop edi
L0056 pop ebp
L0057 ret
L0058 mov eax, 1
L005d pop ebx
L005e pop esi
L005f pop edi
L0060 pop ebp
L0061 ret
L0062 call dword ptr [0xdfedcec]
L0068 int3
Benchmark2.MyArrayUnsafe ()
L0000 push ebp
L0001 mov ebp, esp
L0003 push esi
L0004 xor esi, esi
L0006 mov ecx, 0xdfeca20
L000b mov edx, 2
L0010 call 0x04975760
L0015 mov edx, [eax+8]
L0018 mov edx, [edx+4]
L001b cmp dword ptr [edx+8], 0
L001f jle short L003d
L0021 mov edx, [eax+8]
L0024 mov edx, [edx+4]
L0027 cmp dword ptr [edx+esi*4+0x10], 0xf423f
L002f je short L0042
L0031 inc esi
L0032 mov edx, [eax+8]
L0035 mov edx, [edx+4]
L0038 cmp esi, [edx+8]
L003b jl short L0021
L003d xor eax, eax
L003f pop esi
L0040 pop ebp
L0041 ret
L0042 mov eax, 1
L0047 pop esi
L0048 pop ebp
L0049 ret
となっており、ループ本体に関しては先程みた for でのアセンブリと非常に近いことがわかるでしょう。
間接参照が 1 回多い点が、mov 命令が 2 回連続するところに影響している以外の違いはほとんどないです。
自作配列型も、(そうなるよう工夫しているので)完全にインライン化が入り、関数呼び出しなどは消去されるため、結局中間言語レベルで専用命令だろうが関数呼び出しだろうが関係なくなってしまいます。
ちなみに、インライン化されるために自作配列型では
- 例外を直接スローしない
- 継承させない
という最適化をしています。また、境界値チェックもちょっとしたトリックを活用して最適化しています。
ここまでやれば配列と同じパフォーマンスが出せます。
結論として、配列が高速であるのは、中間言語レベルでの専用命令そのものの恩恵というより
- インライン化
- 境界値チェックの最適化
などが掛かり、かつ無駄がないシンプルな構造であることによるといえるでしょう。
このうち境界値チェックの最適化に関しては安全に模倣するのが難しいため、この恩恵がいわゆる「専用命令によるアドバンテージ」の正体であると思われます。
まとめ
話が長くなり、エディタが重くなってきたのでこの辺で一旦まとめて次回へ続くことにしましょう。
- 配列は
List<T>や interface扱いより早い- 境界値チェックが消えるかどうかが大事
- マルチスレッド安全性やループ条件による
-
foreachはfor相当に展開- もちろん境界値チェックは最適化される、確実
- 境界値チェックが消えるかどうかが大事
- 配列に専用命令があるから早いっていうことではない
- 自作の配列型を作ると同じパフォーマンスになる
次回