LINQソースコードから見る遅延評価のバリエーション #C#

はじめに

.NETの言語を触れていれば必ず通るLINQ，皆様もその恩恵に与ることが多いかと思います。
LINQの特徴は何といっても遅延評価であり，値を取得しようとするまで実際の処理は行われないことにあります。
しかし，偏に遅延評価と言えど，実際にはその評価方式には幾つかの種類があります。
本ドキュメントではそんな遅延評価についてC#の標準ライブラリのソースコードを読みながら，少し掘り下げてみます。

尚，本ドキュメントがカバーする範囲は System.Collection.Generic.IEnumerable<T> をメソッドチェーンで繋げていく部分のみであり，クエリ式（System.Linq.IQueryable<T>）や非同期ストリーム（System.Collections.Generic.IAsyncEnumerable<T>）については触れないことをご留意ください。

本ドキュメントの対象バージョン

項目名	バージョン
.NET	.NET7
C#	11

遅延評価のバリエーション

さて，本題の遅延評価について入りましょう。
MSドキュメントの分類表に目を遣ると，遅延評価に「遅延実行（ストリーミング）」と「遅延実行（非ストリーミング）」の二種類が存在することが見て取れるかと思います。
※MSドキュメントでは「遅延実行」となっていますが，遅延評価と同じ意味です。

「遅延実行（ストリーミング）」は一つの要素を列挙する際，親シーケンスからの要素の取得も一つだけというもので，基本的に要素毎の計算量は同じです。
遅延評価と聞いて最初に思い浮かぶ評価方法になると思います。
Select や Where などが代表的です。
また，Distinct や Union のように列挙した値を列挙終了まで一時的に保存しているものも一部あります。

Selectによるサンプル

ソース

IEnumerable<int> seq = CreateSequence();

Console.WriteLine("列挙開始");

foreach (int current in seq.Select(x => x * 2))
{
    Console.WriteLine(current);
}

Console.WriteLine("列挙終了");

IEnumerable<int> CreateSequence()
{
    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine($"{i}番目の列挙");
        yield return i;
    }
}

出力

列挙開始
0番目の列挙
0
1番目の列挙
2
2番目の列挙
4
3番目の列挙
6
4番目の列挙
8
列挙終了

もう一つの「遅延実行（非ストリーミング）」は一つ目の要素を列挙する前に親シーケンスの全ての要素を処理して列挙すべきソースを作成し，二つ目の要素以降はそのソースの内容を順番に返すものです。
注目すべきは一つ目の要素の列挙時に殆どの処理を行うことで，コルーチンなどの評価タイミングが重要なものや，無限に値を列挙し続けるシーケンスを渡すと思わぬ挙動を引き起こす可能性があります。
TakeLast や OrderBy などが代表的で，ソートや最後の要素の参照など，全ての要素を一旦参照しなければらならない処理でこの評価方法が用いられます。

OrderDescendingによるサンプル

ソース

IEnumerable<int> seq = CreateSequence();

Console.WriteLine("列挙開始");

foreach (int current in seq.OrderDescending())
{
    Console.WriteLine(current);
}

Console.WriteLine("列挙終了");

IEnumerable<int> CreateSequence()
{
    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine($"{i}番目の列挙");
        yield return i;
    }
}

出力

列挙開始
0番目の列挙
1番目の列挙
2番目の列挙
3番目の列挙
4番目の列挙
4
3
2
1
0
列挙終了

また，先ほどの分類表の中にはストリーミングと非ストリーミング両方にチェックがついているものがあります。
これに該当するのは複数のシーケンスを受け取る一部のメソッドで，或るシーケンスはストリーミングで評価され，他のシーケンスは一つ目の要素を列挙する際にまとめて評価されます。
Join や Intercept などが代表的です。

Interceptによるサンプル

ソース

IEnumerable<int> seq1 = CreateSequence1(); // ストリーム
IEnumerable<int> seq2 = CreateSequence2(); // 非ストリーム

Console.WriteLine("列挙開始");

foreach (int current in seq1.Intersect(seq2))
{
    Console.WriteLine(current);
}

Console.WriteLine("列挙終了");

IEnumerable<int> CreateSequence1()
{
    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine($"1-{i}番目の列挙");
        yield return i;
    }
}

IEnumerable<int> CreateSequence2()
{
    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine($"2-{i}番目の列挙");
        yield return i * 2;
    }
}

出力

列挙開始
2-0番目の列挙
2-1番目の列挙
2-2番目の列挙
2-3番目の列挙
2-4番目の列挙
1-0番目の列挙
0
1-1番目の列挙
1-2番目の列挙
2
1-3番目の列挙
1-4番目の列挙
4
列挙終了

LINQソースコードを眺めてみる

ストリーミングによる評価

ここでは先頭から指定した個数の要素を取得する Take(IEnumerable<T>, int) の実装を読んでみます（リンク：Take.cs，Take.SizeOpt.cs）。

// The MIT License (MIT)
// Copyright (c) .NET Foundation and Contributors

public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> source, int count)
{
    if (source == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
    }

    return count <= 0 ?
        Empty<TSource>() :
        TakeIterator<TSource>(source, count);
}

private static IEnumerable<TSource> TakeIterator<TSource>(IEnumerable<TSource> source, int count)
{
    Debug.Assert(count > 0);

    foreach (TSource element in source)
    {
        yield return element;
        if (--count == 0) break;
    }
}

Take<TSource>(IEnumerable<TSource>, int) では引数のチェックと引数に合わせた適切な結果の呼び出しのみを行っており，処理の本体は TakeIterator<TSource>(IEnumerable<TSource>, int) にあります。
TakeIterator<TSource>(IEnumerable<TSource>, int) の中ではシーケンスの列挙を行う度に count を減らしていき，ゼロになったら列挙を終了する処理を記述します。

補足
--count のデクリメントは前置きなので，減算処理が行われた後で 0 との比較が行われています。

非ストリーミングによる評価

要素をキーに基づいてグループ化する GroupBy<TSource, TKey>(IEnumerable<TSource>, Func<TSource, TKey>) について見てみます（リンク：Grouping.cs，Lookup.cs）。
簡単のため，ここでは上記の一つのオーバーロードについてのみ触れます。

// The MIT License (MIT)
// Copyright (c) .NET Foundation and Contributors

public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) =>
    new GroupedEnumerable<TSource, TKey>(source, keySelector, null);

internal sealed partial class GroupedEnumerable<TSource, TKey> : IEnumerable<IGrouping<TKey, TSource>>
{
    private readonly IEnumerable<TSource> _source;
    private readonly Func<TSource, TKey> _keySelector;
    private readonly IEqualityComparer<TKey>? _comparer;

    public GroupedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer)
    {
        if (source is null)
        {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
        }
        if (keySelector is null)
        {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keySelector);
        }

        _source = source;
        _keySelector = keySelector;
        _comparer = comparer;
    }

    public IEnumerator<IGrouping<TKey, TSource>> GetEnumerator() =>
        Lookup<TKey, TSource>.Create(_source, _keySelector, _comparer).GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

// ILookup<TKey, TElement> の実装
public partial class Lookup<TKey, TElement> : ILookup<TKey, TElement>
{
    // 結構長くなるので，大部分を省略

    private Grouping<TKey, TElement>? _lastGrouping;

    public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
    {
        Grouping<TKey, TElement>? g = _lastGrouping;
        if (g != null)
        {
            do
            {
                g = g._next;

                Debug.Assert(g != null);
                yield return g;
            }
            while (g != _lastGrouping);
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

ちょっと複雑なので順を追って見ていきましょう。
先ず，GroupBy<TSource, TKey>(IEnumerable<TSource>, Func<TSource, TKey>) 内ではただ GroupedEnumerable<TSource, TKey> を生成して返すのみです。
GroupedEnumerable<TSource, TKey> のコンストラクタでは単に GroupBy メソッドの引数を受け取ってフィールドにしています。

次に，GroupedEnumerable<TSource, TKey>.GetEnumerator() では Lookup<TKey, TElement> のインスタンスを生成（Lookup<TKey, TElement>.Create メソッド）し，すぐさまその GetEnumerator() を返しています。
この段階で与えたシーケンスの要素が全て読み込まれます。
尚，この過程は ToLookup メソッドと同じことをやっていると考えてしまってOKです。

Lookup<TKey, TElement>.GetEnumerator() では内部に持っている IGrouping<TKey, TElement> のインスタンスを yield return で順番に返しています。
Grouping<TKey, TElement> は IGrouping<TKey, TElement> の実装クラスです。
Lookup<TKey, TElement> 内において Gouping<TKey, TElement> 同士は単連結リストのように繋がっており， _next フィールドで次のインスタンスを参照しています。

ここまでの処理を簡単にまとめると以下のようになります。

専用イテレータのインスタンスを取り敢えず返す
列挙が始まると ILookup<TKey, TElement> に変換，与えられたシーケンスの要素を一旦全て処理
生じた ILookup<TKey, TElement> の内容を一つずつ列挙

ストリーミングと非ストリーミングの混在

二つのシーケンスの積集合を返す Intersect メソッドについて見てみます（リンク：Intersect.cs）。

public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) => Intersect(first, second, null);

public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer)
{
    if (first == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.first);
    }

    if (second == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.second);
    }

    return IntersectIterator(first, second, comparer);
}

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer)
{
    var set = new HashSet<TSource>(second, comparer);

    foreach (TSource element in first)
    {
        if (set.Remove(element))
        {
            yield return element;
        }
    }
}

ここでも実装の実体は IntersectIterator<TSource>(IEnumerable<TSource>, IEnumerable<TSource>, IEqualityComparer<TSource>?) にあります。
このメソッドでは最初に second の要素全てを評価し， HashSet<T> に変換します。
そして first の要素を列挙の度に評価し，second による HashSet<T> から削除できる（=当該セットに含まれる）場合に yield return で返します。

このように，Intersect メソッドでは片方のシーケンス（first）のストリーミングによる評価ともう片方のシーケンスの（second）の非ストリーミングによる評価を組み合わせているわけです。

各遅延評価メソッドの分類表

最後に，MSドキュメントの表の拡張版として遅延評価の分類表を記載します。
+ は全てのシーケンスがストリーミングによる遅延評価を， - は全てのシーケンスが非ストリーミングによる遅延評価を受けることを表します。
また，ストリーミングと非ストリーミングが混在する場合は処理毎に対応する引数名を記載しています。
尚，ToArray メソッドのような即時評価系は省いています。

分類	名前	ストリーミング	非ストリーミング	備考
ソート	Order	-	+
ソート	OrderBy	-	+
ソート	OrderByDescending	-	+
ソート	OrderDescending	-	+
ソート	ThenBy	-	+
ソート	ThenByDescending	-	+
ソート	Reverse	-	+
集合操作	Distinct	+	-	列挙した値を一時的に保存
集合操作	DistinctBy	+	-	列挙した値を一時的に保存
集合操作	Except	`first`	`second`	`second` を `HashSet<T>` に変換し， `first` の要素を返すかどうか検証
集合操作	ExceptBy	`first`	`second`	`second` を `HashSet<T>` に変換し， `first` の要素を返すかどうか検証
集合操作	Intersect	`first`	`second`	`second` を `HashSet<T>` に変換し， `first` の要素を返すかどうか検証
集合操作	IntersectBy	`first`	`second`	`second` を `HashSet<T>` に変換し， `first` の要素を返すかどうか検証
集合操作	Union	+	-	列挙した値を一時的に保存
集合操作	UnionBy	+	-	列挙した値を一時的に保存
絞込	OfType	+	-
絞込	Where	+	-
射影	Select	+	-
射影	SelectMany	+	-
射影	Zip	+	-
分割	Chunk	+	-
分割	Skip	+	-
分割	SkipLast	-	+	他のSkip系と評価方法が異なるので注意
分割	SkipWhile	+	-
分割	Take	+	-
分割	TakeLast	-	+	他のTake系と評価方法が異なるので注意
分割	TakeWhile	+	-
結合	Join	`outer`	`inner`	`inner` を `ILookup<TKey, TElement>` に変換し，`outer` の要素と適宜結合
結合	GroupJoin	`outer`	`inner`	`inner` を `ILookup<TKey, TElement>` に変換し，`outer` の要素と適宜結合
グループ化	GroupBy	-	+	列挙開始時に `ILookup<TKey, TElement>` に変換し，その要素を列挙している
生成	DefaultIfEmpty	+	-
生成	Range	+	-
生成	Repeat	+	-
変換	Cast	+	-
連結	Append	+	-
連結	Concat	+	-
連結	Prepend	+	-

おわりに

遅延評価か即時評価かについては俎上に載せられることが多い反面，遅延評価の種類に関してはあまりそうならない印象があるので取り上げてみました。
非ストリーミングな遅延評価に関しては注意して扱うべき時が稀にあるため，このドキュメントが参考になれば幸いです。

以下戯言

Qiitaを初めて最初に書いたメモリ領域関連の記事が思いの外好評で大変驚いています。
いいねなど一つ二つつけば御の字と思っていましたが，結構需要があるもんですね。
評価してくださった皆様に感謝。

Reference

Microsoft公式
- 実行方法による標準クエリ演算子の分類 (C#)
C#ソースコード