LINQが遅いと言われてたので速度比較してみた

きっかけ
=======

facebookのタイムラインでLINQ遅いって言ってる人がいたので、
何番煎じか分からないけど、速度比較してみた。

測定環境
--------

* Visual Studio 2013
* Visual Studio 2015 のASP.NET CoreCLR
* mono 3.10@Ubuntu (Hyper-V上のゲストOS。ホストマシンはVSのと同じマシン)

実行コード
------

```csharp
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace LinqTest
{
    public class Program
    {
        public void Main(string[] args)
        {
            var range1 = Enumerable.Range(1, 10000000);
            var range2 = Enumerable.Range(1, 10000000);
            var range3 = Enumerable.Range(1, 10000000);
            //LINQ
            var start = DateTime.Now;
            var list1 = range1.Where(_ => _ % 2 == 0)
                        .Select(_ => (float)_)
                        .ToList();
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            //foreach
            start = DateTime.Now;
            var list2 = new List<float>();
            foreach (var it in range2)
            {
                if (it % 2 == 0)
                    continue;
                list2.Add(it);
            }
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            //LINQ+foreach
            start = DateTime.Now;
            var list3 = new List<float>();
            foreach (var it in range3.Where(_ => _ % 2 == 0).Select(_ => (float)_))
            {
                list3.Add(it);
            }
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            Console.WriteLine("counts: {0}, {1}, {2}", list1.Count, list2.Count, list3.Count);
            Console.ReadLine();
        }
    }
}
```

結果
-------
* VS2013


```
227.0186 ms
196.0081 ms
197.0254 ms
counts: 5000000, 5000000, 5000000

```

* VS2015 CoreClr

```
350.131 ms
184.0339 ms
324.9954 ms
counts: 5000000, 5000000, 5000000
```

* mono

```
379.231 ms
206.293 ms
392.178 ms
counts: 5000000, 5000000, 5000000
```

一般的な結論
------
確かにLINQ使うと数値上は遅くなる。
でも、1千万件ループにつき173msだから、1ループあたり17.3*10^-9秒(17.3ナノ秒)程度でしかない。
つまり、遅くはなるが「誤差の範囲」程度でしかない。
それに比べれば、複雑になった時のLINQの遅延評価による速度向上の恩恵の方が強い。

この程度の差ならば、一般的なプログラミングにおけるボトルネックとはなりえない。
他にもっと効果的なパフォーマンス改善が得られる場所があるはずです。


(おまけ)ループ回数が少ない場合
=======

上記コードをループする回数を10000回にして計測してみた
(ループ回数が少ないと計測誤差が大きくでるので、数値は大体の傾向と思ってください)

結果
-----

* VS2013

```
12.002 ms
0.998 ms
0 ms
counts: 5000, 5000, 5000
```

メモ: 下２つは測定繰り返すと0～1msぐらいで値がブレてました。最初のもブレブレ。。。

* VS2015 CoreCLR

```
11.0213 ms
0.9956 ms
0 ms
counts: 5000, 5000, 5000
```

メモ: これも測定毎に結構値がブレてます。信頼性があるのはLINQ単体が遅いってぐらいでしょうか。

* mono

```
11.0213 ms
0.9956 ms
0 ms
counts: 5000, 5000, 5000
```

メモ: これも(ry ブレが更にヒドイ。。。

結果メモ
-----

ToList<T>()が何故か遅い！10msもかかってる！

なぜToList<T>()は遅い？
----------

githubのmonoのソースコードを見てみました。
先に結論を言うと、怪しそうな箇所はあるが分からなかったです。
(なお、Unityのmonoも同じコードで差分はありませんでした)

[Enumerable.ToList](https://github.com/mono/mono/blob/5f5bed4643181a26ab8b7a529f032ee1e3c7cb96/mcs/class/System.Core/System.Linq/Enumerable.cs#L2948)

ToList<T>()は単純にreturn new List<T>(source)をしています。(Checkは単にぬるぽチェックしているだけです)

[List.ctor](https://github.com/mono/mono/blob/5f5bed4643181a26ab8b7a529f032ee1e3c7cb96/mcs/class/corlib/System.Collections.Generic/List.cs#L60)

Listのコンストラクタを見てみると、ICollection <T> c = collection as ICollection <T>;という遅そうな関数を見つけました。

このasが遅いのでは？ 単にList.AddEnumerableする拡張メソッドを生やせば速くなるかも？

検証コード
--------

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinqTest2
{
    class Program
    {
        static void Main(string[] args)
        {
            var range1 = Enumerable.Range(1, 10000);
            var range2 = Enumerable.Range(1, 10000);
            var range3 = Enumerable.Range(1, 10000);
            var start = DateTime.Now;
            var list1 = range1.Where(_ => _ % 2 == 0)
                        .Select(_ => (float)_)
                        .ToList();
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            start = DateTime.Now;
            var list2 = range2.Where(_ => _ % 2 == 0)
                         .Select(_ => (float)_)
                         .ToListEx();
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            start = DateTime.Now;
            var list3 = range3 as ICollection<int>;
            Console.WriteLine("{0} ms", (double)(DateTime.Now.Ticks - start.Ticks) / TimeSpan.TicksPerMillisecond);
            Console.WriteLine("counts: {0}, {1}, {2}", list1.Count, list2.Count, list3 == null ? 0 : list3.Count);
            Console.ReadLine();
        }
    }
    static class ListExtensions
    {
        public static List<T> ToListEx<T>(this IEnumerable<T> source)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            var result = new List<T>();
            foreach (var t in source)
            {
                result.Add(t);
            }
            return result;
        }
    }
}

```

monoでの実行結果
---

```
17.763 ms
0.654 ms
0.002 ms
counts: 5000, 5000, 0
```

メモ: ブレる……

結果メモ
-----
ToListのコードを単純化(ToListEx)すると10msぐらい高速化したけど、asがボトルネックという結果は得られなかった
よって、ToListに改良の余地はあるが、どこが原因かは分からなかった。

結論
=====

LINQは遅いっていうのは、ボトルネックの考え方的に間違いである。
ただし、LINQの一部関数は遅いので改良の余地はありそう。
(Unityは誰か検証やってくれー)