Collections

C#のコレクション式にToListの最適化を広げた話

RoslynにマージされたPR #85777。単一spreadからListを作る処理を共通化し、IListや読み取り専用インターフェースにも最適化を適用した。BDNの実測値と、レビューで確認した挙動の違いを残す。

C#のコレクション式で、代入先をList<int>からIList<int>に変えると、生成される処理も変わることがある。 今回調べたのは、LINQで絞り込んだ要素を[.. source]で新しいコレクションに詰めるケースだ。

List<int> concrete = [.. values.Where(static x => x >= 0)];
IList<int> mutable = [.. values.Where(static x => x >= 0)];
IReadOnlyList<int> readOnly = [.. values.Where(static x => x >= 0)];

既存のコンパイラーには、単一のspreadからList<T>を作るときにEnumerable.ToListを使う最適化があった。 その処理を共通の場所へ移し、インターフェース向けに内部でList<T>を作る場合にも適用した。 この変更を含むRoslyn PR #85777が、2026年10月7日午前6時19分(日本時間)にマージされた。

Windows x64の測定では、10万要素のWhere結果をIList<int>へ格納するケースが300.44 µsから97.51 µsになった。 ただし、1要素では速度改善を確認できず、例外などの挙動にも違いがあった。 どの条件で何が変わったのかを記録しておく。

AddRangeとToListで通る処理が違う

上の例のように、長さを事前に決めにくい列挙可能オブジェクトからIList<int>を作る場合、変更前の生成コードは概念的には次の形だった。 説明のためC#に書き戻している。

var result = new List<int>();
result.AddRange(values.Where(static x => x >= 0));
IList<int> mutable = result;

変更後は、条件を満たすと次の形になる。

IList<int> mutable = values.Where(static x => x >= 0).ToList();

どちらもList<int>を作るが、.NET 10の実装では内部の処理が異なる。 List<T>.AddRangeは、渡されたオブジェクトがICollection<T>なら件数を使って一括コピーできる。 それ以外は列挙子で要素を取り出し、Addを繰り返す。 結果の件数が増えると、Listの内部配列を拡張して既存の要素をコピーする処理も発生する。List.cs

一方、Enumerable.ToListには、LINQ自身のイテレーターならその型が持つToList実装を呼ぶ経路がある。 配列を対象とするWhereやWhere.Selectは、入力に直接アクセスし、SegmentedArrayBuilderを使って結果を蓄積する。 このため、同じ要素を返す処理でも、列挙の仕方や一時的なメモリ確保が変わる。 実装の説明には.NET 10.0.0のToCollection.csとWhere.SpeedOpt.csを参照した。 以下の実測に使ったランタイムは10.0.10だ。

今回Roslynで変えたのは、この既存のToList経路を利用する範囲だ。 RuntimeのAddRangeやLINQの実装そのものは変更していない。

既存の判定を共通処理へ移した

最終的な本体の差分は、最適化を呼び出す5行を移す変更になった。 具体的なList<T>を処理する場所にあった判定を、Listを生成する共通処理のCreateAndPopulateListへ移している。

これにより、IList<T>とICollection<T>に加え、内部でListを必要とするIEnumerable<T>、IReadOnlyCollection<T>、IReadOnlyList<T>でも同じ判定を利用できるようになった。 読み取り専用の結果では、作ったListをコンパイラー生成の読み取り専用コレクションで包む処理が残る。 IReadOnlyList<T>への代入が、変更可能なListをそのまま返すようになるわけではない。

適用できるかどうかは、既存のヘルパーが引き続き判断する。 例えば、spreadが一つであること、利用するEnumerable.ToListが参照先に存在すること、必要な型変換が適合することを確認する。 値型の列挙子を持つ独自コレクションについても、既存の判定を保った。

したがって、[0, .. source]のように通常要素が混ざるケースや、要素ごとの数値変換が必要なケースまで一律にToListへ変換してはいない。 明示的に作ったListへ追加するwith(...)のケースも、そのListを使う処理を維持する。 長さが分かる読み取り専用ターゲットの配列生成や、配列とSpan向けの既存のToArray最適化も残している。最終実装

コンパイラーを変えて生成したプログラムを測る

今回はコンパイラーの変更なので、同じベンチマーク用C#を変更前と変更後のコンパイラーでそれぞれビルドした。 その二つのアセンブリを、BenchmarkDotNetの測定用プログラムから読み込んで実行している。 測定時にBDNがコレクション式を同じコンパイラーでビルドし直してしまうと、比較したい差が失われるためだ。

測ったのは生成されたプログラムの実行時間と確保量であり、コンパイルにかかる時間ではない。 セットアップ、リフレクションによる呼び出し準備、結果の検証は測定区間の外に置いた。

環境はWindows 11 x64、AMD Ryzen AI 9 HX 370、.NET 10.0.10、BenchmarkDotNet 0.15.8だ。 MemoryDiagnoserを使用し、CPU affinityを論理CPU 0に設定した。 普段も使うPCなので、専用の測定機ほど条件を揃えられる環境ではない。

最初の測定では、コードを変えていない対照ケースでも時間が動いた。 そこで実行順をA、B、B、Aとし、各プロセスで5秒間の事前実行を行ってから、ウォームアップ15回と測定15回を実施した。 下表の時間は、各コンパイラーで行った2回の独立した起動の平均値を、さらに平均したものだ。 外れ値は除外していない。

変更は二段階で測定したため、以下の二表は比較の基準が異なる。 可変インターフェースの測定は変更前のmainと最初の修正を比較し、読み取り専用インターフェースの測定は、その最初の修正と共通化した修正を比較している。 異なる表の時間を使って、IList<T>とIReadOnlyList<T>の速さを直接比べることはできない。

可変インターフェースの測定結果

次の表は、変更前の8ddc2f18d7a2と、可変インターフェース向けの修正307e04425fc5の比較だ。 各測定イテレーションには200 msを指定した。 入力はint[]で、ここに載せたWhereの述語は全要素を通す。 Where.Selectでは、その後に各値へ1を加える。

ケース 変更前 変更後 変更前 B/op 変更後 B/op
IList、Where、100,000要素 300.44 µs 97.51 µs 1,049,206 400,187
IList、Where.Select、100,000要素 313.99 µs 105.02 µs 1,049,282 400,225
IList、Where、8要素 27.73 ns 14.95 ns 176 136
IList、Where、1要素 14.46 ns 14.70 ns 120 112
AddRangeを直接呼ぶ対照、100,000要素 304.81 µs 303.45 µs 1,049,214 1,049,192

10万要素のWhereでは、平均時間が約68%減り、確保量も約1.05 MBから約0.40 MBへ減った。 この確保量は1操作全体の値であり、単一の配列のサイズではない。 大きなケースの確保量には測定上の小さな変動もある。

一方、1要素の時間は14.46 nsから14.70 nsだった。 2組の比較では変更後/変更前の比率が1.167と0.872に分かれ、速くなるか遅くなるかが揃わなかった。 このケースで確認できたのは、確保量が120 Bから112 Bへ減ったことだ。

初回の72ケースの測定では、対照も含む13ケースに実行途中の時間変動が見られ、その13ケースを追加測定した。 表はその追加測定からの抜粋で、初回の観測も残している。 全13ケースの結果と初回の全結果を参照できる。

読み取り専用インターフェースの測定結果

次の比較は、可変インターフェースへの最適化が入った307e04425fc5と、読み取り専用側にも適用したf4d3fb7の間で行った。 各ケース内でA、B、B、Aを連続して実行し、測定イテレーションには500 msを指定した。 入力配列は0から始まる連番で、述語x >= 0は全要素を通す。

ケース 共通化前 共通化後 共通化前 B/op 共通化後 B/op
IReadOnlyList、Where、100,000要素 372.81 µs 157.20 µs 1,049,143 400,211
IReadOnlyList、Where、1要素 22.46 ns 20.86 ns 144 136
IEnumerable、Where、1要素 24.54 ns 22.63 ns 144 136
変更のないIList対照、100,000要素 164.24 µs 181.68 µs 400,188 400,188
変更のないIList対照、1要素 18.62 ns 18.51 ns 112 112

10万要素のIReadOnlyListでは、2組とも時間が短くなり、変更後/変更前の比率は0.405と0.440だった。 一方、変更していない10万要素のIList対照では、4回の起動のうち1回だけ202.71 µsまで遅くなった。 残りは160.65、163.59、164.89 µsで、この平均値の悪化をコンパイラー変更によるものとは判断できない。 同じ理由で、1要素の小さな差から細かい改善率を主張することも避けたい。

読み取り専用側も、初回25ケースの全結果と、5ケースを追加測定した結果を分けて保存した。 初回には1要素のIEnumerableが24.80 nsから25.10 nsへ遅くなる観測もあったが、追加測定では再現しなかった。追加測定、初回25ケース

その後、レビューに合わせて具体的なListの分岐も修正した。 修正後のコンパイラーで測定用プログラムを再ビルドし、測定済みの共通化版とアセンブリがバイト単位で一致することを確認した。 この修正後にBDNの時間測定をやり直したわけではない。 また、後述するdynamicのケースは、この速度表には含めていない。対応関係を記載したPR本文

以前の狭い修正版をMac ARM64と.NET 12開発版で測った際には、1要素でCPU時間が悪化する結果も出ていた。 今回のWindowsでの結果によって、その観測を取り消すことはできない。 採用した変更でも、すべての入力や実行環境で速くなると確認できたわけではない。

例外と副作用も同じとは限らない

AddRangeをToListへ置き換えれば、同じ値が得られる通常ケースだけでなく、例外や列挙中の副作用も確認する必要がある。 .NET 10.0.10上の比較では、次の違いを観測した。

条件 変更前の経路 ToListを使う経路
nullのIEnumerable<int> ArgumentNullException、引数名collection ArgumentNullException、引数名source
nullのint[]から可変インターフェースを生成 NullReferenceException ArgumentNullException、引数名source
Whereの述語内で入力Listへ要素を追加する検証ケース InvalidOperationException 元の2要素を返して完了

最後の行は、列挙中の変更を一般に安全に扱えるという意味ではない。 入力に副作用を与える特定のプログラムで、利用するLINQの経路によって観測結果が違ったという記録だ。 nullの列挙可能オブジェクトと入力Listへの追加については、読み取り専用の3種類のインターフェースでも違いを確認した。 それらは既存の具体的なList<T>向けの生成コードと同じ結果だった。挙動の比較記録

これらの差もPRに明記した。 最適化の適用条件を満たし、テストが通ったことだけから、すべての入力で挙動が完全に同じとは言えない。

dynamicのAddをどう扱ったか

レビューで特に調べたのは、dynamicの要素をList<object>へ追加する場合だった。 実行時にAddを解決するループと、ToListでコピーする処理では、要素の参照同一性が違うケースがある。

object boxed = 42;
IEnumerable<dynamic> source = new object[] { boxed };

List<object> copied = source.ToList();
var loop = new List<object>();
foreach (dynamic item in source)
{
    loop.Add(item);
}

Console.WriteLine(ReferenceEquals(boxed, copied[0])); // True
Console.WriteLine(ReferenceEquals(boxed, loop[0]));   // False

copiedは元のboxへの参照をコピーする。 一方、このloop.Add(item)では、C#の実行時バインダーが引数を実行時の型intとして扱い、Add(object)へ渡す際にboxingする。 調べたバインダーの式もobject → int → objectという変換になっており、同じ42でも新しいboxになる。 loop.Add((object)item)と明示すれば、その動的な呼び出しを避けて元の参照を保てる。調査結果への返信

最終的には、レビューで示された方針に従い、Addを動的に解決するケースではコレクション初期化子として処理する形に整理した。 ここで既存の挙動が仕様上のバグだと確定したわけではない。 そのケースの最適化を広げる議論は今回進めず、既存のuseListOptimization判定を通す構成にした。Rikkiの判断

小さい本体変更と長いILテスト

本体で移した処理は5行だが、テストの差分は大きくなった。 当初は、生成されたILにToListが含まれるかどうかを部分一致で確認していた。 レビューでメソッド全体を検証するVerifyILを使うよう指摘を受け、7テスト内の部分一致チェック14か所を置き換えた。レビューコメント

この修正だけで643行追加、31行削除になった。 型の違い、数値変換、boxing、列挙子の破棄、読み取り専用のラッパーまで、生成されるメソッド全体を期待値として残したためだ。 冗長にはなるが、目的の呼び出しが存在することに加えて、その前後に意図しない処理が増えたときにもテストで気付ける。

最終push前には、Release/net10.0でアナライザーを有効にしたビルドを行い、警告とエラーは0だった。 コレクション式関連のテストは2,058件成功、7件スキップ、失敗0だった。 これは関連テスト群の結果であり、Roslyn全体のテスト件数ではない。最終返信

測定データと利用できる時期

本文の表に使った集計値は、可変インターフェースのJSONと読み取り専用インターフェースのJSONにも保存した。 どちらも2回の起動ごとの値を含み、表では省いたケースも残している。 比較したコミットと公開済みの測定資料へのリンクはデータの目録からたどれる。

再現用のソース、コンパイラーのハッシュ、BDNの出力は、次の二組に分かれている。

今回のマージは、変更を含むコンパイラーが一般向けSDKへ配布されたことを意味しない。 この記事では、利用可能になるSDKのバージョンまでは確認していない。 また、コンパイル時の変換なので、実行先のRuntimeを更新するだけで既存のアセンブリの生成コードが変わることもない。

マージされたのは、既存のLINQ最適化を利用する機会を増やす変更だ。 アプリケーションで効果を確認するときも、代入先の型だけでなく、生成したコンパイラー、入力の種類と件数、実行するRuntimeを揃えて比べたい。