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

# はじめに

[前回](https://qiita.com/NCT48/items/d8394d587e9fee969ca9)は`foreach`について色々書いてみました。

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

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

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

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

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

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

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

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

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

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

```c#
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です。

フィルタ方法

1. `Where`+`Count`
2. `Count`のみ
3. インデックス付き`Where`+`Count`

フィルタ対象

1. `IEnumerable<int>`
2. `List<int>`
3. `int[]`
4. `IEnumerable<int>`+`Where`

こうなりました。

```ini
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>`の定義です。

```c#
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は遅延評価と呼ばれる評価の方法を採用しているメソッドが多いです。

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

```c#
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`クラス内で拡張メソッドとして定義されています。

https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs

`````c#
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つ出てきます。

1. `Iterator<TSource>`
2. `WhereArrayIterator<TSource>`
3. `WhereListIterator<TSource>`
4. `WhereEnumerableIterator<TSource>`

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

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

### (1).Iterator

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

```c#
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>`です。

```c#
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>`です。

```c#
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`構造体を持っています。[前回](https://qiita.com/NCT48/items/d8394d587e9fee969ca9)、`foreach`で僕が間違えていたお方です。このお方が出てくる時は、パフォーマンスの話が出てくる時です。

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

### (4).WhereEnumerableIterator

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

```c#
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を合体させるメソッドです。

```C#
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:必要になったら)コンパイラがやっているらしい)

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

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

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

[前回](https://qiita.com/NCT48/items/d8394d587e9fee969ca9)の記事で、

```c#
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)`よりも～

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

```c#
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`クラスです。必要な部分だけ抜き出してます。

```c#
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`(条件なし)ですが、以下のようになっています。

https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs

```c#
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`から先は[前回](https://qiita.com/NCT48/items/d8394d587e9fee969ca9)お話した、`foreach`のコンパイル後の姿と同じです。

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

```c#
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`(条件なし)ですが、以下のようになっています。

https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs

```c#
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`(条件なし)の、ソースコードです。

https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs

```c#
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`(条件あり)の、ソースコードです。

```c#
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`は、以下のようになっています。

https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs

```c#
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`を使えば使うほどジャンプする回数が増えパフォーマンスが落ちてしまうのです。

```c#
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`を減らすのが難しい場合は、より厳しい条件を前に持ってくることで改善できます。

```c#
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();
    }
}
```

``` ini
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

https://ufcpp.net/study/csharp/structured/miscinlining/

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

https://ufcpp.net/blog/2018/12/FastEnumerator/