LINQでメモリを節約しないと処理速度はどうなってしまうのか


本記事は、エムティーアイ Advent Calendar 2016 20日目 の記事です。

本記事の目的は?

備忘録です。
以前、LINQの実装ミスで、データ取得ロジックの負荷が高まって、処理速度に大きな影響を与えてしまったことがありました。
もう1ヶ月くらい前の話なのですが、どれくらいになっていたのか実際に測定して見よー、と思ったのでやってみました。

どんな実装ミス?

下記です。
numsAとnumsBの被っている数値を、resultに格納するという簡単な処理を、修正前と修正後の2パターン書いてあります。
修整前と修正後の違いは、ToList()メソッドの呼び出しタイミングです。
もちろん、修正後の方が速く処理します。

実装時は、もう少し複雑でしたが、簡潔にかくとこんな感じです。

修整前
var numsA = Enumerable.Range(1, 100).ToList();
var numsB = Enumerable.Range(1, 100000);
var result = numsA.FindAll(a => numsB.ToList().Exists(b => b == a));
修整後
var numsA = Enumerable.Range(1, 100).ToList();
var numsB = Enumerable.Range(1, 100000).ToList();
var result = numsA.FindAll(a => numsB.Exists(b => b == a));

何が起こったの?

LINQは遅延評価されます。
LINQは、IEnumerable<T>オブジェクト以外の、何らかの結果を要求するまで、実体化しません。
上記の例では、Listのメソッドとなる.ToList()がその要求にあたります。

FindAllメソッドは、対象の要素分ループして何かしらの処理を行うメソッドです。
修正前では、numsAの要素分、毎回numsBを実体化しているので、遅くなります。

具体的にこれぐらい

numsB、numsAの要素数を変えて、処理時間を測定して見ました。
測定方法:System.Diagnostics.Stopwatchでのよくある方法で。

Stopwatch sw = new Stopwatch();
sw.Start();
//処理
sw.Stop();

numsBの要素数を変えた際の処理速度の違い

まずは、実際実体化させているnumsBの要素数を100000, 1000000, 10000000と変化させます。下記のようになりました。
numsAの要素数は1000で固定しています。

要素数が100倍になった時、修正後ではほぼ変わっていませんが、修正前では指数関数的に約70倍に伸びています。

追記:よく見たら間違えていました。
修正後ではほぼ変わっていませんが 

修正後の方でも、同様に指数関数的に伸びていますが、それでも1秒にはみたない程度です。

numAの要素数を10倍にした際の処理速度の違い

numsAを100から1000に変えた時に違いは、下記のようになりました。
numsBは、先ほどの中での最大値10,000,000で固定です。

ループ数が10倍になったので、修正前の方の処理時間もしっかり10倍(9.69倍)に伸びています。
修正後ではほぼ変わっていません。

想像していたような結果になりましたが、こうやって改めてみると怖いですね。

終わりに

知っている方からすれば、当然の事例かもしれませんが、こうやって測定してみると面白いですね。
これからもやっていこうと思います。

参考文献

LINQの処理中に使うメモリを節約するには?