LINQ って速いの?

LINQ って速いの?

LINQ が登場してからもう結構立ちます。使い勝手の良さに感動したですねぇ。当時。

パフォーマンスってどうなんでしょうね? 昔から気になってたんですが、今更ですがベンチマークとってみました。

ことの発端は、Twitter で JavaScript の for of より for の方が数十倍くらい遅いみたいな話をしている人がいて、さすがにそりゃあないだろうと思ってたら、.forEach() とか .map() とかのほうが JIT コンパイラがごにょごにょしてくれるから気にせんでいいよとか突っ込みが入ってて。それもそれでほんとかよ? って思った次第でして。

なんで、それで JavaScript じゃなくて .NET (LINQ) なの? って話ですが、.NET ならちゃんとしたベンチマークの取り方知ってるからでして。そのうち JavaScript でもやってみますけど、ひとまず長年の疑問だった LINQ を確かめてみたわけです。

コレクションの合計を求める

ベンチマーク結果です。

Method	Mean	Error	StdDev
SumFor	731.8 us	9.40 us	8.79 us
SumForeach	659.6 us	9.09 us	8.51 us
SumForeachList	1,121.4 us	13.91 us	12.33 us
SumForeachEnumerable	5,010.3 us	35.40 us	33.11 us
SumAggregate	6,145.8 us	91.86 us	81.44 us
SumLinq	4,756.9 us	90.66 us	97.01 us

for と foreach

配列 (int[]) の合計を求めるのを for と foreach で比較してみます。

// SumFor
// 731.8 us

var total = 0;
for (var i = 0; i < Array.Length; i++) total += Array[i];

// SumForeach
// 659.6 us

var total = 0;
foreach (var value in Array) total += value;

foreach の方が一割くらい速いです。

BenchmarkDotNet を使ったベンチマークでして。Mean は平均らしいので、誤差の範疇というわけではないようです。

foreach は配列の場合、コンパイラーが配列専用のコードを吐き出すのでその分だけ速いんじゃないかな? って思います。(ちゃんと調べてるわけじゃないので間違ってるかも)

配列以外の foreach

List<int> 型のリストの foreach です。1,121.4 us と、配列の 659.6 us と比べると倍近くかかってます。

// SumForeachList
// 1,121.4 us

var total = 0;
foreach (var value in List) total += value;

IEnumerable<int> 型の foreach になると、5,010.3 us と配列に比べると 8 倍くらい時間がかかってます。

// SumForeachEnumerable
// 5,010.3 us

var total = 0;
foreach (var value in (IEnumerable<int>) Array) total += value;

List<int> と IEnumerable<int> で結構差が出ていますが、前者はインスタンスメソッドを直接呼び出していて、後者はインターフェイス経由になるので遅くなってるのだと思われます。`

インターフェイスでは実際に呼び出すメソッドの実装が動的に決まるので、インライン化などの最適化があんまり効かないんですね。

LINQ の Sum()

LINQ の拡張メソッドの Sum() はインターフェイス経由の foreach よりちょっとだけ速いです。

// SumLinq
// 4,756.9 us

Array.Sum();

Sum() のソースコード読んでみたんですが、インターフェイス経由の foreach よりちょっと速い理由はわかりませんでした。

LINQ の Aggregate()

LINQ の拡張メソッドの Aggregate() は 6,145.8 us と予想通りめちゃくちゃ遅いです。配列の 10 倍くらいです。

// SumAggregate
// 6,145.8 us

Array.Aggregate((previous, current) => previous + current);

おそらくなんですが、ラムダ式の (previous, current) => previous + current の部分がインライン化されていないんだと思います。

配列の要素を倍にした配列を作る

Method	Mean	Error	StdDev
DoubleFor	1.942 us	0.0378 us	0.0477 us
DoubleList	5.287 us	0.0957 us	0.1139 us
DoubleLinq	2.735 us	0.0481 us	0.0915 us

for を使う

foreach では書きづらいので for で。1.942 us かかってます。これが基準になります。

// DoubleFor
// 1.942 us

var result = new int[Array.Length];
for (var i = 0; i < Array.Length; i++) result[i] = Array[i] * 2;

絶対にやってはいけない

次の例は foreach と List<int> を使って一つ一つ追加していく方法です。5.287 us かかりました。2.5 倍くらい遅いですね。

// DoubleList
// 5.287 us

var result = new List<int>();
foreach (var value in Array) result.Add(value * 2);
result.ToArray();

最後の ToArray() を外すと 4.332 usでした。それでも倍くらい遅いです。

まあ、これは絶対にやってはいけないとされる書き方でして。

List<T> の内部は配列です。配列は固定長なので、Add() を何度も呼び出すとはみ出します。はみ出さないように新しい少し長い配列を用意してそこに値をコピーするという実装です。使わなくなった古い配列はガベージコレクションで回収されるのですが、こういうコードがあちこちにあると、ガベージコレクションの負荷も上がって、異常に遅くなるとかあるかもしれません。

new List<int>(Array.Length) として最初から必要な量の配列を確保すると 4.264 us でした。ToArray() の分を差し引けば、配列 + for のときの倍まではいかないくらいです。

LINQ の Select() を使う

LINQ の Select() を使った書き方です。同一条件にするために、ToArray() も呼び出しています。2.735 us かかりました。for の五割り増しくらいでしょうか?

// DoubleLinq
// 2.735 us

Array.Select(x => x * 2).ToArray();

これだけ速いのは予想外です。実装まで追っかけていませんが、おそらく Select() はソースが配列などのような長さを持つコレクションなら、次の処理にも長さを渡しているんだと思います。

このあたり、LINQ は最速ではないかもだけど、遅くならない実装を持ってたりするのがすごいですねぇ。

LINQ 速い?

• 配列の foreach 速いですな!
• LINQ は速くはないけど遅くもない
• LINQ は関数のインライン化はやってなさそう

まあ、今回は圧倒的に高速な単純計算をベンチマークに使っているので、反復処理の違いが如実に出ましたけど、実際のコードではここまで差が出ることは少ないと思います。

PLINQ などもありますし、単純な foreach より LINQ の方が速いことも多いと思います。

インターフェイスを使う使わないでも劇的に変わったりするので、このベンチマークだけを見て判断するんではなく、実際のコードのベンチマークを取って速い遅いは議論すべきだと思います。

ファーストクラスコレクション

コンピューターの性能を極限まで生かす必要があるなら別ですが、それなりにで良ければコレクションの操作はファーストクラスコレクションを使うのがいいと考えています。

こういうのです。

public sealed class Scores
{
    private readonly ImmutableArray<int> _values;

    public Scores(IEnumerable<int> values)
    {
        _values = values.ToImmutableArray();
    }

    public int Sum()
    {
        return _values.Sum();
    }
}

ファーストクラスコレクションを使わず、直に配列やコレクションクラスを使うと、パフォーマンスの問題が起きた時のチューニングが広範囲に及ぶんですね。

ファーストクラスコレクションならば、これを利用しているコードの実装を変えずに、ファーストクラスコレクションの内部の実装を変えるだけでパフォーマンスチューニングができるわけです。

例のような単純な実装でまずはいいわけです。

要素の数がすごく多く、パフォーマンスの問題があるとわかってから次のように書き換えればいいわけです。

public sealed class Scores
{
    private readonly int[] _values;
    private readonly Lazy<int> _sum;

    public Scores(IEnumerable<int> values)
    {
        _values = values.ToArray();
        _sum = new Lazy<int>(PerformSum);
    }

    public int Sum()
    {
        return _sum.Value;
    }

    private int PerformSum()
    {
        var sum = 0;
        foreach (var value in _values) sum += value;
        return sum;
    }
}