Posted at

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

More than 3 years have passed since last update.


きっかけ

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

メモ: 下2つは測定繰り返すと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も同じコードで差分はありませんでした)

Enumerable.ToList

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

List.ctor

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は誰か検証やってくれー)