More than 5 years have passed since last update.

WhereとCountのパフォーマンスについて本気出して調べてみた

Last updated at 2019-05-07Posted at 2019-01-21

はじめに

前回はforeachについて色々書いてみました。

そろそろネタが切れそうですが、今回はLINQについてです。

特にWhereの仕組みとパフォーマンス関連の話が中心です。というかそれでほぼ全てです。

過去最高レベルでマニアックな話になってしまいました。~~かなりの変態向けの記事です。~~

マニアック過ぎて文献とか全然見つからなかったので、間違ってる可能性大です。

ガンガン指摘してください。

たまには結論から述べるスタイル

Count(hoge)よりもWhere(hoge).Count()のほうがパフォーマンスに優れている(事がある)。
First,Last,Single,Anyも同様の事が言える(有効な局面は少ない)。
index付きのWhereは、通常のWhereよりも遅い(普通に考えたら当たり前ではある)。
不要なWhereはパフォーマンスに大きな影響を及ぼす(これも当たり前ではある)。

今回色々調べて分かった事は以上になります。

パフォーマンスの根拠は？

0から99_999_999までの整数から、4の倍数の個数を求めます。

public class LinqTest
{
    public IEnumerable<int> a;
    public List<int> b;
    public int[] c;
    public IEnumerable<int> d;

    public LinqTest()
    {
        //普通のIEnumerable
        a = System.Linq.Enumerable.Range(0, 100_000_000);
        //List
        b = a.ToList();
        //配列
        c = a.ToArray();
        //無駄にWhereしてみる
        d = a.Where(x => x == x);
    }

    [Benchmark]
    public int WhereCountA()
    {
        return a.Where(x => x % 4 == 0).Count();
    }
    [Benchmark]
    public int CountA()
    {
        return a.Count(x => x % 4 == 0);
    }
    [Benchmark]
    public int WhereCountIndexA()
    {
        return a.Where((x, i) => x % 4 == 0).Count();
    }

    [Benchmark]
    public int WhereCountB()
    {
        return b.Where(x => x % 4 == 0).Count();
    }
    [Benchmark]
    public int CountB()
    {
        return b.Count(x => x % 4 == 0);
    }
    [Benchmark]
    public int WhereCountIndexB()
    {
        return b.Where((x, i) => x % 4 == 0).Count();
    }

    [Benchmark]
    public int WhereCountC()
    {
        return c.Where(x => x % 4 == 0).Count();
    }
    [Benchmark]
    public int CountC()
    {
        return c.Count(x => x % 4 == 0);
    }
    [Benchmark]
    public int WhereCountIndexC()
    {
        return c.Where((x, i) => x % 4 == 0).Count();
    }

    [Benchmark]
    public int WhereCountD()
    {
        return d.Where(x => x % 4 == 0).Count();
    }
    [Benchmark]
    public int CountD()
    {
        return d.Count(x => x % 4 == 0);
    }
    [Benchmark]
    public int WhereCountIndexD()
    {
        return d.Where((x, i) => x % 4 == 0).Count();
    }
}

テストパターンは以下の3*4です。

フィルタ方法

Where+Count
Countのみ
インデックス付きWhere+Count

フィルタ対象

IEnumerable<int>
List<int>
int[]
IEnumerable<int>+Where

こうなりました。

BenchmarkDotNet=v0.11.3, OS=Windows 10.0.15063.1508 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
Frequency=3312645 Hz, Resolution=301.8736 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3260.0
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3260.0

Method	Mean	Error	StdDev
WhereCountA	657.6 ms	1.044 ms	0.9770 ms
CountA	680.2 ms	2.699 ms	2.3923 ms
WhereCountIndexA	858.6 ms	15.043 ms	12.5617 ms
WhereCountB	436.5 ms	2.097 ms	1.8586 ms
CountB	863.3 ms	3.291 ms	2.9176 ms
WhereCountIndexB	936.8 ms	2.023 ms	1.6891 ms
WhereCountC	331.7 ms	1.438 ms	1.3451 ms
CountC	738.5 ms	2.932 ms	2.5994 ms
WhereCountIndexC	993.8 ms	13.260 ms	11.0729 ms
WhereCountD	963.2 ms	16.680 ms	14.7867 ms
CountD	1,249.4 ms	9.701 ms	8.5999 ms
WhereCountIndexD	1,414.5 ms	28.221 ms	30.1967 ms

フィルタ方法は、

1 < 2 < 3

の順です。

フィルタ対象は、

3 < 2 < 1 < 4

の順です。

どうしてこうなったのかは、「パフォーマンに差が出る理由は？」で説明します。

LINQとは

Language INtegrated Queryの略。(日本語にすると、統合言語クエリ)

C# 3.0の頃の機能なので、実は結構古株なお方。

「SQLっぽくて何かヤダ」とか「LINQって遅いんでしょ？」とか言って敬遠する人が多い。(当社調べ)

今回取り扱うメソッドについて

LINQと一言で言っても、色々なメソッドがあります。

その数なんと約200個！とは言っても、メソッドのオーバーロードを含めてなので実際は50～60個くらいです。

全てについて書いていたらキリがないので、前述のWhereを中心に書いて行きます。

Whereって？

以下が、Where<TSource>の定義です。

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
    
public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)

これだけみてもよくわからないので、公式リファレンスを見に行きましょう。

https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.where?view=netframework-4.7.2 より

Filters a sequence of values based on a predicate.

述語に基づいて一連の値をフィルタリングします。

となっています。

やっぱりよくわからないので、順を追って説明していきたいと思います。

引数のthisって？

Whereの説明の前に、「そのthisってなんだよ？」って思う方も多いでしょう。始めてみた時、僕は思いました。

こいつは拡張メソッドです。自作のメソッドをインスタンスメソッドかのように呼び出せます。見た目上、クラスに新たなメソッドを追加したかのような動作をさせることが出来ます。

自作のクラスに対して使うメリットはあまりありません。(どちらかと言うとデメリットのほうが大きい。)

最大のメリットは、インターフェースや他人が作ったクラスにインスタンスメソッドっぽい物を足せる事です。

IEnumerable<T>に対して、インスタンスメソッドを実装することは出来ません。(インターフェースの仕様)

そんな時でも拡張メソッドを用いて、あたかもインスタンスメソッドを持っているかのように振る舞う事が可能なのです。

Funcって？

Funcとはデリゲートの一種です。今回使用されているのは、Func<T,TResult>とFunc<T1,T2,TResult>です。C# 3.0の頃に追加された機能です。

それ以前はdelegateクラスを使用して作成していたものを、ジェネリクスを用いて(比較的)簡単に作れるようになりました。

Whereはこのデリゲートで渡された条件に従って、フィルタリングを行います。先述の述語ってやつです。

本当はもっと詳しく書くべきなんですが、~~面倒なので~~本題からそれてしまうので今回はカットです。

デリゲートって？

いきなりデリゲートとか言われても困る方も多いでしょう。初めて聞いた時、僕は困りました。

簡単に言うと、「メソッドを変数として扱うための機能」って感じですかね。C言語に触れたことが有る人なら、関数ポインタをイメージすると良いかもしれません。

C#の勉強をしていた人間が、つまづきやすい所No.1です。(当社調べ)

こいつも本当はもっと詳しく書くべきなんですが、~~面倒なので~~書ききれないのでカットです。

2つの違いって？

Whereメソッドですが、2つあります。違いは引数のデリゲートです。

1つ目はFunc<TSource, bool> predicateです。こいつはそのままフィルタリングするだけ。

2つ目はFunc<TSource, int, bool> predicateです。こいつもフィルタリングするのは同じなんですが、インデックスを持てます。0から始まり、1ずつインクリメントされて行きます。

大きな違いはありません。......と言いたいところですが、実はかなり大きな違いがあります。

この記事では、1つ目のWhereをメインで解説します。2つ目は後々出てきますので、存在だけ覚えておいてください。

遅延評価？

突然謎の単語が出てきました。遅延評価です。

Whereに限った話ではありませんが、LINQは遅延評価と呼ばれる評価の方法を採用しているメソッドが多いです。

読んで字のごとく、評価を遅らせる機能です。「宣言されたときではなく、必要になった時に計算する」んです。

public int LinqTest()
{
    //Listの作成
    var intList = Enumerable.Range(0, 100_000_000).ToList();
    //ここではまだ評価しない
    var odd = intList.Where(x=>x % 2 != 0);
    //Countで中身を見なければならないので、ここで評価
    return odd.Count();
}

ちょっとした例を書いてみました。

ちなみにCountは要素数を返すメソッドです。条件を指定することも可能です。

oddが宣言されたタイミングでは、何も起こりません。Countで数える時に初めて評価します。

この場合、50_000_000が戻り値になります。

ちょっとした注意事項的な何か

今回説明の都合上、intListに対してToListを実施しています。本来であれば、Count実施時に評価されるので不要です。パフォーマンスが落ちるので止めましょう。

Whereの中身って？

Whereですが、System.Core.dll → System.Linq名前空間の下にあります。

Enumerableクラス内で拡張メソッドとして定義されています。

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    //(1)
    if (source is Iterator<TSource>)
    {
        return ((Iterator<TSource>)source).Where(predicate);
    }
    //(2)
    if (source is TSource[])
    {
        return new WhereArrayIterator<TSource>((TSource[])source, predicate);
    }
    //(3)
    if (source is List<TSource>)
    {
        return new WhereListIterator<TSource>((List<TSource>)source, predicate);
    }
    //(4)
    return new WhereEnumerableIterator<TSource>(source, predicate);
}

if文が5個出てきます。

上2つは簡単です。元データやデリゲートがnullであれば例外を出力して終了。

問題はその下で、イテレータの名を冠する謎のクラスが4つ出てきます。

Iterator<TSource>
WhereArrayIterator<TSource>
WhereListIterator<TSource>
WhereEnumerableIterator<TSource>

彼らはEnumerableクラス内に定義されているprivateなクラスです。

なんとなく分かるかもしれませんが、2,3,4のクラスは、1を継承しています。

(1).Iterator

まずは1.Iterator<TSource>から行きたいと思います。

private abstract class Iterator<TSource> : IEnumerable<TSource>, IEnumerator<TSource>
{
    private int threadId;
    internal int state;
    internal TSource current;

    public Iterator()
    {
        threadId = Thread.CurrentThread.ManagedThreadId;
    }

    public TSource Current
    {
        get
        {
            return current;
        }
    }

    public abstract Iterator<TSource> Clone();

    public virtual void Dispose()
    {
        current = default(TSource);
        state = -1;
    }

    public IEnumerator<TSource> GetEnumerator()
    {
        if (threadId == Thread.CurrentThread.ManagedThreadId && state == 0)
        {
            state = 1;
            return this;
        }
        Iterator<TSource> iterator = Clone();
        iterator.state = 1;
        return iterator;
    }

    public abstract bool MoveNext();

    public abstract IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector);

    public abstract IEnumerable<TSource> Where(Func<TSource, bool> predicate);
    
    object IEnumerator.Current
    {
        get
        {
            return Current;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    void IEnumerator.Reset()
    {
        throw new NotImplementedException();
    }
    
    object IEnumerator.Current
	{
        get
        {
            return Current;
        }
    }
}

abstractなので抽象クラスです。メソッドの約半数もabstractです。

IEnumerable<TSource>を実装しているので、foreachや各種LINQにも対応しています。

このクラスは抽象クラスなので、インスタンスは作成されません。

既にWhere等でイテレータが作成済みの物に対して、再度Whereを行なった場合、Where内でキャストされます。Where(hoge).Where(huga)とかです。

この場合、拡張メソッドの優先順位の関係で、オーバーライド先のWhereが呼ばれます。

その後は、各メソッドのオーバーライド内容に従います。

(2).WhereArrayIterator

次に2.WhereArrayIterator<TSource>です。

private class WhereArrayIterator<TSource> : Iterator<TSource>
{
    private TSource[] source;
    private Func<TSource, bool> predicate;
    private int index;

    public WhereArrayIterator(TSource[] source, Func<TSource, bool> predicate)
    {
        this.source = source;
        this.predicate = predicate;
    }

    public override Iterator<TSource> Clone()
    {
        return new WhereArrayIterator<TSource>(source, predicate);
    }

    public override bool MoveNext()
    {
        if (state == 1)
        {
            while (index < source.Length)
            {
                TSource val = source[index];
                index++;
                if (predicate(val))
                {
                    current = val;
                    return true;
                }
            }
            Dispose();
        }
        return false;
    }

    public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector)
    {
        return new WhereSelectArrayIterator<TSource, TResult>(this.source, this.predicate, selector);
    }

    public override IEnumerable<TSource> Where(Func<TSource, bool> predicate)
    {
        return new WhereArrayIterator<TSource>(source, Enumerable.CombinePredicates<TSource>(this.predicate, predicate));
    }
}

SelectメソッドとWhereSelectArrayIteratorクラスが出てきましたが、今回Selectは扱わないので無視してください。(これ以降のクラスも同様です。)

このクラスのインスタンスが作成されるのは2パターンあります。

1つ目が、配列に対してWhereでフィルタリングを行なった場合。(2)のケースです。

コンストラクタの引数で、sourceとpredicateを設定します。元データが配列なので、sourceも配列です。そして配列のアクセス用にindexを持っています。

Whereの処理はこれで終わりです。遅延評価なので、評価対象データと評価方法だけ保存すればOK。後は必要になったら取り出します。(これ以降のクラスも同様です。)

2つ目が、オーバーライドされたWhereが呼ばれた場合。(1)のケースで、元々が配列だった場合です。

このときもやはり、コンストラクタの引数で、sourceとpredicateを設定します。その際にCombinePredicatesメソッドが実行されます。こいつは後の2つにも出てくるので、最後に説明します。

(3).WhereListIterator

次に3.WhereListIterator<TSource>です。

private class WhereListIterator<TSource> : Iterator<TSource>
{
    private List<TSource> source;
    private Func<TSource, bool> predicate;
    private List<TSource>.Enumerator enumerator;

    public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate)
    {
        this.source = source;
        this.predicate = predicate;
    }

    public override Iterator<TSource> Clone()
    {
        return new WhereListIterator<TSource>(source, predicate);
    }

    public override bool MoveNext()
    {
        switch (state)
        {
        case 1:
            enumerator = source.GetEnumerator();
            state = 2;
            goto case 2;
        case 2:
            while (enumerator.MoveNext())
            {
                TSource current = enumerator.Current;
                if (predicate(current))
                {
                    base.current = current;
                    return true;
                }
            }
            Dispose();
            break;
        }
        return false;
    }

    public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector)
    {
        return new WhereSelectListIterator<TSource, TResult>(this.source, this.predicate, selector);
    }

    public override IEnumerable<TSource> Where(Func<TSource, bool> predicate)
    {
        return new WhereListIterator<TSource>(source, Enumerable.CombinePredicates<TSource>(this.predicate, predicate));
    }
}

このクラスのインスタンスが作成されるのは2パターンあります。

1つ目が、Listに対してWhereでフィルタリングを行なった場合。(3)のケースです。

やはりコンストラクタの引数で、sourceとpredicateを設定します。元データがListなので、sourceはListです。

そしてindexの代わりに、List<T>.Enumerator構造体を持っています。前回、foreachで僕が間違えていたお方です。このお方が出てくる時は、パフォーマンスの話が出てくる時です。

2つ目が、オーバーライドされたWhereが呼ばれた場合。(1)のケースで、元々がListだった場合です。CombinePredicatesメソッドは後ほど。

(4).WhereEnumerableIterator

最後、(4).WhereEnumerableIterator<TSource>です。

private class WhereEnumerableIterator<TSource> : Iterator<TSource>
{
    private IEnumerable<TSource> source;
    private Func<TSource, bool> predicate;
    private IEnumerator<TSource> enumerator;

    public WhereEnumerableIterator(IEnumerable<TSource> source, Func<TSource, bool> predicate)
    {
        this.source = source;
        this.predicate = predicate;
    }

    public override Iterator<TSource> Clone()
    {
        return new WhereEnumerableIterator<TSource>(source, predicate);
    }

    public override void Dispose()
    {
        if (enumerator != null)
        {
            enumerator.Dispose();
        }
        enumerator = null;
        base.Dispose();
    }

    public override bool MoveNext()
    {
        switch (state)
        {
        case 1:
            enumerator = source.GetEnumerator();
            state = 2;
            goto case 2;
        case 2:
            while (enumerator.MoveNext())
            {
                TSource current = enumerator.Current;
                if (predicate(current))
                {
                    base.current = current;
                    return true;
                }
            }
            Dispose();
            break;
        }
        return false;
    }

    public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector)
    {
        return new WhereSelectEnumerableIterator<TSource, TResult>(this.source, this.predicate, selector);
    }

    public override IEnumerable<TSource> Where(Func<TSource, bool> predicate)
    {
        return new WhereEnumerableIterator<TSource>(source, Enumerable.CombinePredicates<TSource>(this.predicate, predicate));
    }
}

このクラスのインスタンスが作成されるのは2パターンあります。

1つ目が、Listでも配列でも無いIEnumerableに対してWhereでフィルタリングを行なった場合。(4)のケースです。

こいつもコンストラクタの引数で、sourceとpredicateを設定します。元データがIEnumerableなので、sourceはIEnumerableです。

そしてindexの代わりに、IEnumerator<TSource>構造体を持っています。

2つ目が、オーバーライドされたWhereが呼ばれた場合。(1)のケースで、元々がListでも配列でも無い場合です。

CombinePredicates

名前のまんまです。PredicatesをCombineする、つまりPredicatesを合体させるメソッドです。

private static Func<TSource, bool> CombinePredicates<TSource>(Func<TSource, bool> predicate1, Func<TSource, bool> predicate2)
{
    return delegate (TSource x)
    {
        if (predicate1(x))
        {
            return predicate2(x);
        }
        return false;
    };
}

引数で2つのpredicateを受け取り、「順番に実行するデリゲート」を返します。

このメソッドはデリゲートを作成するだけなので、この段階では何も実行されません。

インライン展開って？

何がパフォーマンに影響を与えているかを説明する前に、関数のパフォーマンスに関する話を少し。

C#では、関数化するとその分だけパフォーマンスが下がってしまいます。

関数を呼び出した時や戻る時のジャンプにかかるコストや、最適化が行えなくなることによる無駄な処理が原因です。

なので関数化せずに、全てmainメソッドに押し込んでしまいましょう。

......なんてことは出来ませんよね。死人が出ます。これじゃ不便なので、誰かがせっせと関数化した部分を元に戻してくれます。(C#コンパイラではなく、JIT(Just in time:必要になったら)コンパイラがやっているらしい)

この元に戻す行為をインライン展開と呼びます。

この便利な機能ですが、仮想呼び出しされている関数はインライン展開できません。

なので、インターフェースを介している時はこいつは働かないのです。(原理的に無理らしい)

前回の記事で、

var listStr = new List<string>() { "aaa", "abc", "bbc", "aba", "cbc", "bcc" };

//(1)
//IEnumerator<string> e = listStr.GetEnumerator();
List<string>.Enumerator e = listStr.GetEnumerator();
//(2)
while (e.MoveNext())
{
    //(3)
    string item = e.Current;
    if (item.Contains("a"))
    {
        Console.Write(item);
    }
}

こんなコードがありました。foreachのコンパイル後の姿です。

(1)でIEnumerator<string>ではなく、List<string>.Enumeratorに展開されています。

List<string>.Enumeratorは構造体なので、インライン展開できます。IEnumerator<string>にしてしまうとインライン展開できません。

パフォーマンスに影響するのでこういう形になっています。

パフォーマンに差が出る理由は？

順番に説明してきましょう。

`Count(hoge)`よりも～

一番最初に上げた例で、説明します。

public int LinqTest()
{
    //Listの作成
    var intList = Enumerable.Range(0, 100_000_000).ToList();
    //ここではまだ評価しない
    var odd = intList.Where(x=>x % 2 != 0);
    //Countで中身を見なければならないので、ここで評価
    return odd.Count();
}

Whereメソッドと、WhereListIteratorクラスです。必要な部分だけ抜き出してます。

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source is List<TSource>)
    {
        return new WhereListIterator<TSource>((List<TSource>)source, predicate);
    }
}

private class WhereListIterator<TSource> : Iterator<TSource>
{
    private List<TSource> source;
    private Func<TSource, bool> predicate;
    private List<TSource>.Enumerator enumerator;

    public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate)
    {
        this.source = source;
        this.predicate = predicate;
    }
}

今回sourceは(当たり前ですが)、Listです。なので、WhereListIteratorのインスタンスが作成されます。

元クラスのコンストラクタも実行されますが、マルチスレッドの時くらいしか関係しないので割愛。

Whereが実行された時点では、コンストラクタの引数からsourceとpredicateをローカルに保存して終了です。

次にCount(条件なし)ですが、以下のようになっています。

public static int Count<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    //ICollection<T>ではないし、
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null)
    {
        return collection.Count;
    }
    //ICollectionでもない
    ICollection collection2 = source as ICollection;
    if (collection2 != null)
    {
        return collection2.Count;
    }
    //ここまで来る
    int num = 0;
    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            num = checked(num + 1);
        }
        return num;
    }
}

引数のsourceはWhereListIteratorなので、一番下のusingまで来ます。

このusingから先は前回お話した、foreachのコンパイル後の姿と同じです。

現在、sourceはWhereListIterator<TSource>です。改めてWhereListIteratorのMoveNextを見てみると、

private class WhereListIterator<TSource> : Iterator<TSource>
{
    //元クラスのメンバ
    internal int state;
    internal TSource current;

    public TSource Current
    {
        get
        {
            return current;
        }
    }
    
    //派生クラスのメンバ
    private List<TSource> source;
    private Func<TSource, bool> predicate;
    private List<TSource>.Enumerator enumerator;
    
    public override bool MoveNext()
    {
        switch (state)
        {
        case 1:
            enumerator = source.GetEnumerator();
            state = 2;
            goto case 2;
        case 2:
            while (enumerator.MoveNext())
            {
                TSource current = enumerator.Current;
                if (predicate(current))
                {
                    base.current = current;
                    return true;
                }
            }
            Dispose();
            break;
        }
        return false;
    }
}

こうなってました。

改めてソースを見ると、WhereListIterator<T>.MoveNext()の内部で、再度enumerator.MoveNext()を行なっています。

ここでのenumeratorは、List<TSource>.Enumeratorです。そしてCount内のenumeratorは、IEnumerator<TSource>です。

なので、Countの中ではインライン展開されず最適化できませんが、そのさらに内側のWhereListIteratorの中では、インライン展開され最適化できるようになっています。

一方、Count(条件なし)ですが、以下のようになっています。

public static int Count<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    int num = 0;
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            num = checked(num + 1);
        }
    }
    return num;
}

この場合、ListをIEnumerable<TSource> で受け取っています。なので、foreachを行う際に、List<TSource>.Enumeratorに展開できず、IEnumerator<TSource>として展開されてしまいます。

結果、インライン展開されず最適化できないので、およそ2倍の時間が掛かってしまいます。

配列に関しても同様です。

`First`,`Last`,`Single`,`Any`も～

First,Last,Single,Any(条件なし)の、ソースコードです。

public static TSource First<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        if (((ICollection<TSource>)list).Count > 0)
        {
            return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (enumerator.MoveNext())
            {
                return enumerator.Current;
            }
        }
    }
    throw Error.NoElements();
}

public static TSource Last<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        int count = ((ICollection<TSource>)list).Count;
        if (count > 0)
        {
            return list[count - 1];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (enumerator.MoveNext())
            {
                TSource current;
                do
                {
                    current = enumerator.Current;
                }
                while (enumerator.MoveNext());
                return current;
            }
        }
    }
    throw Error.NoElements();
}

public static TSource Single<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        switch (((ICollection<TSource>)list).Count)
        {
        case 0:
            throw Error.NoElements();
        case 1:
            return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (!enumerator.MoveNext())
            {
                throw Error.NoElements();
            }
            TSource current = enumerator.Current;
            if (!enumerator.MoveNext())
            {
                return current;
            }
        }
    }
    throw Error.MoreThanOneElement();
}

public static bool Any<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        if (enumerator.MoveNext())
        {
            return true;
        }
    }
    return false;
}

そして、First,Last,Single,Any(条件あり)の、ソースコードです。

public static TSource First<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate == null)
    {
        throw Error.ArgumentNull("predicate");
    }
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            return item;
        }
    }
    throw Error.NoMatch();
}

public static TSource Last<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate == null)
    {
        throw Error.ArgumentNull("predicate");
    }
    TSource result = default(TSource);
    bool flag = false;
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            result = item;
            flag = true;
        }
    }
    if (flag)
    {
        return result;
    }
    throw Error.NoMatch();
}

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate != null)
    {
        TSource result = default(TSource);
        long num = 0L;
        foreach (TSource item in source)
        {
            if (predicate(item))
            {
                result = item;
                num = checked(num + 1);
            }
        }
        switch (num)
        {
        case 0L:
            throw Error.NoMatch();
        case 1L:
            return result;
        default:
            throw Error.MoreThanOneMatch();
        }
    }
    throw Error.ArgumentNull("predicate");
}

public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate == null)
    {
        throw Error.ArgumentNull("predicate");
    }
    foreach (TSource item in source)
    {
        if (predicate(item))
        {
            return true;
        }
    }
    return false;
}

ものすごく長くなってしまいましたが、全てCountと同じことが言えます。

しかし、FirstとAnyは、見つけた段階で即時returnです。なので、最初の方で見つかった場合、ほとんど変わらない影響を受けません。

そして、LastとSingleはFirstに比べると使われる頻度が少ないと思います。(そんなことなかったらごめんなさい)

なので、(有効な局面は少ない)とさせていただきました。

index付きの`Where`は～

index付きのWhereは、以下のようになっています。

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }
    return WhereIterator(source, predicate);
}

private static IEnumerable<TSource> WhereIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    int index = -1;
    foreach (TSource item in source)
    {
        index = checked(index + 1);
        if (predicate(item, index))
        {
            yield return item;
        }
    }
}

通常のWhereは、Listや配列に対して最適化されていました。しかし、Index付きWhereは最適化されていません。何も解説がいらないくらいシンプルです。

この場合も、ListをIEnumerable<TSource> で受け取っています。なので、IEnumerator<TSource>として展開されてしまい、インライン展開されず最適化できません。その上、インクリメント処理も行なっており、更に遅くなってしまいます。

不要な`Where`は～

Whereは複数回呼び出した場合、CombinePredicatesによって条件が結合されます。

デリゲートもインライン展開出来ないです。なので、Whereを使えば使うほどジャンプする回数が増えパフォーマンスが落ちてしまうのです。

private static Func<TSource, bool> CombinePredicates<TSource>(Func<TSource, bool> predicate1, Func<TSource, bool> predicate2)
{
    return delegate (TSource x)
    {
        if (predicate1(x))
        {
            return predicate2(x);
        }
        return false;
    };
}

どうしてもWhereを減らすのが難しい場合は、より厳しい条件を前に持ってくることで改善できます。

public class WTest
{
    public List<int> a;
    public WTest()
    {
        a = System.Linq.Enumerable.Range(0, 100_000_000).ToList();
    }

    [Benchmark]
    public int SingleWhere()
    {
        //こいつが理想だが
        return a.Where(x => (x % 9_999_991 == 0) && (x % 2 == 0)).Count();
    }

    [Benchmark]
    public int DoubleWhere()
    {
        //これよりは
        return a.Where(x => x % 2 == 0).Where(x => x % 9_999_991 == 0).Count();
    }

    [Benchmark]
    public int DoubleWhereKai()
    {
        //こっちのほうがマシ
        return a.Where(x => x % 9_999_991 == 0).Where(x => x % 2 == 0).Count();
    }
}

BenchmarkDotNet=v0.11.3, OS=Windows 10.0.15063.1508 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
Frequency=3312645 Hz, Resolution=301.8736 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3260.0
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3260.0

Method	Mean	Error	StdDev
SingleWhere	416.0 ms	5.625 ms	4.986 ms
DoubleWhere	688.5 ms	9.355 ms	8.751 ms
DoubleWhereKai	599.7 ms	5.521 ms	5.164 ms

改めて結論

Listや配列形式でデータがある場合は、Count(hoge)よりもWhere(hoge).Count()のほうがパフォーマンスに優れている。
すでにIEnumerable<T>等の型になっている場合、どちらでも変わらない。
First,Last,Single,Anyも同様のことが言える。
極力Whereは1度で済ませる。
どうしても難しかったらより厳しい条件を前に。

以上です。

おわりに

とても長くなってしまいましたが、最後までお付き合いくださいありがとうございました。

過去2回分よりは実用性があるんじゃないかと思ってます。が、それでもたかが知れている気もします。

ちなみに次回の予定はSelectです。~~が、Whereほど書くことが無いので書かないかもしれません。~~

参考文献

~~参考にしたページを書く脳みそが付いたらしいです。~~

[雑記] インライン化 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

IEnumerator の別実装 | ++C++; // 未確認飛行 C ブログ

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

WhereとCountのパフォーマンスについて本気出して調べてみた

はじめに

たまには結論から述べるスタイル

パフォーマンスの根拠は？

LINQとは

今回取り扱うメソッドについて

Whereって？

引数のthisって？

Funcって？

デリゲートって？

2つの違いって？

遅延評価？

ちょっとした注意事項的な何か

Whereの中身って？

(1).Iterator

(2).WhereArrayIterator

(3).WhereListIterator

(4).WhereEnumerableIterator

CombinePredicates

インライン展開って？

パフォーマンに差が出る理由は？

Count(hoge)よりも～

First,Last,Single,Anyも～

index付きのWhereは～

不要なWhereは～

改めて結論

おわりに

参考文献

`Count(hoge)`よりも～

`First`,`Last`,`Single`,`Any`も～

index付きの`Where`は～

不要な`Where`は～