きっかけ
facebookのタイムラインでLINQ遅いって言ってる人がいたので、
何番煎じか分からないけど、速度比較してみた。
測定環境
- Visual Studio 2013
- Visual Studio 2015 のASP.NET CoreCLR
- mono 3.10@Ubuntu (Hyper-V上のゲストOS。ホストマシンはVSのと同じマシン)
実行コード
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()が何故か遅い！10msもかかってる！
なぜToList()は遅い？
githubのmonoのソースコードを見てみました。
先に結論を言うと、怪しそうな箇所はあるが分からなかったです。
(なお、Unityのmonoも同じコードで差分はありませんでした)
ToList()は単純にreturn new List(source)をしています。(Checkは単にぬるぽチェックしているだけです)
Listのコンストラクタを見てみると、ICollection c = collection as ICollection ;という遅そうな関数を見つけました。
このasが遅いのでは？ 単にList.AddEnumerableする拡張メソッドを生やせば速くなるかも？
検証コード
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は誰か検証やってくれー)