LINQ のコツ 2021 年版 (1)

まえがき

今からできる、速くシンプルに LINQ を書くためのコツ 3 個 という記事を書いてから 3 年半が経ちました. LINQ で思ったようにパフォーマンスが出ないという悩みは多くの人に共通しているようで,今でもこの記事は毎月コンスタントに 300 弱の PV 数があります.

この記事はとくに書いてからメンテナンスなどしていなかったのですが,3 年前の未熟な文章で誤解を与えかねない部分があるのと, IAsyncEnumerable が標準入りしたなどの背景もあり,今回思い切って Ver.2 として内容を刷新し,『LINQ のコツ 2021 年版』を書くこととしました.

今回の記事はより基礎的なところから最新の応用例まで,検証を含めてまとめていくスタイルになっているとおもいます. また,何事も理解するにはたくさんの具体例をこなすのが近道なので,具体例も豊富に用意しました. そのため記事としてはかなりボリュームが出てしまいますので,複数の記事に分割しています. 必要なところを抜き出して使うなどしていただければと思います(Zenn で本のような形式にすることも検討しています).

また,具体例を理解するには実際に手を動かしてみることが必要です. 実際に例を動かしてみることで理解も早まるでしょう.この記事の具体例は LINQPad 6 / .NET 5 を前提に書かれていますので,手元に LINQPad を用意して読むことをおすすめします.

ご指摘やご質問に関しては twitter で @wipianoooo まで DM をいただくか, 2120082 [at] ed.tus.ac.jp までメールをいただければ,可能な範囲で対応いたします.

さて,この記事は 1 本目ということで,LINQ の遅延評価の特性についてです. 次回以降の記事は

  • materialization
  • LINQ を pure にしよう
  • SelectMany の活用
  • IAsyncEnumerableSystem.Linq.Async
  • Parallel.ForEachAsync
  • Channel<T> と非同期 LINQ
  • .NET 6 時代の最新の LINQ メソッド

を予定しています.

1. LINQ の遅延評価

LINQ を書く上でぜひとも知っておきたい概念が「遅延評価」です. LINQ の操作(Select, Where など.以後 operator といいます)には大きく分けて以下の 2 種類があります.

  • 必ず遅延評価になるもの
  • その場でいくつか,あるいはすべての要素の評価が発生する可能性のあるもの

まずこの 2 つの違いを理解し,特性に応じて使い分けることが LINQ のコツのひとつです. 昔の記事 では主にこの遅延評価を活かすという観点で LINQ のコツを書きました.

今回の記事ではおもにこの「遅延評価」戦略の特性について見ていきます. 遅延評価が適さない場合の materialize 手法については次回の記事で扱う予定です.

1.1. LINQ の基本は遅延評価である

LINQ の基本, IEnumerable<T> インターフェースの基本は遅延評価です. ここでの遅延評価とは,ほんとうに必要になるまでそれぞれの要素を評価しない,必要最低限の計算しかしないということです.

1.1.1. 例: Select は遅延評価

簡単な Select の例を考えましょう.次のプログラムの出力はどのようになるでしょうか?

void Main()
{
    int[] numbers = new int[] {1, 2, 3};
    Console.WriteLine("A. 配列の初期化をしました");

    // int の配列の各要素を string に変換する
    IEnumerable<string> stringNumbers = numbers.Select(x =>
    {
        Console.WriteLine($"Select: {x} を string に変換します");
        return x.ToString();
    });
    Console.WriteLine("B. Select メソッドを呼び出しました");

    foreach (string s in stringNumbers) Console.WriteLine($"foreach: {s}");
}

実際に実行すると,次の出力が得られます.

A. 配列の初期化をしました
B. Select メソッドを呼び出しました
Select: 1string に変換します
foreach: 1
Select: 2string に変換します
foreach: 2
Select: 3string に変換します
foreach: 3

この出力から, Select メソッドの呼び出し時点では stringNumbers の要素の評価は一切発生せず, 実際にそれぞれの要素が必要になったタイミングで必要な要素のみが評価されることがわかります.

これが,「LINQ の基本は遅延評価である」ということです. 同様に,他の WhereAppend などの operator も遅延評価です.

注: 詳しくは後述しますが,この例のように LINQ を使って副作用を発生させるのは悪いパターンであると考えるべきです. Select には任意の操作を書けますが,foreach の代わりに Select を使うのはほぼ 100% の確率で誤りです.

1.1.2. 例: multiple enumeration

前の例で,LINQ の operator によって作られた IEnumerable<T> の要素は必要になるまで評価されないことを確認しました. では,同じ要素が複数回評価された場合,要素の評価も 2 回発生するのでしょうか?それとも要素の評価は 1 回だけでしょうか?

前の例の foreach の行を複製して,次のようにします.

void Main()
{
    int[] numbers = new int[] {1, 2, 3};
    Console.WriteLine("A. 配列の初期化をしました");

    // int の配列の各要素を string に変換する
    IEnumerable<string> stringNumbers = numbers.Select(x =>
    {
        Console.WriteLine($"Select: {x} を string に変換します");
        return x.ToString();
    });
    Console.WriteLine("B. Select メソッドを呼び出しました");

    foreach (string s in stringNumbers) Console.WriteLine($"foreach1: {s}");
    foreach (string s in stringNumbers) Console.WriteLine($"foreach2: {s}");
}

すると,出力は下記のようになります.

A. 配列の初期化をしました
B. Select メソッドを呼び出しました
Select: 1string に変換します
foreach1: 1
Select: 2string に変換します
foreach1: 2
Select: 3string に変換します
foreach1: 3
Select: 1string に変換します
foreach2: 1
Select: 2string に変換します
foreach2: 2
Select: 3string に変換します
foreach2: 3

このように, stringNumbers の要素は必要になるたびに,何度でも評価されます. 一般に遅延評価といえば一度計算したものを再評価しないようなキャッシュ機構を備えていることもありますが, LINQ の operator は基本的にそのような機構を備えていません.

1.2. JavaScript の map/filter と比較した遅延評価の特性

LINQ の SelectWhere などの operator は JavaScript 等における mapfilter と対応します. ただし,先程の例で見たように両者の間には評価のタイミングという観点で決定的な違いがあります. SelectWhere は要素を必要になったときに計算するのに対し,配列に対する JavaScript の mapfilter は呼び出し時点ですべての要素を評価して新しい配列を返します.

この 2 つの方式の間にどのような特性の違いがあるのか見てみましょう. 以後簡単のために, LINQ の方式を「遅延評価方式」, JavaScript の方式を「materialize 方式」と呼ぶことにします.

注: 実際には,以下で挙げるようなそれぞれの方式が苦手とするケースであっても,パフォーマンスの低下が最小限となるようにライブラリの内部でさまざまな工夫が施されていることが多いです.以下ではあくまで基本的な考え方を知るための実験的な例を扱います.

1.2.1. 準備

それぞれの方式を同じランタイムで単純に比較するため,以下では LINQ の標準メソッドではなくもっと単純な Select/Where の実験用の代替を利用します.どちらか一方に最適化が施された標準ライブラリの実装を使用してしまうと,それぞれの特性の違いが見えにくくなるため単純化した実装を使用します.

以下の実験では,遅延評価方式の操作として下記のような単純な SelectLazyWhereLazy を考えます. これは LINQ の SelectWhere の実装を単純化したものと考えてください.

public static class SimpleLazyEvalLinq
{
    public static IEnumerable<TResult> SelectLazy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> resultSelector)
    {
        foreach (var item in source) yield return resultSelector(item);
    }

    public static IEnumerable<T> WhereLazy<T>(this IEnumerable<T> source, Func<T, bool> predicate)
    {
        foreach (var item in source) if (predicate(item)) yield return item;
    }
}

つぎに materialize 方式ですが,配列に対して配列を返す操作ということで下記のような SelectToArray, WhereToArray を考えます. これは JavaScript 等の言語における mapfilter を単純化したものと考えてください.

public static class LinqToArray
{
    public static TResult[] SelectToArray<TSource, TResult>(this TSource[] source, Func<TSource, TResult> resultSelector)
    {
        var results = new TResult[source.Length];
        for (var i = 0; i < source.Length; i++) results[i] = resultSelector(source[i]);
        return results;
    }

    public static T[] WhereToArray<T>(this T[] source, Func<T, bool> predicate)
    {
        var results = new T[source.Length];
        var i = 0;
        for (var j = 0; j < source.Length; j++) if (predicate(source[j])) results[i++] = source[j];

        Array.Resize<T>(ref results, i);
        return results;
    }
}

1.2.2. 計算量の観点

計算の量をみたときには, materialize 方式のほうが有利に見えるかもしれませんが,そうとも言い切れません.

「LINQ の基本は遅延評価である」の 2 つめの例で見たように,遅延評価方式では要素を複数回使う場合にその分だけ計算が発生します. 一方 materialize 方式のほうは最初にすべての要素を評価済みなので,何度要素を使っても計算は 1 度だけです. これは遅延評価方式の影の部分ともいえるところで,何度も要素を使う場合には materialize 方式のほうが有利になることがあります. そのため,LINQ においても materialize を活用することが重要な場面もあり,そのことは後述します.

ただしこれには例外があって,たとえば巨大なシーケンスに対して Select/map をかけておいて,実際に使われるのは最初の 10 個の要素だけ,というような場合には,遅延評価方式では計算は最初の 10 個の要素に対してのみ行われますが, materialize 方式では使われるかどうかにかかわらず,すべての要素を評価する必要があります.このような場合では,遅延評価方式が有利です.

1.2.3. メモリ使用量の観点

メモリの使用量をみたときは,遅延評価方式が有利なことが多いです.遅延評価方式では計算結果を保持しておく必要がないため,メモリはあまり.一方で materialize 方式では基本的には計算結果をすべて新しい配列に保持しておくため,とくに巨大なシーケンスに対してはメモリ使用量の観点から不利といえます.

1.2.4. BenchmarkDotNet による性能評価

上記で,巨大なシーケンスにおいて LINQ の基本戦略である遅延評価が有利であると述べました. そこで,実際にどのくらいの差があるのかベンチマークをとってみます.

「準備」のところで提示した SelectLazy, WhereLazy, SelectToArray, WhereToArray メソッドを使って,次のようなベンチマークプログラムを実行してみます. 試験用のロジックとしては, 10 万件のデータから, Where による絞り込みと Select による射影を 1 回ずつ行い,その結果の最初の 10 件を取り出すというものです. ベンチマーク用のプログラム全体は GitHub に置いてあります.

public class Program
{
    static void Main(string[] args)
    {
        var config = new ManualConfig()
            .AddJob(Job.ShortRun)
            .AddExporter(MarkdownExporter.GitHub)
            .AddDiagnoser(MemoryDiagnoser.Default)
            .AddDiagnoser(ThreadingDiagnoser.Default)
            .AddLogger(ConsoleLogger.Default)
            .AddColumnProvider(DefaultColumnProviders.Instance);

        BenchmarkRunner.Run<Benchmark1>(config);
    }
}

// 大きいデータに対して LINQ クエリを実行し,最初の 10 件だけ使う場合の Benchmark
public class Benchmark1
{
    private TestData[] _source;

    private readonly Consumer _consumer = new();

    [GlobalSetup]
    public void Setup()
    {
        // 10万件のテストデータを用意
        _source = GenerateTestData().Take(100000).ToArray();
    }

    [Benchmark]
    public void StandardLinqSelectWhere()
    {
        var top10Ids = new List<int>();

        var linqResults = _source
            .Where(x => x.Name == "taro")
            .Select(x => x.Id);

        int count = 0;
        foreach (var id in linqResults)
        {
            top10Ids.Add(id);
            if (++count >= 10) break;
        }

        top10Ids.Consume(_consumer);
    }

    [Benchmark(Baseline = true)]
    public void LazySelectWhere()
    {
        var top10Ids = new List<int>();

        var linqResults = _source
            .WhereLazy(x => x.Name == "taro")
            .SelectLazy(x => x.Id);

        int count = 0;
        foreach (var id in linqResults)
        {
            top10Ids.Add(id);
            if (++count >= 10) break;
        }

        top10Ids.Consume(_consumer);
    }

    [Benchmark]
    public void MaterializedSelectWhere()
    {
        var top10Ids = new List<int>();

        var linqResults = _source
            .WhereToArray(x => x.Name == "taro")
            .SelectToArray(x => x.Id);

        int count = 0;
        foreach (var id in linqResults)
        {
            top10Ids.Add(id);
            if (++count >= 10) break;
        }

        top10Ids.Consume(_consumer);
    }

    private static IEnumerable<TestData> GenerateTestData()
    {
        Random random = new Random();
        var names = new [] {"foo", "bar", "hanako", "taro", "jiro", "kyoko"};
        int id = 0;

        while (true)
            yield return new TestData(++id, names[random.Next(0, names.Length - 1)]);
    }

    private record TestData(int Id, string Name);
}

ベンチマーク用のツールとしては BenchmarkDotNet を使用しています. このベンチマークを実行した結果は次のとおりです.

|                  Method |           Mean |         Error |       StdDev |    Ratio | RatioSD |    Gen 0 |    Gen 1 |    Gen 2 |   Allocated |
|------------------------ |---------------:|--------------:|-------------:|---------:|--------:|---------:|---------:|---------:|------------:|
| StandardLinqSelectWhere |       641.3 ns |     139.47 ns |      7.64 ns |     0.87 |    0.01 |   0.1717 |        - |        - |       360 B |
|         LazySelectWhere |       734.9 ns |      55.19 ns |      3.03 ns |     1.00 |    0.00 |   0.2060 |        - |        - |       432 B |
| MaterializedSelectWhere | 1,203,037.1 ns | 996,333.01 ns | 54,612.37 ns | 1,636.92 |   70.13 | 197.2656 | 162.1094 | 160.1563 | 1,038,595 B |

平均の実行時間 (Mean) を見ると,Lazy(遅延評価版)が 734 ns に対して, materialized 版は 120 万 ns と,実行時間に 1600 倍以上の差があります.また,メモリ使用量 (Allocated) を見ても, Lazy 版のほうがかなり少なく済んでいることがわかります.

では,すべてのデータを使うときはどうでしょうか? さきほどのベンチマークプログラムを次のように変えてみます. 各メソッドの最後に呼び出している Consume は BenchmarkDotNet が提供しているメソッドで,ベンチマークの最後に IEnumerable<T> の各要素を評価するために使います.

// 大きいデータに対して LINQ クエリを実行し,すべてのデータを使う場合の Benchmark
public class Benchmark2
{
    private TestData[] _source;

    private readonly Consumer _consumer = new();

    [GlobalSetup]
    public void Setup()
    {
        // 10万件のテストデータを用意
        _source = GenerateTestData().Take(100000).ToArray();
    }

    [Benchmark]
    public void StandardLinqSelectWhere()
    {
        var linqResults = _source
            .WhereLazy(x => x.Name == "taro")
            .SelectLazy(x => x.Id);

        linqResults.Consume(_consumer);
    }

    [Benchmark(Baseline = true)]
    public void LazySelectWhere()
    {
        var linqResults = _source
            .WhereLazy(x => x.Name == "taro")
            .SelectLazy(x => x.Id);

        linqResults.Consume(_consumer);
    }

    [Benchmark]
    public void MaterializedSelectWhere()
    {
        var linqResults = _source
            .WhereToArray(x => x.Name == "taro")
            .SelectToArray(x => x.Id);

        linqResults.Consume(_consumer);
    }

    private static IEnumerable<TestData> GenerateTestData()
    {
        Random random = new Random();
        var names = new[] { "foo", "bar", "hanako", "taro", "jiro", "kyoko" };
        int id = 0;

        while (true)
            yield return new TestData(++id, names[random.Next(0, names.Length - 1)]);
    }

    private record TestData(int Id, string Name);
}

このベンチマークでは下記のような結果が得られます.

|                  Method |     Mean |     Error |    StdDev | Ratio |    Gen 0 |    Gen 1 |    Gen 2 |   Allocated |
|------------------------ |---------:|----------:|----------:|------:|---------:|---------:|---------:|------------:|
| StandardLinqSelectWhere | 1.550 ms | 0.0755 ms | 0.0041 ms |  1.00 |        - |        - |        - |       176 B |
|         LazySelectWhere | 1.546 ms | 0.0626 ms | 0.0034 ms |  1.00 |        - |        - |        - |       176 B |
| MaterializedSelectWhere | 1.164 ms | 0.1089 ms | 0.0060 ms |  0.75 | 191.4063 | 160.1563 | 154.2969 | 1,040,734 B |

計算結果全体を使うということで, materialize 版のほうが計算時間的には有意に速い結果となりました.これは最終的な結果が実体のある配列であるところが大きいと思います. それに対して,遅延評価版は計算時間の面では少し及ばないものの,メモリの使用量は格段に少なくなっています.

1.2.5. 要素数の問題

ここまで計算量とメモリ使用量を比較し, LINQ の遅延評価方式のパフォーマンス上のメリットについて見てきました. しかし,遅延評価方式にはひとつ重要な欠点があります.それが「要素数がわからない」という問題です.

materialize 方式の場合,配列に対して mapfilter を呼んでも返ってくるものはやはりただの配列ですから,当然配列の長さ(要素数)を取得できます.配列が空かどうかの判定も容易です.

一方遅延評価方式の場合は,全部の要素をいったん評価してみないと要素数がわからない場合があります.とくに, SelectManyWhere など,呼ぶ前と呼んだあとで要素数が変化するような操作を行った場合には,基本的には全体を評価してみないと要素数がわかりません. LINQ には要素数を評価する Count という操作がありますが,これは基本的にはすべての要素を評価して数え上げる操作で,配列の要素を取得するようにカジュアルに使うと著しいパフォーマンスの低下を招きます. 同様に, AnyAll などの呼び出しも,意図せず要素の評価を発生させる可能性があります.

1.3. LINQ の遅延評価についてのまとめ

まとめると,LINQ の遅延評価の特性としては下記のようになります.

  • 巨大なシーケンスの扱いにおいて,計算量・メモリの観点からたいへん有利である
  • 計算結果を保持しないため,複数回の評価が行われる場合には計算量の観点から不利である
  • 要素の数を取得したり,シーケンスが空かどうか判定するような行為は苦手とする

遅延評価という戦略は基本的にはたいへん有利であるものの,その仕組みから無視できない欠点も存在します. そのため,基本的には遅延評価を最大限利用しつつ,必要に応じて実体のある配列などに変換する操作(materialization)を組み合わせていくことが大切です.

次回の記事 では,この materialization について,具体的な方法と注意点を扱います.