Deep Dive into LINQ シリーズ記事一覧
はじめに
この記事は Deep Dive into LINQ シリーズの第3回目の記事です。
Deep Dive into LINQ シリーズでは、 LINQ の内部実装やパフォーマンス特性について基本的なことから調べていきます。
前回に引き続き LINQ の First メソッドについて研究していきます。
今回は実際にコードを眺めて処理の流れを追っていきます。
ざっくり実装を眺めてみる
それでは、 First、 FirstOrDefault メソッドの実装を眺めていきましょう。
コード全文は こちら から読めます。
First メソッドにもいろいろなバリエーションがあるので、まずはすべてのバリエーションをざっと眺めます。
いずれのメソッドでも、肝となるのは「最初の要素を探してくる」という処理ですが、この処理は TryGetFirst というメソッドに委譲されています。
この TryGetFirst ついてはこの記事の後半で詳しく見ていきます。
条件なし First メソッド
まずは条件なしの（追加で引数をとらない） First メソッドを読んでみます。
この First メソッドでは、 TryGetFirst メソッドを使って最初の要素の取得を試みます。
要素が見つからなければ例外を発生させ、要素が見つかればその要素を返します。
public static TSource First<TSource>(this IEnumerable<TSource> source)
{
TSource? first = source.TryGetFirst(out bool found);
if (!found)
{
ThrowHelper.ThrowNoElementsException();
}
return first!;
}
条件なし FirstOrDefault メソッド
次に条件なしの FirstOrDefault メソッドを読んでみます。
これも First メソッドとほとんど同じですが、例外を発生させない点が違います。
public static TSource? FirstOrDefault<TSource>(this IEnumerable<TSource> source) =>
source.TryGetFirst(out _);
TryGetFirst メソッドは通常の Try パターンとは異なり、戻り値に処理の結果を返し、 out 引数に処理の成否を返しています。
この形だと FirstOrDefault の実装がシンプルになるメリットがありますね。
また、要素が見つからなかった場合の既定値を指定できるオーバーロードも存在します。
public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, TSource defaultValue)
{
TSource? first = source.TryGetFirst(out bool found);
return found ? first! : defaultValue;
}
このメソッドでは、 found （要素が見つかったかどうかのフラグ）を捨てずに取っておいて、
true なら TryGetFirst の結果を、そうでなければ指定された既定値を返します。
条件付き First メソッド
次に条件付きの First メソッドを見てみます。
これは各要素が条件を満たすかどうかを判定する predicate 関数を引数にとり、最初に条件を満たした要素を返します。
このメソッドの構造は、TryGetFirst に predicate 関数を渡している以外、条件なしの First メソッドとほぼ同じです。
public static TSource First<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
TSource? first = source.TryGetFirst(predicate, out bool found);
if (!found)
{
ThrowHelper.ThrowNoMatchException();
}
return first!;
}
条件付き FirstOrDefault メソッド
FirstOrDefault メソッドにも条件付きのものがあります。基本的には First メソッドと同じで、 TryGetFirst に処理のほとんどが委譲されています。
public static TSource? FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) =>
source.TryGetFirst(predicate, out _);
条件なしの First メソッドの場合と同じように、既定値を指定するオーバーロードも存在します。
public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate, TSource defaultValue)
{
TSource? first = source.TryGetFirst(predicate, out bool found);
return found ? first! : defaultValue;
}
TryGetFirst メソッドを読む
以上でみてきたコードでは、「最初の要素を探してくる」という処理は TryGetFirst メソッドに隠されていました。
次に、 TryGetFirst メソッドを読んで、どのような処理になっているのか確認してみましょう。
条件付き TryGetFirst
まず、「条件付きの」TryGetFirst から読んでいきます。
これは要素が満たすべき条件を Func<TSource, bool> で受け取り、条件を満たす最初の要素を返すものです。
private static TSource? TryGetFirst<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate, out bool found)
{
if (source == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
}
if (predicate == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.predicate);
}
foreach (TSource element in source)
{
if (predicate(element))
{
found = true;
return element;
}
}
found = false;
return default;
}
まず foreach で各要素に対してループを回します。
条件（predicate 関数） を満たす要素が見つかり次第、その要素を返します。
このとき、 out 引数である found フラグが true に設定されます。
このフラグは「要素が見つかった」ことを呼び出し元に伝える役割を果たします。
もし foreach が終わってしまった場合、
すなわち、ひとつも predicate を満たす要素が存在しなかった場合は、
found フラグを false に設定し、型の既定値を返します。
前回の記事 で作った自作のものとほとんど変わりない単純な実装になっています。
条件なし TryGetFirst
次に条件なしの TryGetFirst を見ていきます。
条件がないということは、「最初の要素を取り出して返す、空っぽなら既定値を返す」という簡単な処理で済むはずです。
実際、前回の記事 の自作の実装はとてもシンプルな実装になっていました。
しかし、.NET 6 の実装は少し複雑に見えます。
前回の記事の実装と根本的に違うのは、特別な型に対する最適化が行われている点です。
処理対象は原則として IEnumerable<T> なのですが、
実際の型は配列であったり、リストであったり、LINQ のメソッドで生成された結果であったりなどさまざまです。
「最初の要素を取り出す」という処理の最適な実装方法はコレクションの特性に応じてさまざまです。
TryGetFirst メソッドでは、処理するシーケンスの実際の型に応じて、
最適な処理を選択するような実装になっています。
それでは実際にコードを見てみましょう。
private static TSource? TryGetFirst<TSource>(this IEnumerable<TSource> source, out bool found)
{
if (source == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
}
if (source is IPartition<TSource> partition)
{
return partition.TryGetFirst(out found);
}
if (source is IList<TSource> list)
{
if (list.Count > 0)
{
found = true;
return list[0];
}
}
else
{
using (IEnumerator<TSource> e = source.GetEnumerator())
{
if (e.MoveNext())
{
found = true;
return e.Current;
}
}
}
found = false;
return default;
}
IPartition<T> の場合
まず、最初の部分を見ていきます。
もし source が IPartition<T> 型であれば IPartition<T> に実装された TryGetFirst メソッドを呼びます。
if (source is IPartition<TSource> partition)
{
return partition.TryGetFirst(out found);
}
IPartition<T> というのは、Skip や Take などの、「シーケンス中の連続した一部分を取り出す」という操作をした場合に作られるものです。
インターフェースの定義としては以下のようになっています。
internal interface IPartition<TElement> : IIListProvider<TElement>
{
IPartition<TElement> Skip(int count);
IPartition<TElement> Take(int count);
TElement? TryGetElementAt(int index, out bool found);
TElement? TryGetFirst(out bool found);
TElement? TryGetLast(out bool found);
}
IPartition<T> の TryGetFirst メソッドの実装は状況に応じてさまざまなものが使われますが、
特に配列のようにランダムアクセスをサポートできる型に対して効果を発揮します。
IPartition<T> に関しては、 .NET 6 では多数の実装があるため、別の記事で詳しく扱います。
IList<T> の場合
次に、 IList<T> の場合を見てみます。
if (source is IList<TSource> list)
{
if (list.Count > 0)
{
found = true;
return list[0];
}
}
この場合はまずリストの長さをチェックします。list.Count > 0 が成立するということは、少なくとも「0番目の要素」が存在するということです。
「最初の要素」とはすなわち 0 番目の要素のことですから、0 番目の要素を最初の結果として返します。
一般的に IList<T> のインデクサを使ったアクセスは高速ですので、このような実装になっているのだと考えられます。
ここで、 IReadOnlyList<T> ではなく IList<T> に変換しているのには歴史的な理由があるようです。
.NET 5 でかなり改善されたようですが、共変のインターフェースへのキャストは非常に遅い時期があり、そのコストが許容できなかったようです。
IList<T> は共変でも反変でもない interface ですが、 IReadOnlyList<T> では T は戻り値にのみ使用されるため共変な interface になっているため、 IList<T> が使われています。
共変 (Covariant) と反変 (Contravariant) は圏論由来の概念ですが、コレクションを扱う上では大変重要な概念なので、別の記事で扱います。
一般の場合
最後に、一般の IEnumerable<T> の場合について見てみます。 IEnumerable<T> の場合は要素を順番に列挙してみることしかできませんから、
MoveNext と Current を利用した、ある意味素直な実装になっています。
using (IEnumerator<TSource> e = source.GetEnumerator())
{
if (e.MoveNext())
{
found = true;
return e.Current;
}
}
GetEnumerator() は呼び出しごとに新しく IEnumerator<T> のインスタンスを作って返すため、メモリアロケーションが発生します。
MoveNext() をしてみて Current をとるという処理も、リストの 0 番目の要素をダイレクトに取るよりは若干コストが高いです。
そのため IList<T> や IPartition<T> では専用の実装が使われるようです。
まとめ
今回は First メソッドの実装をざっくり読んでみました。
前回の記事 での自作のメソッドに比べて、
.NET 6 の実装ではさまざまな最適化が施されていることがわかりました。
IPartition<T> の最適化については深追いできていませんので、他の記事で深く取り扱います。
次回はこの最適化がどのぐらい効いているのか、いろいろな型に対してパフォーマンスを計測して調べていきます。
ライセンス
今回紹介したコードはすべて、 MIT ライセンスで公開されている .NET 6 の実装の引用です。