maxfie1d のブログ

マイクロソフト系技術ネタを中心に書きます。

LINQ の実装を覗いてみる

ふと LINQ の拡張メソッドの実装を見てみたくなったので調べてみました。

LINQ のコードの入手

corefx というリポジトリで公開されています。

github.com

一番簡単そうな First() を見てみる。

IEnumerable の最初の要素を返す First() メソッドを見てます。

corefx/First.cs at master · dotnet/corefx · GitHub

        public static TSource First<TSource>(this IEnumerable<TSource> source)
        {
            TSource first = source.TryGetFirst(out bool found);
            if (!found)
            {
                throw Error.NoElements();
            }

            return first;
        }

TryGetFirst()メソッドの返り値を返しているようです。 ということでTryGetFirst()メソッドを見てみます。

        private static TSource TryGetFirst<TSource>(this IEnumerable<TSource> source, out bool found)
        {
            if (source == null)
            {
                throw Error.ArgumentNull(nameof(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(TSource);
        }

ちょっと長くなってきました。まずsourcenullでないかチェックしています。 次にsourceIPartitionなら~と分岐しています。ちょっと待った、IPartitionってなんだ。

IPartition インターフェースとは

ぐぐってみると参考になる記事がヒットしました。

azyobuzin.hatenablog.com

どうやらIPartitionインターフェースはIEnumerableであり、 さらにある程度LINQの処理を最適化できる場合に用いられるインターフェースのようです。

f:id:maxfieldwalker:20180112161220p:plain

話を戻します

というわけで、より高速に処理できるIPartitionならばそれがもつTryGetFirst()メソッドを 使おうというわけです。IPartitionでなければ次はIListなら~ と分岐します。これも高速化のためと思われます。

IPartitionでもIListでもなければ、諦めて最終手段です。コードの最後の部分を再掲します。 sourceGetEnumerator()を呼び出してIEnumeratorを取得し、一度だけMoveNext()を呼び出して、 要素があれば返しなければ失敗となります。

            else
            {
                using (IEnumerator<TSource> e = source.GetEnumerator())
                {
                    if (e.MoveNext())
                    {
                        found = true;
                        return e.Current;
                    }
                }
            }

            found = false;
            return default(TSource);

ほかにも色々

LINQには他にもまだまだメソッドがありますが、長くなりそうなのでこの辺りにしようと思います。 初めて内部実装を見るということをしましたが、結構工夫がなされていてここはこうなっていたんだ~とちょっと感動すらしました。 よい勉強になりました。