標準ライブラリのLINQオペレータにはパフォーマンス向上のための様々なトリックが仕込まれている。
実装をざっと調べたので、その成果をここにまとめておく。
- 調査対象は.Net Core 2.。
- オーダーが同じだからと言ってパフォーマンスが同じとは限らない。
- 結構雑な調査なので信用しすぎないように。
- 項目について
- シグニチャの特殊化 :オーバーロードによって最適化の度合いが異なる場合、各オーバーロードを表す。
- ソースの特殊化 : ソースシーケンスの具象型によって最適化の度合いが異なる場合、各具象型を表す。
-
コールスタック : オペレータ利用による、
MoveNext/Currentのコールスタック深さの増加分を表す。深くなるとcallvirt呼び出しが増えるためパフォーマンスが劣化する。 - 戻り値の特殊化型 : オペレータの戻り値が他のオペレータのパフォーマンス向上に寄与するような具象型を持つとき、その具象型を列挙する。
- オーダーの記号について
- $n$: ソースシーケンスの要素数。複数のソースからなる場合は添え字が省略されている。
- $k$: ソースの要素値とオペレータの引数で決まる定数。O記法ではふつうこのような値を使わないが、LINQを考える上ではなかなかに効いてくるので便宜的に導入する。
集計メソッド
|
|
|
|
|
|---|---|---|---|---|
| メソッド名 | シグニチャの特殊化 | ソースの特殊化 | 時間計算量 | 備考 |
Aggregate |
$O(n)$ | |||
Any |
$O(n)$ | |||
All |
$O(n)$ | |||
Average |
$O(n)$ | |||
Contains |
$O(n)$ | |||
Count |
$O(n)$ | |||
ElementAt |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
ElementAtOrDefault |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
First |
$O(1)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
FirstOrDefault |
$O(1)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
Last |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
LastOrDefault |
$O(n)$ | |||
IPartition |
$O(1)$ | |||
IList |
$O(1)$ | |||
Max |
$O(n)$ | |||
Min |
$O(n)$ | |||
SequenceEqual |
$O(n)$ | 両シーケンスがICollectionの場合、事前に要素数チェックが入る。両シーケンスがIListの場合、イテレータではなくインデクサでアクセスするためcallvirt呼び出しが減る。 |
||
ICollection |
$O(n)$ | |||
IList |
$O(n)$ | |||
Single |
$O(1)$ | シーケンスがIListの場合、Countとインデクサにより処理される。 |
||
IList |
$O(1)$ | |||
Sum |
$O(n)$ | |||
ToArray |
$O(n)$ | シーケンスがIListProviderの場合、各インターフェースに実装されたアルゴリズムで処理される。 |
||
IListProvider |
$O(n)$ | |||
ToList |
$O(n)$ | |||
IListProvider |
$O(n)$ | |||
ToDictionary |
$O(n)$ | シーケンスが配列またはListの場合、専用のアルゴリズムで処理される。シーケンスが ICollectionの場合、Countをもとに初期キャパシティを取得する。 |
||
ICollection |
$O(n)$ | |||
T[] |
$O(n)$ | |||
List |
$O(n)$ | |||
ToHashSet |
$O(n)$ |
射影メソッド
|
|
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|
| メソッド名 | シグニチャの特殊化 | ソースの特殊化 | コールスタック | 時間計算量 | 戻り値の特殊化型 | 備考 | |
| 最初の1件 | 全件 | ||||||
Append |
1 | $O(1)$ | $O(n)$ |
AppendPrependIterator, Iterator, IListProvider
|
AppendPrependIteratorはソースと前後のリンクリストを保持する。AppendPrependIteratorへのAppend/Prependはリンクリストを延長するだけなのでコールスタックが深くならない。 |
||
AppendPrependIterator |
0 | $O(1)$ | $O(n)$ | ||||
Prepend |
1 | $O(1)$ | $O(n)$ |
AppendPrependIterator, Iterator, IListProvider
|
|||
AppendPrependIterator |
0 | $O(1)$ | $O(n)$ | ||||
OfType |
1 | $O(1)$ | $O(n)$ | ||||
Cast |
1 | $O(1)$ | $O(n)$ | ||||
Concat |
1 | $O(1)$ | $\sum O(n)$ |
ConcatIterator, Iterator, IListProvider
|
ConcatIteratorはシーケンスのリンクを保持する。ConcatIteratorへのConcatはリンクを延長するだけなのでコールスタックが深くならない。 |
||
ConcatIterator |
0 | $O(1)$ | $\sum O(n)$ | ||||
DefaultIfEmpty |
1 | $O(1)$ | $O(n)$ | ||||
Distinct |
1 | $O(1)$ | $O(n)$ |
Iterator, IListProvider
|
|||
Except |
1 | $O(n_{inner})$ | $\sum O(n)$ |
Setに依存。 |
|||
GroupJoin |
1 | $O(n_{inner})$ | $\sum O(n)$ |
Lookupに依存。 |
|||
GroupBy |
1 | $O(n)$ | $O(n)$ | ||||
Intersect |
1 | $O(n_{inner})$ | $\sum O(n)$ |
Setに依存。 |
|||
Join |
1 | $O(n_{inner})$ | $\sum O(n)$ |
Lookupに依存。 |
|||
ToLookup |
1 | $O(n)$ | $O(n)$ | IListProvider |
戻り値の実体はLookup。 |
||
OrderBy |
1 | $O(n)$ | $O(n)$ |
IPartition, IOrderedEnumerable
|
|||
Reverse |
1 | $O(n)$ | $O(n)$ | ||||
Select |
Func<T, TResult> |
1 | $O(1)$ | $O(n)$ |
Iterator, IListProvider
|
配列、ListはIListと同じオーダーだが、一部のメソッド呼び出しにより強力な最適化が働く。セレクタにインデックスをとるオーバーロードは最適化が弱い。 |
|
Iterator |
1 | $O(1)$ | $O(n)$ |
Iterator, IListProvider
|
|||
T[] |
1 | $O(1)$ | $O(n)$ |
Iterator, IPartition
|
|||
List |
1 | $O(1)$ | $O(n)$ |
Iterator, IPartition
|
|||
IList |
1 | $O(1)$ | $O(n)$ |
Iterator, IPartition
|
|||
IPartition |
1 | $O(1)$ | $O(n)$ |
Iterator, IPartition
|
|||
Func<T, int, TResult> |
1 | $O(1)$ | $O(n)$ | ||||
SelectMany |
Func<TSource, IEnumerable<TResult>> |
1 | $O(1)$ | $O(n)$ |
Iterator, IListProvider
|
セレクタにインデックスをとるオーバーロードは最適化が弱い。 | |
Func<TSource, int, IEnumerable<TResult>> |
1 | $O(1)$ | $O(n)$ | ||||
Skip |
1 | $O(k)$ | $O(n)$ | Iterator |
|||
IIterator |
0 ～ 1 | $O(k)$ | $O(n)$ | Iterator |
|||
IPartition |
0 | $O(1)$ | $O(n)$ | IPartition |
|||
SkipWhile |
1 | $O(k)$ | $O(n)$ | ||||
SkipLast |
1 | $O(1)$ | $O(n)$ | ||||
Take |
1 | $O(1)$ | $O(k)$ |
Iterator, IPartition
|
|||
IPartition |
0 | $O(1)$ | $O(k)$ |
Iterator, IPartition
|
|||
IList |
1 | $O(1)$ | $O(k)$ |
Iterator, IPartition
|
|||
TakeWhile |
1 | $O(1)$ | $O(k)$ | ||||
TakeLast |
1 | $O(n)$ | $O(n)$ | ||||
IPartition |
0 | $O(1)$ | $O(k)$ |
Iterator, IPartition
|
|||
IList |
1 | $O(1)$ | $O(k)$ |
Iterator, IPartition
|
|||
Union |
1 | $O(1)$ | $\sum O(n)$ |
UnionIterator, Iterator, IListProvider
|
UnionIteratorはシーケンスのリンクを保持し、イテレート時に重複の除外を行う。ソースがUnionIteratorで、かつ同じcomparerを使っているときはリンクを追加するだけなのでコールスタックが深くならない。 |
||
UnionIterator |
0 ～ 1 | $O(1)$ | $\sum O(n)$ |
UnionIterator, Iterator, IListProvider
|
|||
Where |
1 | $O(k)$ | $O(n)$ |
Iterator, IListProvider
|
配列、Listは一部のメソッド呼び出しにより強力な最適化が働く。セレクタにインデックスをとるオーバーロードは最適化が弱い。 |
||
T[] |
1 | $O(k)$ | $O(n)$ |
Iterator, IListProvider
|
|||
List |
1 | $O(k)$ | $O(n)$ |
Iterator, IListProvider
|
|||
Func<T, int, bool> |
1 | $O(k)$ | $O(n)$ |
Iterator, IListProvider
|
|||
Zip |
1 | $O(1)$ | $\min(O(n))$ | ||||
最適化に用いられる型
Iteratorクラス
LINQオペレータで広く利用される抽象クラス。IEnumerable, IEnumeratorを実装している。
ステートとスレッドIDを管理しており、自身を生成したスレッド内かつ唯一の利用ならGetEnumeratorが自身を返すことでオブジェクト数を増やさないようになっていたりする。
ステートフィールドの解釈は子クラス側に委ねられており、OOP的にはあまりよろしくない設計となっているが、パフォーマンスを出すためには仕方ないことなのだろうか。
IListProviderインターフェース
ToArray, ToListの専用実装を用意できるようにするインターフェース。
IPartitionインターフェース
ランダムアクセス可能なシーケンスであることを表すインターフェース。参照型向けのSpanみたいなもの。
Lookupクラス
ILookupの実装。ToLookupやGroupByなどで用いられる、グループキーとシーケンスの軽量な辞書。
Setクラス
軽量なハッシュセットクラス。System.Collections.Generic.HashSetはコアライブラリで使うにはリッチすぎるということだろうか。
まとめ
- 同じオペレータを連続適用すると効率が良い(ことがそこそこある)
-
Select/Whereはインデックス込みで評価できるオーバーロードを使うと最適化が利かなくなったりする。
最後に
正直こういうの考える必要があるほどパフォーマンスが大事なら素直にforeachで書いた方がいいと思う。
QiitaでHTML属性使えなくなってテーブルきれいに書くのとてもつらいんだけど誰かいい方法教えて