LINQは本当に強力だ (1)　データ加工の究極の道具

長い間、.NET2.0から知識をアップグレードしていなかったのだが、先日一気に.NET4.0の知識を詰め込んだ。
LINQに触る必要性から、匿名デリゲート・ラムダ式・匿名クラス・式ツリー・拡張メソッドなどを覚えたのだが、はっきり言って今まで勉強を放置してきた事に、激しく後悔している。
「食わず嫌い」だったのは、矢継ぎ早に追加される新しい構文に対する抵抗だったような気がする。C++のテンプレート拡張がもめたらしいのも、気持ちはよくわかる。

テンプレートもそうだが、LINQも言語思想の革命と言っても言い過ぎではないぐらいのインパクトがあった。

LINQの何が良いかと言えば、比類なき拡張性だろう。これを支えているのはIEnumerable<T>インターフェイスと、拡張メソッド構文なわけだが、LINQに触ったことが無い人向けに、興味が持てそうな事を書いてみる（但し無保証 :-) まぁ、もう既に「枯れた」技術になり始めてる気がするので、今更だが）

IEnumerable<T>インターフェイスは、List<T>ジェネリッククラスや配列が実装している。というよりも、「列挙」可能なクラスには、このインターフェイスが実装されている（ちなみに、非ジェネリックなIEnumerableは列挙可能だが、LINQで使うには難点があるので省略）。

このインターフェイスが実装されていれば、以下のようにforeach出来る。

List<string> nameList = new List<string>();
// ...
foreach (string name in nameList)
{
    // 様で呼んでくれなきゃやだ
    if (name.EndsWith("様") == true)
    {
        Console.WriteLine(name);
    }
}

＃ varはわざと使ってないよ？（一応、.NET 2.0技術者向け）
で、LINQでforeachの部分を以下のように書ける。

// LINQクエリ（まだ実行されない）
IEnumerable<string> kingNames =
    // nameListの個々の要素をnameとして取り出し、
    from name in nameList
    // nameの終端が"様"の場合に、
    where name.EndsWith("様") == true
    // このクエリの結果要素としてnameを返す。
    select name;

// クエリの結果を列挙
foreach (string name in kingNames)
{
    Console.WriteLine(name);
}

「仮」に、nameListの要素数が非常に多かったとする（100万件とか）。
その場合に、以下のように「AsParallel()メソッドを呼び出す」だけで、”様”付きの判定をマルチスレッド化出来る。

IEnumerable kingNames =
    from name in nameList.AsParallel()
    where name.EndsWith("様") == true
    select name;

大量の要素の、しかしながら個々の要素の判定にはそれほどの判定コストを必要としない場合でも、この「PLINQ（パラレルLINQ）」は効率的に動作するはずだ。

通常、マルチスレッドで同じことを行う場合、以下のようなコードとなる。

private readonly List<T> kingNames = new List<T>();
private int count = 1;
private readonly ManualResetEvent final = new ManualResetEvent(false);

// ワークアイテム実行のエントリポイント
private void WorkItemEntry(object argument)
{
    string name = (string)argument;
    if (name.EndsWith("様") == true)
    {
        // 追加が競合しないように、コレクションをロックする
        lock (kingNames)
        {
            kingNames.Add(name);
        }
    }

    // 自分が最後なら通知
    if (Interlocked.Decrement(ref count) == 0)
    {
        final.Set();
    }
}

public IEnumerable<T> GetKingNames()
{
    List<string> nameList = new List<string>();

    // ...

    // ワークアイテムをキューに入れる
    foreach (string name in nameList)
    {
        Interlocked.Increment(ref count);
        ThreadPool.QueueUserWorkItem(WorkItemEntry, name);
    }

    // （キューに入れている間に終わってしまわないように、カウンタの初期値を1にしてあるので減算）
    if (Interlocked.Decrement(ref count) == 0)
    {
        final.Set();
    }

    // 全てのスレッドが終わるのを待つ
    final.WaitOne();
    return kingNames;
}

まず、第一にわかることは、「マルチスレッド対応」にするだけで面倒で不安な同期処理を大量に記述しなければならない事だ。この処理の肝は「EndsWith(“様”)」だけであるのに、付随コードの何とも多い事か。そして、これだけでもLINQで書く事がいかに強力であるかが分かる。

LINQで書く場合、「AsParallel()」で列挙子を修飾するだけだ。AsParallelメソッドは、指定された列挙子（nameList）をParallelQuery<T>クラスでラップする。LINQの他のメソッド同様、これだけではまだクエリは実行されていない。最後にkingNamesをforeachで列挙するまで、全く処理は行われていない。つまり、中間バッファは一切不要という点も重要だ。

元のデータが100万件、EndsWithで絞り込んでも50万件のデータがあるとすれば、判定しては新たなコレクション（中間バッファ）にデータを格納するのはためらわれる。また、列挙した時点で一気に処理を実行することで、CPUのキャッシュにコードが維持される可能性も高まる。おまけに.NETはJITコンパイラで動いているので尚更だ。

次に、レガシーコードで示した方法には、マルチスレッドを効率的に実行できない罠がある。それは、kingNamesに対してロックを行っている部分だ。この実装は、一回のワークアイテム実行に占めるロック時間が、相対的に長すぎる。そのため、複数のスレッドで同時実行されると、ロック競合が多量に発生する。結局その間は「シングルスレッド」と変わらないのだ。おまけにスレッドコンテキストの遷移に時間がかかってしまうので、シングルスレッド性能より落ちてしまう。

「既存コードのマルチスレッド化でパフォーマンス向上」なんて、生易しい事ではないのだ。

それがもっとよく分かるように、このレガシーコードを改良してみる。

// スレッドのエントリポイント
private void ThreadEntry(object argument)
{
    KeyValuePair<Queue<string>, List<string>> pair = (KeyValuePair<Queue<string>, List<string>>)argument;
    Queue<string> queue = pair.Key;
    List<string> localKingNames = pair.Value;

    while (true)
    {
        // キューから文字列を取り出す。最後なら抜けてスレッド終了
        string name = queue.Dequeue();
        if (name == null)
        {
            return;
        }
        if (name.EndsWith("様") == true)
        {
            // コレクションはスレッド固有なのでロック不要
            localKingNames.Add(name);
        }
    }
}

public IEnumerable<T> GetKingNames()
{
    List<string> nameList = new List<string>();

    // ...

    // スレッドに供給する文字列と、結果文字列を格納するコレクションをスレッド数分用意する
    List<KeyValuePair<Queue<string>, List<string>>> pairs = new List<KeyValuePair<Queue<string>, List<string>>>();
    for (int i = 0; i < Environment.ProcessorCount; i++)
    {
        pairs.Add(KeyValuePair<Queue<string>, List<string>>(
            new Queue<string>(), new List<string>());
    }

    // 事前にキューに入れる（スレッド毎に均等に）
    int index = 0;
    foreach (string name in nameList)
    {
        pairs[index].Key.Enqueue(name);
        index = (index + 1) % Environment.ProcessorCount;
    }

    // スレッドを生成して実行を開始する
    List<Thread> threads = new List<Thread>();
    for (int i = 0; i &lt; Environment.ProcessorCount; i++)
    {
        Thread thread = new Thread(ThreadEntry);
        threads.Add(thread);
        thread.Start(pairs[i]);
    }

    // スレッド群が終わるのを待つ
    List<string> kingNames = new List<string>();
    for (int i = 0; i < Environment.ProcessorCount; i++)
    {
        threads[i].Join();
        // 終わったスレッドから、結果を収集する
        kingNames.AddRange(pairs[i].Value);
    }
    return kingNames;
}

あーもう、書いている矢先から面倒で、記事自体無かったことにしようかと5回ぐらい思った :-) （そんな訳で、コンパイルして検証はしていない）

要するにこのコードは、ロックを行わなくて済むように、事前にスレッド毎にデータを分散し、スレッド毎に結果を格納し、その結果はメインスレッド側で収集する、という事をしている。これはマルチスレッドでパフォーマンスを向上させる定石のようなものだ（ロックを不要にする）。キューにデータを入れ直している時点でメモリを余分に使っているため、さらなる改良が必要だが、「もういいだろう」。それにこれ以上書きたくない。

つまり、こういう面倒なことを、ParallelQuery<T>クラスの内部でやってくれるという事だ。そして、現在のCPU事情と言えば、シングルスレッド性能は頭打ちで、マルチコア・SMTを推進している。コードを高速化させるためには、マルチスレッドに対応させるコーディングを行う必要があるが、同期処理は面倒かつバグを生みやすい。上記のような短いコードでさえ、書いただけでは正しいかどうか分からない。

この最適化手法を知っている人なら、これがAsParallelするだけで実現される、なおかつそれはコンパイラが何か怪しげなことをやっているのではなく、全てライブラリだけで実現されていると聞けば、カルチャーショックを受けるはずだ（受けなきゃおかしい）。

＃LINQのクエリ構文はコンパイラが解釈する。しかしParallelQuery<T>クラスは種も仕掛けもない、普通のライブラリだ。
＃その気になれば、だれでも同じものが作れる。もちろん、安全に実行出来るようにするには高度な技術が必要なので、「俺ParallelQuery<T>」は作らない方がいい。

さて、どのようなコードでも、LINQで書かなければならない訳ではない。例えば、LINQで列挙しながら、列挙中のコレクションを更新するという操作はNGだ。しかし、それはLINQを使わない場合でも同じ事だ（LINQで記述すると、あまりに簡便になるため、出来ない事があると欠点に思えてくるが、それは多分違うよ？）。

また、LINQは「常に構造が変化する要素」を扱うのが難しい。これは当たり前だ。列挙する要素がintになったりstringになったりする状況では、クエリが簡便に記述出来ない（そういう状況が、IEnumerable非ジェネリックインターフェイスを使った場合だ。もっとも、LINQのライブラリはIEnumerableに対応していない。擬似的にIEnumerable<object>で試せば分かる）。

これを以って、やはりLINQは中途半端と思うなら、実用的なコードをLINQで書いてみるべきだ。また、LINQを使うのに、SQL Serverにアクセスする必要などない。IEnumerable<T>インターフェイスを実装していれば、あらゆる要素に応用が可能だ。

「LINQが適している分野ではLINQで書け」

これに尽きる。そしてLINQの「後」でPLINQが生み出されたように、LINQの拡張性にも目を見張るものがある。次回に続く。