wiprog

C#, .NET, Scala ... について勉強したことのメモ

今からできる、速くシンプルに LINQ を書くためのコツ 3 個

たびたび 「LINQ が遅い」 と言われているのを見かけるので、どうやったら速く書けるのか、どう書くと遅くなるのかについてまとめてみます。
LINQ は非常に強力で、ぼくが出会った「LINQ 遅い」のほとんどは、 実装の仕方がまずいものばかりです。
LINQ はいくつかポイントを意識するだけでかなり安全に速く書けるようになります。
いろいろとポイントはありますが、 3 つだけに絞って書いてみました。

私自身 C# 書き始めてようやく 2 年たったぐらいなので、間違っているところはバシバシご指摘いただけると嬉しいです。

こちらの記事も参考になるので、合わせてご覧ください。

blog.okazuki.jp

「LINQ 遅い」の 3 パターン

まあ LINQ は速くないこともたまにあるのですが、大抵の場合は十分なパフォーマンスを提供してくれます。
「LINQ が遅い」 と言う時はだいたい以下のどれかかなと思います。

  1. よくわからないけどイメージで「遅そう」と言っている (要するに使いたくない、覚えたくない)
  2. LINQ のしくみがよくわからず、誤った使い方、明らかに遅い書き方をしている (例: なんとなく Count(), ToArray() などしてしまう)
  3. LINQ の内部実装をよく知っているプロフェッショナルが LINQ が適していない場合に「遅い」と言う

1 の場合はどうにもできないです。 3 の場合は必要に応じて LINQ 以外の方法を取ることもできますし、 LINQ を使うと判断した場合は最も適切なメソッドを選んで使用できるので遅くなりません。プログラマとしてはここを目指したい。
問題は 2 の場合で、「なんとなく動くものは書けるけど遅い、どこが遅いのかよくわからない」というのが多いです。
今回は最も多いと思われる 2 のパターンをターゲットに書いていきます。

1. 不用意に要素数を取得しない (Count メソッド)

一番良く見かけるのがこれです。簡単に書けてしまいますが非常に危険です。

IEnumerable<Hoge> source = // ...

if (source.Count() > 0)
{
    // 要素があるときの処理
}

IEnumerable<T> はカウントを持ちません。いくつ要素があるのかも全部列挙してみないとわかりません。 もしかしたら非常に長かったり、列挙におおきなコストがかかったり、無限につづくシーケンスでそもそもカウントできないかもしれません。
Count メソッドは基本的には 100 万個要素があったら 100 万個全部を 1 個ずつ列挙して数えていくため非常に遅く、ほとんどの場合に意図していない列挙を発生させます。
もちろん Count の前に Select や Where をかけていて、列挙の際になんらかの計算が発生するような場合にはその計算のコストもかかります。 実体が Count プロパティをもつコレクションである場合には Count プロパティの値を取得するような最適化は入っているものの、本当に「何個あるか知りたい時」以外使うべきでないです。

source.Count() > 0 と書くのであれば、代わりに source.Any() と書きましょう。

「ある条件を満たす要素が n 個以上あるかどうかを判定したいとき」には下記のように Skip や Take を使用することで、一部だけの列挙におさえることができます。

var filtered = source.Where(predicateFunc);

// 列挙した要素を一切使わず、ただ n 個以上あることをたしかめたいとき
// 列挙したものを保存する必要がないのであれば、この方法で無駄な配列確保を避けられる
if (filtered.Skip(n - 1).Any())
{
    // n 個あった時の処理
}

// 列挙した要素を n 個使用するとき
// 複数回同じものに対しての列挙を避けるには、ToArray() が有効。
// ただし、 n が大きくなった場合、それだけ大きい配列が確保されるので注意。これは ToList() でも同様
var part = filtered.Take(n).ToArray();

if (part.Length == n)
{
    foreach (var item in part)
    {
        // なにか処理
    }
}

2. なんとなく配列やリストに突っ込まない。ライブラリを作るときはなるべく IEnumerable<T> で受ける。

ToArray() や ToList() は非常に便利なメソッドですが、ほとんどの場合 LINQ の途中で呼ぶ必要はありません。 たとえば、下記のような ToArray は意味がないばかりか、無駄な配列のためのメモリを確保してパフォーマンスを著しく低下させます。

IEnumerable<Hoge> source = // ...

var array = source.ToArray() // むだな配列生成
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct()
    .ToArray(); // むだな配列生成

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

下記のように書いてもまったく動作上問題がなく、パフォーマンスがよくなります。

IEnumerable<Hoge> source = // ...

var array = source
    .Select(x => ごにょごにょ)
    .Where(x => ごにょごにょ)
    .Distinct();

// foreach するだけならむだな array はいらない
foreach (var x in array)
{
    // なにかする
}

また、配列である必要がないのに配列で引数を要求するメソッドを書くのはやめましょう。 IEnumerable<T> で受けましょう。 本当は 1 個ずつ処理するだけのメソッドなのに、渡す側で ToArray() して渡す必要があるのは無駄です。

3. 巨大なファイルを 1 行ずつ処理するときも、リストはいらない。

たとえば、こんなコードを書いたことはありませんか？これはほんとうに無駄なのでやめましょう。

// 1 行ずつ処理したいけど、 LINQ つかうから IEnumerable<T> がほしい。 List<T> に Add していこう

List<Hoge> sourceList = new List<Hoge>();

using (var reader = new StreamReader(stream))
{
    string line;
    while ((line = reader.ReadLine()) != null
    {
        sourceList.Add(MapToHoge(line));
    }
}

sourceList.Select(xxx).Where(xxx). // ...

こんなふうに書けば、一気に全部読んでしまう必要はまったくありません。

IEnumerable<Hoge> Read()
{
    using (var reader = new StreamReader(stream))
    {
        string line;
        while ((line = reader.ReadLine()) != null
        {
            yield return MapToHoge(line);
        }
    }
}

Read().Select(xxx).Where(xxx) // ...

あるいは、ファイルから読むことがわかっているならこれでも良いです。

File.ReadLines("filepath")
    .Select(xxx)
    .Where(xxx)
    . // ...

File.ReadAllLines メソッドもありますが、こちらはすべてを読んで配列に入れてから返してくるので気をつけましょう。巨大なファイルを読む場合に大量のメモリが必要になります。

まとめ

たくさん書きましたが、要するにおなじシーケンスに対しての複数回の列挙や、必要のないものの列挙、巨大なメモリ確保にもっと慎重になりましょうということです。
LINQ は遅延評価が基本ですが、誤った使い方をすればそのメリットを活かせないばかりか、非常に遅いコードが簡単に出来上がってしまいます。
遅いのは LINQ のバグでも、 .NET Core 開発チームの怠慢でも、マシンのスペックが足りないからでもなく、ただ遅くなるように書いたからです。そうでないこともありますが、だいたいそうです。

自分で書いたコードが遅かったり、すっきり書けなかったりして困ったときに、Qiita や twitter に投稿するといろんな人のアドバイスが受けられて楽しいです。
読む人にとってはその投稿についたコメントや、反応の記事のほうが役にたつことがたくさんありますが、最初の投稿がなければそれらの記事も生まれません。

LINQ の内部の実装を読むことは非常に勉強になります。
GitHub で .NET Core の完全な実装を読むことができます。
難しく見えるかもしれませんが、単純なもの、きになるものから読んでいくといいと思います。 また、簡単そうなメソッドを自分で書いてみるのも理解するには効果がありました。
LINQ を書く際に気をつけることはこれがすべてではありませんが、ドキュメントやコードをきちんと読んだり、信頼できる先輩にアドバイスをもらったりしながらだんだんと身についていくものだと思います。

github.com

あと、 ReSharper などのツールを入れると multiple enumeration の注意を出してくれたりもします。

www.jetbrains.com

（ReSharper は他にもいろいろなことを教えてくれる素晴らしい先生になるのでめちゃくちゃおすすめです）

(おまけ) 記事を書いたきっかけ

もともと微妙なコードをちょくちょく見かけていて、 LINQ ってそんなに難しいのかなーと思っていたのですが、 twitter で
C#でLinqを使うよりPythonの方が2倍速かったのでベンチマークをしてみた - Qiita
という記事が回ってきました。

公開から短時間でいいねが複数ついていたことから、ほんとうは速くシンプルに書けるにもかかわらず、 LINQ が遅いと判断してしまう人は多いのではないかと思い、 急いで記事を書いている次第です (そもそもこのブログ自体そんなに見られてないのでどの程度効果があるかは疑問ですが)。

この記事の具体的な内容についてはもう十分他の方が指摘などされていると思いますので、ここでは細かく言及しません。 ただ、もし初心者の方が読まれる場合には下記の点だけは頭においてほしいです。

  1. (意図的にそうしているとは思いませんが、結果として) 検証用のコードが非常に遅くなるように書かれています。 検証用のコードを改善することでだいぶ速い結果になる、という記事がすでにあります。GroupBy が遅いように書かれていますが、それよりも 無駄な ToList 何度も呼んでいるめにループの回数が増えてしまっていることのほうがはるかに大きな問題です。C# の Linq が python の２倍遅い、は嘘 - Qiita
  2. Span<T> に関しては用途が違うように思います。 Qiita の記事とは全く無関係ですが、 日本語で読める Span<T> の記事としては Span<T>構造体 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C がとても参考になります。
  3. 実際には、LINQ に限らず .NET のパフォーマンスの改善や新機能の開発に多くの優秀なエンジニアが取り組んでいます。また、明らかに遅かったり問題があり、改善方法があることが本当にわかっているなら、 issue をあげたり、プルリクエストを送ってみたりする手段は誰にでも開かれています。 GitHub - dotnet/corefx: This repo contains the .NET Core foundational libraries, called CoreFX. It includes classes for collections, file systems, console, XML, async and many others. We welcome contributions.

BenchmarkDotnet を使って LINQ の部分のベンチマークをとってみたところ、標準の LINQ メソッドだけで 3 倍以上高速になりました。

SlowLinq が Qiita の元記事、 NormalLinq がそれを書き直したもの、 UseGroupSum が GroupBy を使わないものです。

Method Mean Error Gen 0 Gen 1 Gen 2 Allocated
SlowLinq 321.59 ms NA 12400.0000 6200.0000 800.0000 78916.81 KB
NormalLinq 85.77 ms NA 1400.0000 600.0000 - 8415.32 KB
UseGroupSum 62.12 ms NA - - - 147.43 KB