List<T>の話
困ったことにList<T>を最近使いたくありません。
List<T>の場合.NET Framework 4.5 時点でいまだに for と foreach では、 forが高速に組めます。
コンパイラやJITの最適化が進化すれば同じ速度になるかと思いきや、いつまで経っても foreachの方が遅いのです。
あっさり言うと理由は2つあります。
- foreachはILコード上は try~finallyで囲われており、Disposeが呼ばれます。IEnumeratorがIDisposableを持っているので仕方ありません。中身は空ですが、インターフェースに対するILのcallvirt(遅延バインディングのcall命令)はインライン展開も省略もしません。
- 列挙子でMoveNext()とCurrentをアクセスするより、List<T>のインデクサ1回アクセスの方が高速です。
興味深いのはList<T>のインデクサは callvirt なのに思いのほか高速なことです。(とはいえ、2回程度同じリストにアクセスする場合は ToArray()してアクセスした方が高速な場合が多いようです。配列とList<T>ですら、速度面ではそれだけの隔たりがあります。しかし、マクロな視点ではGCが効率化されない可能性もあるので、この辺りは丹念な計測で決定づけるべき要素です。)
また、List<T>には専用の struct List<T>.Enumerator が実装されており、それらのメソッドはIL上は call なので (structは継承しないためインターフェースが callvirtにならないので)インライン展開が容易な形になります。
それでも、インデクサより速くはなりません。理由は List<T>.Enumerator.MoveNext() の実装が ILで81バイトあり、インライン展開しないほどのサイズとなっているためです。(.NET Frameworkは通常、32バイトを超えるメソッドをインライン展開しません。*1)
いえ、ここで重要なのはインライン展開がどうのというよりは、ちょっと処理量が多いことでしょうか。どう見ても列挙中にリストが変更されたことを検知することに躍起です。
そのコードはここにあります。
http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs#1209
このあたりのコードを読ませていただきますと、実装方針としてcallにせよcallvirtにせよ、メソッドの呼び出しを減らす設計というものは常に大事です。
また、.NET Frameworkの各種クラスは、GCを強く信頼しながらメモリを最小限に扱うことと、不味い組み方に耐えることには長けていますが、動作が最も速いコードではないことを覚えておく必要があります。
独自のコレクションを作る際には、列挙子の各メソッドをILコード32バイト以下にするための独自実装を行う、というのも実は結構重要なポイントになります。
あと、列挙時にEnumeratorではなくインデクサを使うという最適化ヒントを与える属性でもあれば良いのですが・・・。ただ、foreach中にリストが変更された場合の扱いはやや難しいものになりますが。
これらの点は近いうちにもう少し掘り下げます。