LINQのWhereやSelect連打のパフォーマンス最適化について

Where連打していますか？それともパフォーマンスの悪化を心配して&&連結にしていますか？LINQの仕組み＆遅延評価の正しい基礎知識 － ＠ITではWhere+Selectに対して

「WhereSelectEnumerableIterator」となっていて、名前のとおり、WhereとSelectが統合されていることです。これは、「Where」->「Select」が頻出パターンなので、それらを統合することでパフォーマンスを向上させるためでしょう。

と書きましたが、では連打の場合はどうなっているでしょうか。見てみましょう。

var seq1 = Enumerable.Range(1, 10)
    .Where(x => x % 2 == 0)
    .Where(x => x % 3 == 0);

// どうでもいいんですが、これはVisual Studio 11 Betaです。VS11最高ですよ！

@ITの記事では、sourceに格納されて内包した形の連鎖となっている、と書きました。しかしseq1のsourceはRangeIteratorで、Where連打のはずなのに、すぐ上の階層が元ソースとなっています。そして、predicateの名前がCombinePredicates。はい、その通りで、2つの条件式が連結されています。確認してみましょう。

var pred = (Func<int, bool>)seq1.GetType().GetField("predicate", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(seq1);

Console.WriteLine(pred(2)); // false
Console.WriteLine(pred(3)); // false
Console.WriteLine(pred(6)); // true

というわけで、Where連打はpredicateが連結されて一つのWhereに最適化されることが確認できました。LinqとCountの効率でICollectionやIListの場合の特別扱いなケースがあることを紹介しましたが、Whereに関しても同様な特別扱いが発生するというわけです。

Selectの場合

Whereの他にSelectの場合も、同じような最適化を行ってくれます。

var seq2 = Enumerable.Range(1, 10)
    .Select(x => x * 2)
    .Select(x => x + 10);

var selector = (Func<int, int>)seq2.GetType().GetField("selector", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(seq2);

Console.WriteLine(selector(2)); // 2 * 2 + 10 = 14
Console.WriteLine(selector(5)); // 5 * 2 + 10 = 20

sourceのすぐ上がRangeIteratorで、selectorにCombineSelectorsとして格納されていました。なお、型名であるWhereSelectEnumerableIteratorのとおり、現在はpredicateはnullですが、前段にWhereを書けばpredicateに格納されて、やはりWhere+Selectの最適化となります。では、後段にWhereを書いた場合は……？

最適化されない場合

Where+SelectとSelect+Whereは異なるものです。見てみましょう。

var whereSelect = Enumerable.Range(1, 10)
    .Where(x => x % 2 == 0)
    .Select(x => x * 2);

var selectWhere = Enumerable.Range(1, 10)
    .Select(x => x * 2)
    .Where(x => x % 2 == 0);

Where+SelectはWhereSelectEnumerableIteratorのpredicateとselectorにそれぞれデリゲートが格納され、ひとまとめに最適化されていますが、Select+WhereはsourceがRangeIteratorではなくWhereSelectEnumerableIteratorであるように、普通に階層の内包構造となっています。Selectの後にWhereは最適化されません。まあ、そりゃ値が変形されているのだからpredicateがひとまとまりになるわけがなく、当たり前ではあります。

次にインデックスが使えるオーバーロードのケースを見てみましょう。

var whereIndex = Enumerable.Range(1, 10)
    .Where(x => x % 2 == 0)
    .Where((x, i) => i % 2 == 0);

var selectIndex = Enumerable.Range(1, 10)
    .Select(x => x * 2)
    .Select((x, i) => i * 2);

// GetEnumeratorしないとpredicate/selectorとsourceがnullです
// これはyield returnによる生成なためです
whereIndex.GetEnumerator();
selectIndex.GetEnumerator();

これもひとまとめにしようにも、しようがないので、当然といえば当然ですね。

IQueryableの場合

IQueryableだとどうなのか、というと……

// LINQ to SQL - AdventureWorks sample
var ctx = new AdventureWorksDataContext();
var query = from model in ctx.ProductModel
            where model.Name == "hoge"
            where model.ProductModelID == 100
            select model.Instructions;

Console.WriteLine(query);

// 結果
SELECT [t0].[Instructions]
FROM [Production].[ProductModel] AS [t0]
WHERE ([t0].[ProductModelID] = @p0) AND ([t0].[Name] = @p1)

というわけで、LINQ to SQLはand連結されますね。ここで注意なのが、どういう挙動を取るのかは全てクエリプロバイダの解釈次第です。例えばLINQ to Twitterはwhere連打ではダメで、&&で連結しなければなりません。

Reactive Extensionsの場合

Reactive Extensionsの場合も見てみましょうか。Rx-Main(1.0.11226)では、というと

var rx = Observable.Range(1, 10)
    .Where(x => x % 2 == 0)
    .Where(x => x % 3 == 0);

さっぱりワケワカメですが、とりあえずひとまとめになってないのでは感でしょうか。それにしても本当にワケワカメ。次にRx_Experimental-Main(1.1.11111)は、というと

var pred = (Func<int, bool>)rx.GetType().GetField("_predicate", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(rx);

Console.WriteLine(pred(2)); // false
Console.WriteLine(pred(3)); // false
Console.WriteLine(pred(6)); // true

_predicate発見！Experimental版では挙動が改善され、ひとまとめにされているようです。IDisposable<Generate>は、Rangeの生成がGenerateメソッドによってなされているからですね。しかし、やはり読み取りにくい。

Rx v2

3/5にReactive Extensions (Rx) v2.0 Betaの配布がスタートしています。NuGetではInstall-Package Rx-Main -Preで配布されていますね。改善内容は後日詳しくということでまだ詳しくは出てないのですが、v2というだけあって中身はガラッと変わっています。とりあえず、見てみましょう。

もちろん、predicateはひとまとめにされているのですが、それだけじゃなくて、とにかく見やすい、分かりやすい。しかし、ところどころ変ですね、Observαble(aがアルファ)だのΩだの。v2はソースのキチガイ度が跳ね上がっているのでILSpyとかで覗いちゃえる人は一度見ちゃうといいと思います、頭おかしい。あと、C#でのプログラミング的な小技も効いてたりして、テクニックの学習にもとても良い。

スタックトレースへの影響

このコードのクリアさはスタックトレースにも良い影響を与えています。まず、Rx v1で見てみると

try
{
    Observable.Range(1, 10)
        .Where(x => x % 2 == 0)
        .Take(10)
        .Timestamp()
        .Subscribe(_ => { throw new Exception(); });
}
catch (Exception ex)
{
    Console.WriteLine(ex.StackTrace);
}

場所 ConsoleApplication9.Program.<Main>b__1(Timestamped`1 _) 場所 c:\Users\ne
場所 System.Reactive.AnonymousObserver`1.Next(T value)
場所 System.Reactive.AbstractObserver`1.OnNext(T value)
場所 System.Reactive.AnonymousObservable`1.AutoDetachObserver.Next(T value)
場所 System.Reactive.AbstractObserver`1.OnNext(T value)
場所 System.Reactive.Linq.Observable.<>c__DisplayClass408`2.<>c__DisplayClass40a.<Select>b__407(TSource x)
場所 System.Reactive.AnonymousObserver`1.Next(T value)
場所 System.Reactive.AbstractObserver`1.OnNext(T value)
場所 System.Reactive.AnonymousObservable`1.AutoDetachObserver.Next(T value)
場所 System.Reactive.AbstractObserver`1.OnNext(T value)
場所 System.Reactive.Linq.Observable.<>c__DisplayClass43e`1.<>c__DisplayClass440.<Take_>b__43d(TSource x)
// 以下略

これは酷い。こんなの見ても何一つ分かりはしません。では、Rx v2で試してみると

場所 ConsoleApplication10.Program.<Main>b__1(Timestamped`1 _) 場所 c:\Users\n
場所 System.Reactive.AnonymousObserver`1.Next(T value)
場所 System.Reactive.ObserverBase`1.OnNext(T value)
場所 System.Reactive.Linq.Observαble.Timestamp`1._.OnNext(TSource value)
場所 System.Reactive.Linq.Observαble.Take`1._.OnNext(TSource value)
場所 System.Reactive.Linq.Observαble.Where`1._.OnNext(TSource value)
場所 System.Reactive.Linq.Observαble.Range._.LoopRec(Int32 i, Action`1 recurse)
場所 System.Reactive.Concurrency.Scheduler.<>c__DisplayClass3a`1.<InvokeRec1>b__37(TState state1)
// 以下略

めっちゃよく分かる。Timestamp->Take->Where->Rangeという遡りがしっかり見える。何て素晴らしいんだ！

匿名 vs 有名

さて、どういうことかというと、これ、neue cc - Rx(Reactive Extensions)を自前簡易再実装するで紹介したような、ラムダ式をぶん投げてその場で匿名のクラスを作るAnonymousパターンをやめたんですね。で、代わりに名前付きのクラスを立ててる。だから分かりやすい。

これ、uupaaさんが仰ってるナビ子記法←ググッた先の本人のスライドが、Handsoutがサービス終了で見れないので、紹介のある記事にリンクします-などにも近いところがあるかなあ、と。

ただやっぱ書くのにはコスト高というか匿名で書けることの良さを殺してしまうので、ライブラリサイドだったら検討する、アプリケーションサイドだったらやらない、になってしまうかなあ。ライブラリサイドであってもかなり手間なので、よほど余裕あるとかでないとやらない、かなあ。JavaScriptならともかくC#では、特に……。

Rx v2についてもう少し

詳しい話は詳細が出てから、と思いますが（と言いながらRxJSの話も結局書いてないので、あうあう）、とりあえずObservableへの拡張メソッド郡はExperimentalから変化は特にありません。ただ、Experimentalは既にStableとはかなり違っているので、Stableしか追っかけてない人は、かなり目新しいものを見かけることができると思います。

内部実装は見たとおりガラッと変わって、スタックトレースも見やすくなった、などなどなわけですが、それとあわせてパフォーマンスも相当上がっています。v1で基本的な部分を固めたので、v2ではそういった周辺部分に本気で取り組みだした、ということですね。

まとめ

LINQは細かいところまで配慮が行き届いていて本当に素晴らしいですね。というわけで平然とWhereの連打かましましょう。私もつい昨日にWhere6連打かましたりしてました。

linq.js - LINQ for JavaScriptはさすがにここまではやってないんですが、いずれかはやりたいですね。その前にやらなきゃならないことがありすぎて当面はないですけれど。うーん、なんかもう色々やることありすぎて、かつそれなりに忙しくて、頭が爆発しそうです。はっきしいってヤバい。で、こうしてヤバくなると、硬直しちゃって余計に何もできなくなったり、唐突にこうして息抜き記事を書き出したり、うみみぅ。まあともかく、がんばろふ。