はじめに
この記事は配列編の続きです。先に配列編を読まれることをおすすめします。
List<T> のパフォーマンス
関係するベンチマーク結果を抜き出すとこんな感じです。
ポイントは
- 配列より流石に遅い。
-
forとforeachでパフォーマンスが違う -
IEnumerable<T>扱いするよりは格段に早い
ことです。
List<T> では、利用者側でできる最適化手法は最後に紹介する１つ以外ありません。どちらかといえば、標準ライブラリ側でどんな工夫をしているかの紹介になります。
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 530.3 μs | 7.36 μs | 6.89 μs |
| ConstArrayFor | 547.2 μs | 2.47 μs | 2.06 μs |
| ListFor | 625.0 μs | 10.18 μs | 9.03 μs |
| ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
| IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |
List<T> のしくみ
以下の説明で、List<T> というか可変長の配列リストというものがどういう仕組みなのか知っていないと困るので簡単に説明します。知っている人は読み飛ばしてください。
List<T> クラスは配列をフィールドとして保持しており、これが List<T> の中身です。そして、要素を追加するときにこの配列を拡張します。
ただし、拡張するとはいっても配列の長さを伸ばすことはできません。実際には、より長い新しい配列を確保して、もともとの配列から要素をすべてコピーして再代入しています。
ここで問題になるのがこの拡張操作のコストです。長さが n のとき、長さ 2n の配列を確保して n 個の要素をコピーするので、これは計算量が O(n) の操作になります。
要素を追加するたびに O(n) かかるとたまったものではないので、ある程度まとめて拡張することを考えます。
ここで、「足りなくなったら配列の長さを2倍に拡張」ことを考えます。2のべき乗は (定数倍の) 計算コストが安いのでだいたいこの実装になります。
この場合、拡張操作で新たに n 個の余裕ができますから、O(n) 操作 が 1/n 確率で発生することになり、要素の追加の計算量が平均して O(1) になります。
狐につままれたような気がしますが、こういう理屈で List<T> への Add は O(1) です。
したがって、List<T> の実態は、その要素数 (Count) 以上の長さを常に持つ配列が裏側に存在するという状況です。
慣習的に、裏側の配列の長さは Capacity と呼称します。
List<T> は普通にクラスとして実装されているので、普通にソースコードが読めます。
冒頭はこんな感じです。
public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
private const int DefaultCapacity = 4;
internal T[] _items; // Do not rename (binary serialization)
internal int _size; // Do not rename (binary serialization)
private int _version; // Do not rename (binary serialization)
}
配列、( List<T> としての ) 長さを保持していることがわかります。(あと書き換え時の一貫性保証のためのバージョンがあります)
配列の最初のキャパシティは 4 で、(掲載はしませんが) 足りなくなると 2倍の長さで確保しなおして Array.Copy しています。
List<T> のインデクサー実装
インデクサー ([]) は、配列に対しては専用命令でしたが、List<T> の場合は普通にメソッド呼び出しです。
その実装は
public T this[int index]
{
get
{
// Following trick can reduce the range check by one
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
}
return _items[index];
}
set
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
}
_items[index] = value;
_version++;
}
}
となっています。色々と工夫がされていますね。
「0以上X未満」の最適化
index として正当な値は、0 以上、List<T> の Count (_size) 未満です。
愚直に実装すると、
if (index < 0 || index >= size)
{
// throw exception
}
と、2回比較して OR になります。
しかし、負の整数の場合、先頭の符号ビットに 1 が立っていることに注目しましょう。
size は常に正なので、先頭の符号ビットは常に 0 です。したがって、符号なし 整数としてみると、負の数のほうが常に大きいことになります。
この点を理解すると、List<T> の実装で使われている if ((uint)index >= (uint)_size) がよくできていることがわかります。
この方法では 1 比較で済むので、愚直な方法より高速です。
例外スローの切り出し
throw 文 (あるいは式) は、インライン化を阻害することが知られています。
今回のような、短い関数の場合は通常であればインライン化されることが期待されるため、throw を書くのを避けたいです。
そのため、例外をスローするための関数を用意する手法がよく使われます。
今回の List<T> でも、ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();という形で、 throw を避けています。
前回の配列編で自作配列型を実装するときに、最初この点を忘れて実装してしまい、とんでもない差がついてびっくりしました。
List<T> の内部実装と同じ手法で正しく実装した自作配列型は、以下のように配列と変わらないパフォーマンスでしたが
| 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 |
例外を投げる部分を関数に切り出すのを忘れ、普通に throw すると
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 57.25 ms | 0.366 ms | 0.306 ms |
| ConstArrayFor | 58.75 ms | 0.209 ms | 0.163 ms |
| MyArraySafe | 218.97 ms | 0.572 ms | 0.477 ms |
| MyArrayUnsafe | 57.81 ms | 0.526 ms | 0.492 ms |
3.7倍遅くなりました。単純な関数であればあるほどインライン化の有無の差が開くので注意が必要です。
境界値チェックの問題
以上のように、List<T> のインデクサーの実装は結構工夫がされています。この工夫がどう影響するのか、逆アセンブル結果を見てみましょう。
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+8]
L001f cmp dword ptr [rdx+0x10], 0
L0023 jle short L004f
L0025 mov rdx, [rax+8]
L0029 cmp esi, [rdx+0x10]
L002c jae short L0062
L002e mov rdx, [rdx+8]
L0032 cmp esi, [rdx+8]
L0035 jae short L0068
L0037 movsxd rcx, esi
L003a cmp dword ptr [rdx+rcx*4+0x10], 0xf423f
L0042 je short L0057
L0044 inc esi
L0046 mov rdx, [rax+8]
L004a cmp esi, [rdx+0x10]
L004d jl short L0025
L004f xor eax, eax
L0051 add rsp, 0x20
L0055 pop rsi
L0056 ret
L0057 mov eax, 1
L005c add rsp, 0x20
L0060 pop rsi
L0061 ret
L0062 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException()
L0067 int3
L0068 call 0x00007ff8a709f120
L006d int3
例外スローを関数に切り出したことから期待される通り、インライン化が実行され、インデクサーの関数呼び出しは消失し、境界値チェックも少ない命令数で表現され、配列への for に近いアセンブリが生成されています。しかし、配列の場合よりループ本体がやや長いようです。
List<T> では、Count (_size) を超えていないかどうかをチェックしていました。裏の配列の長さ、キャパシティは、List<T> としての長さより長いことがあるため、この独自の境界値チェックが必要なのです。もちろん、List<T> は普通のクラスなので、配列と異なりランタイムでの特殊扱いなどはなく、ループごとにチェックされます。
この時点で、裏の配列へのアクセスが範囲外にならないことは保証されています。しかし、前回説明したように配列への境界値チェックの最適化は結構狭い範囲を見て自明かどうかを判断しており、ここまで大局的な判断はしてくれません。よって、無慈悲にも境界値チェックがランタイムによりさらに挿入されます。
結果として、ループ本体に境界値チェックが 2 回入るという悲しい結果になります。
L0025 ~ L002c の3命令が List<T> としての境界値チェック、L002e ~ L0035 が 裏側の配列への境界値チェックです。
これは、境界値チェック 0 回が実現できる配列への for と比較するとまぁまぁのペナルティで、今回だと 20% 程度のオーバーヘッドになっています。
List への foreach
List<T> への foreach に関して注目されるのは
-
forより低速 -
IEnumerable<T>扱いより高速
という点です。配列の場合とは異なり、foreach が for 相当に展開されるということはやはりないので、一旦は GetEnumerator() ~ MoveNext() ~ Current にコンパイルされます。
IL_0000 ldsfld Benchmark.list
IL_0005 callvirt List <Int32>.GetEnumerator ()
IL_000A stloc.0
IL_000B br.s IL_001F
IL_000D ldloca.s 00
IL_000F call Enumerator <Int32>.get_Current ()
IL_0014 ldc.i4 FF E0 F5 05 // 99999999
IL_0019 bne.un.s IL_001F
IL_001B ldc.i4.1
IL_001C stloc.1
IL_001D leave.s IL_003A
IL_001F ldloca.s 00
IL_0021 call Enumerator <Int32>.MoveNext ()
IL_0026 brtrue.s IL_000D
IL_0028 leave.s IL_0038
IL_002A ldloca.s 00
IL_002C constrained. List <T>.Enumerator
IL_0032 callvirt IDisposable.Dispose ()
IL_0037 endfinally
IL_0038 ldc.i4.0
IL_0039 ret
IL_003A ldloc.1
IL_003B ret
ここで、foreach の仕様の面白い部分があります。「foreach は IEnumerable を処理できる」は正しいですが、実はそれ以外も処理することができるのです。
つまり、GetEnumerator() の部分はいわゆるダックタイピングになっていて、IEnumerable を実装することは必要条件ではなく、単に GetEnumeraor というメソッドを実装すればよいです。シンプルに {object}.GetEnumerator() というコード相当に展開されるため、インスタンスメソッド・拡張メソッドの別も問いません。
この仕様を List<T> はうまく活用しています。
public Enumerator GetEnumerator()
=> new Enumerator(this);
IEnumerator<T> IEnumerable<T>.GetEnumerator()
=> new Enumerator(this);
IEnumerator IEnumerable.GetEnumerator()
=> new Enumerator(this);
と、IEnumerable<T> インターフェイスを実装するための GetEnumerator とは別の GetEnumerator メソッドが用意されているのです。
そして、foreach はダックタイピングなので、ここでオーバーロード解決が入ります。もちろん、一致度が高い List<T>.GetEnumerator に解決されます。
このとき、Enumerator として、IEnumerator<T> 型ではなく、具象型の List<T>.Enumerator 型が返っています。
この型は以下のような 構造体 です。
public struct Enumerator : IEnumerator<T>, IEnumerator
{
private readonly List<T> _list;
private int _index;
private readonly int _version;
private T? _current;
internal Enumerator(List<T> list)
{
_list = list;
_index = 0;
_version = list._version;
_current = default;
}
public void Dispose()
{
}
public bool MoveNext()
{
List<T> localList = _list;
if (_version == localList._version && ((uint)_index < (uint)localList._size))
{
_current = localList._items[_index];
_index++;
return true;
}
return MoveNextRare();
}
private bool MoveNextRare()
{
if (_version != _list._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = _list._size + 1;
_current = default;
return false;
}
public T Current => _current!;
object? IEnumerator.Current
{
get
{
if (_index == 0 || _index == _list._size + 1)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return Current;
}
}
void IEnumerator.Reset()
{
if (_version != _list._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = 0;
_current = default;
}
}
結果として、MoveNext() や Current が静的関数呼び出しになります。
これがダックタイピング、パターンベースの強い所の1つで、インターフェイスを介する場合に発生する仮想関数呼び出しのコストを回避できるのです。
静的関数呼び出しはインライン化できますから、foreach はJITコンパイル時には関数呼び出しがすべて消失します。
L0000 sub rsp, 0x28
L0004 mov rcx, 0x7ff847e3cea8
L000e mov edx, 1
L0013 call 0x00007ff8a709dae0
L0018 mov rdx, [rax+8]
L001c mov edx, [rdx+0x14]
L001f mov rax, [rax+8]
L0023 mov edx, [rax+0x14]
L0026 mov ecx, edx
L0028 xor r8d, r8d
L002b jmp short L0036
L002d cmp r9d, 0xf423f
L0034 je short L0076
L0036 cmp ecx, edx
L0038 jne short L0080
L003a cmp r8d, [rax+0x10]
L003e jae short L0067
L0040 mov r9, [rax+8]
L0044 cmp r8d, [r9+8]
L0048 jae short L0086
L004a movsxd r10, r8d
L004d mov r9d, [r9+r10*4+0x10]
L0052 inc r8d
L0055 mov r10d, 1
L005b test r10d, r10d
L005e jne short L002d
L0060 xor eax, eax
L0062 add rsp, 0x28
L0066 ret
L0067 mov r8d, [rax+0x10]
L006b inc r8d
L006e xor r9d, r9d
L0071 xor r10d, r10d
L0074 jmp short L005b
L0076 mov eax, 1
L007b add rsp, 0x28
L007f ret
L0080 call System.ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion()
L0085 int3
L0086 call 0x00007ff8a709f120
L008b int3
と、foreach の C# コンパイラのレベルでのコンパイル結果からは想定できないくらいマシなアセンブリが生成されます。
ただし、
- もちろん、配列への境界値チェックの最適化は入らない
-
forのときの 2 重境界値チェックはないが、列挙中にList<T>が編集されていないことを保証する比較がある - 終端に達した場合の特殊対応がある
と、やはりオーバーヘッドはそれなりにあり、List<T> への for のときよりさらにループ本体が長くなっています。
これはベンチマーク結果にも表れていて、配列や List<T> への for よりさらに遅いです。
しかし、IEnumerable<T> 扱いより 5 倍 も高速であることはとにかく素晴らしいの一言です。
これはおもにインライン化の恩恵であり、ダックタイピングが生きています。
追記：ForEach メソッド
ちょうどこの記事を書いている頃、別の方がこんな記事を書いていました。
ForEach メソッドの存在を忘れていたのですが、せっかくなので検証してしまいましょう。
こんなテストケースを追加します。
public bool ListForeachMethod()
{
bool found = false;
list.ForEach(n =>
{
if (n == target)
{
found = true;
}
});
return found;
}
結果
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
N=1M
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 530.3 μs | 3.46 μs | 3.07 μs |
| ListFor | 826.6 μs | 2.84 μs | 2.37 μs |
| ListForeach | 1,107.3 μs | 9.96 μs | 9.31 μs |
| ListForeachMethod | 2,184.0 μs | 7.19 μs | 5.61 μs |
| SpanList | 293.8 μs | 1.93 μs | 1.51 μs |
| IEnumerableListForeach | 4,654.7 μs | 35.60 μs | 31.55 μs |
| ListLinq | 174.6 μs | 0.37 μs | 0.31 μs |
N=100M
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 57.13 ms | 0.273 ms | 0.242 ms |
| ListFor | 83.72 ms | 0.503 ms | 0.446 ms |
| ListForeach | 111.20 ms | 0.144 ms | 0.113 ms |
| ListForeachMethod | 219.46 ms | 1.657 ms | 1.384 ms |
| SpanList | 38.29 ms | 0.287 ms | 0.255 ms |
| IEnumerableListForeach | 465.18 ms | 5.701 ms | 5.054 ms |
| ListLinq | 27.10 ms | 0.290 ms | 0.271 ms |
と、元記事と同じ傾向の結果が得られました。
考察
結果を得て満足せずに、原因を探しに行き汎用的なテクニックを発見するのが私のモットーなので今回も考察をしましょう。
まずは ForEach メソッドのソースコードをば。
public void ForEach(Action<T> action)
{
if (action == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
}
int version = _version;
for (int i = 0; i < _size; i++)
{
if (version != _version)
{
break;
}
action(_items[i]);
}
if (version != _version)
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
- 実態は
for文- だがループ条件が最適化掛かる形式ではないので境界値チェックが入る
- とはいえ、二重ではない
-
List<T>が列挙中に変更されてないことを確認している- ただし、ループの前と後で比較してるだけでループごとに確認はしてない
-
Action<T>による仮想関数呼び出しがある- インライン化を阻害
しかし、ForEach は標準ライブラリ内の関数なので、そのままでは LinqPadで逆アセンブルできないのでどうしたものか悩んだのですが
結局 List<T>のソースコードの要所をコピペして逆アセンブルしました。
L0000 push rdi
L0001 push rsi
L0002 push rbp
L0003 push rbx
L0004 sub rsp, 0x28
L0008 mov rsi, rcx
L000b mov rdi, rdx
L000e test rdi, rdi
L0011 je short L0053
L0013 mov ebx, [rsi+0x14]
L0016 xor ebp, ebp
L0018 cmp dword ptr [rsi+0x10], 0
L001c jle short L0045
L001e cmp ebx, [rsi+0x14]
L0021 jne short L0045
L0023 mov rcx, [rsi+8]
L0027 cmp ebp, [rcx+8]
L002a jae short L0076
L002c movsxd rdx, ebp
L002f mov rdx, [rcx+rdx*8+0x10]
L0034 mov rax, rdi
L0037 mov rcx, [rax+8]
L003b call qword ptr [rax+0x18]
L003e inc ebp
L0040 cmp ebp, [rsi+0x10]
L0043 jl short L001e
L0045 cmp ebx, [rsi+0x14]
L0048 jne short L0070
L004a add rsp, 0x28
L004e pop rbx
L004f pop rbp
L0050 pop rsi
L0051 pop rdi
L0052 ret
L0053 mov ecx, 1
L0058 mov rdx, 0x7ffe2ec8c060
L0062 call 0x00007ffe8e010390
L0067 mov rcx, rax
L006a call ThrowHelper.ThrowArgumentNullException(System.Object)
L006f int3
L0070 call ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion()
L0075 int3
L0076 call 0x00007ffe8e16f120
L007b int3
ループ本体に関数ポインタをオペランドにした call 命令が残っていることがわかります。
for でみられた、二重の境界値チェックや、foreach でみられた、バージョンの確認といったコストは回避できているのですが、
ループ本体に関数ポインタによる関数呼び出しが残っていることのペナルティが非常に大きいです。
ということで、仮想関数呼び出しとそれに伴うインライン化阻害のペナルティが致命的で、foreach よりは低速であるが、
いずれにせよ仮想関数呼び出しを避けられない IEnumerable<T> 扱いと比較すれば、MoveNext() ~ Current とループごとに二回呼び出すよりマシですし
境界値チェックやバージョン確認のコストは比較的回避できている、というところでしょうか。
内部イテレーター vs 外部イテレーター
foreach などの、列挙操作の実装として、内部イテレーターと外部イテレーターの2つがあります。
List<T>.ForEach メソッドは、コレクション内部で列挙操作を実装し、列挙ごとに行うメソッドを外部から挿入してもらう方式になっていますが、こういうのを、列挙操作をコレクション内部で実装することから、内部イテレーターと呼びます。
逆に、foreach では、MoveNext() ~ Current メソッドを公開することで、要素の取得操作をする方法を提供されています。ループ (制御フローを前に飛ばす行為) は利用者側で行うことから、こういうのは外部イテレーターと呼ばれます。
つまり、List<T>.ForEach と foreach とのパフォーマンス差というのは、内部イテレーターと外部イテレーターのパフォーマンス差と言えるわけです。
ご存知の通り、C# は IEnumerable<T> 経済圏なので、言語全体として外部イテレーターを選択したことになります。
外部イテレーターの方が柔軟に操作ができる、などのメリットもありますが (途中でやめたり、無限に続くイテレーターを作ったりしてもOK) 、実装が複雑になります。
通説では、実装が複雑で MoveNext() ~ Current とループあたり2回呼び出さなければいけない外部イテレーターの方が遅いことになっていますが、
- ラムダ式で渡したものはインライン化されない
- 内部イテレーターは絶対にインライン化されない - foreach はダックタイピング
GetEnumeraotrを介する- 外部イテレーターは、
List<T>など具象型に対してはインライン化される可能性がある
- 外部イテレーターは、
ということを考慮すると、先程のように、
List<T>に外部イテレーター < List<T>に内部イテレーター < IEnumerable<T>に外部イテレーター
という実行時間順になります。つまり、
- 具象型(
List<T>など) には 外部イテレーターが高速 - 抽象型(
IEnumerable<T>など) には 内部イテレーターが高速
という事情になるわけです。この辺は foreach がダックタイピングにした言語設計者の妙という感です。
List<T> の Span<T> 化
では、最後に List<T> に対するループを高速化する方法を検討します。
逆アセンブル結果を踏まえると、for ループを回すときに、境界値チェックが 2 回も入るのが問題でした。これを 0 回に減らすことができれば、オーバーヘッドはなくなるでしょう。
これには、配列に対する場合と同じような境界値チェックの最適化を、任意の型に対して適用できればよいことは明らかです。
しかし、無数にある型それぞれを特殊扱いするようにランタイムに手を入れるのは、メンテナンスなども含めれば高コストで、いい選択ではありません。
よって、このニーズはありながらもずっと配列だけが特殊扱いされる状況で、これを回避するにはアンマネージドポインタくらいしか選択肢がありませんでした。
しかし、C# 7時代に Span<T> という包括的な解決策が導入されました。
これにより、「境界値チェックの最適化」を配列以外でも享受できるようになったのです。
さらに、.NET 5 で List<T> を Span<T> に変換するメソッドが標準ライブラリに導入され、(それ以前から黒魔術的に知られていた手法ではありましたが)、List<T> の Span<T> 化は、かなり実践的な最適化テクニックに昇格した感があります。
Span<T> 化の理屈はシンプルで、List<T> の裏側の配列のうち、「List<T> の Count まで」をスライスして取得するだけです。
この領域は、もとの List<T> の要素数を変更しない限り 範囲外になる可能性はありません。
なお、もとの List<T> の要素数を変更しない限り の部分は 実装者責任 です。
やり方はとてもシンプルで、
System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list)
で終わりです。このメソッドの内部実装は
public static Span<T> AsSpan<T>(List<T>? list)
=> list is null ? default : new Span<T>(list._items, 0, list._size);
と、やはりかなり単純です。しかし、ベンチマークをとると
| Method | Mean | Error | StdDev |
|---|---|---|---|
| ArrayFor | 530.3 μs | 7.36 μs | 6.89 μs |
| ConstArrayFor | 547.2 μs | 2.47 μs | 2.06 μs |
| ListFor | 625.0 μs | 10.18 μs | 9.03 μs |
| ListForeach | 1,097.5 μs | 11.69 μs | 10.36 μs |
| IEnumerableListForeach | 5,215.4 μs | 68.93 μs | 61.10 μs |
| SpanList | 289.3 μs | 0.83 μs | 0.65 μs |
と、驚異的 なパフォーマンスが出ます。
Span<T> の方が配列より早いという不思議な結果が出てしまいました。
このへんの謎は、また次回解説したいと思います。
次回