Making of Parallel LINQ for Java

この記事は、新感覚アドベントカレンダー、LL/ML Advent Calendar 2012 (#LLAdventJP) の12月12日分トラック1です。

おそしろいことに、気づけば投稿者として登録されていました。唯一の救いは、タイトルに「MとL」または「Lが2つ以上」入っていれば何を書いてもいいことです。

Making of ParaLLeL LINQ for Java
ごらんください、LLにいたっては2つも入っています。

ざっくりしたLINQの紹介

LINQは、配列やデータベースのような何らかの「データの集まり」に対する、とても便利な道具です。数多くの便利な問い合わせ演算子を組み合わせて、どんなデータの集まりでも同じように操作することができます。

var top5 = list.Where(o => 東海三県.Contains(o.住所))
               .OrderByDescending(o => o.こわさ)
               .Select(o => o.名前)
               .Take(5);

すっきりと書けますね。

対象がデータベースの場合、内部ではSQLが実行され、その結果を取得できます（SelectやWhereなど、演算子がSQLを模していることにお気づきでしょうか？）。つまり、プログラミングでよく扱うデータ構造とRDBの区別をあまり意識することなく扱えます。

問い合わせ演算子を多数組み合わせても、できるだけ効率よく処理されるように実装されています。ループ回数が必要最小限になるようなもの…と思うとラクでしょう（上の例だと、並び替え演算子が入っているため、全要素が1回は列挙されるのですが）。

さらには、終わりがないかもしれないデータであっても、演算子の順序をあまり意識せずに扱うことができます（例えば、フィボナッチ数列やTwitterのタイムラインなど）。

var sum = list.Where(o => 東海三県.Contains(o.住所) 
              .Select(o => o.こわさ)
              .Take(10)
              .Sum();

この例だと、仮に元のデータ（list）が1億個あるいは無限だとしても、条件（Where）を満たす最初の10要素が取得できた時点で、それ以上の列挙は行われません。効率的です。

これらの興味深い性質は、遅延実行と怠惰評価によるものです。これをうっかり遅延評価というと、こわい人たちからマサカリやスリケンが飛んでくるそうなので、気をつけましょう。

LINQについてさらに詳しく知りたい方は、neue先生の入門記事とか、このあたりをオススメします。

LINQをどこでも使いたい: 独自実装LINQたち

LINQは、１度覚えたら、プログラミングの道具箱に常に入れておきたい道具の１つです。このすばらしい道具は、C#、F#、Visual Basicなどの言語向けに、LINQの開発元であるMicrosoftから提供されています。

このすばらしい道具を、自分が好きな……あるいは仕事の都合で使わるを得ない……プログラミング言語でも使えるようにがんばっている人たちがいます。LINQに魅了されたプログラマたち…通称LINQ星人です。

“[Language Name Here] LINQ”などと検索すると、そんな独自実装がたくさん見つかります。主だった言語でいえば、

neueccさんの JavaScript版linq.js

私はこのlinq.jsでLINQを知り、感銘を受けました。

yharaさんの Ruby版enumerable-lazy

Ruby 2.0に取り込まれるそうですね。

RyujiSamejimaさんの Objective-C版Linq

Objective-C Advent Calendar 2012で紹介されました。どうみてもネタかぶりです。本当に（略）。

LINQをJavaでも使いたい

嬉しいことに、来年2013年にリリースされる Java8 には、LINQの影響を受けたであろう機能が標準に組み込まれます。(この機能、今のところ名前がないようですが、Stream Operatorsとかなんとか、はっきりした名前が欲しいところです)

悲しいことに、お仕事では最新のJavaが使えるとは限りません。

しかし、心配することはありません。ScalaやGroovyを使いましょう。Java8未満でも使える、LINQの独自実装（またはLINQとよく似た使い方ができるライブラリ）が、既に多く存在します。

• https://code.google.com/p/guava-libraries/
• https://code.google.com/p/lambdaj/
• https://code.google.com/p/totallylazy/
• https://code.google.com/p/reactive4java/
• https://github.com/goldmansachs/gs-collections/
• https://github.com/SamirTalwar/Streams
• https://github.com/dolbz/JEnumerable
• などなど

機能の充実具合、開発の活発さ、ライセンス、命名ルールなどの好みに合わせて選ぶとよいでしょう。

どうせなら作ってみたい（ようやく本題）

ここまでは長い前置きです！

Java用LINQにも既にいろいろ実装があるので、何かひねりを加えようと思いました。そこで、並列実行できるLINQ（Parallel LINQ）を、Java用に実装してみました。できあがったものが https://github.com/exoego/Queen です。

ライブラリ名Queenの名付け親（ゴッドファーザー）は、@mzpさんか@bleisさんのどちらかです（忘れました）。その節は、ありがとうございました。由来は、某作品のキャラクタ通称「女帝」です。いちおう、Queenも女帝と訳せるそうですよ。

Q. なぜ車輪の再発明をするのか？

A. それは私がJavaとLINQを勉強するためです！　あと、他の実装が私が感銘をうけたlinq.jsほど演算子が充実していなかったからです！

並列クエリを使ってみる

さて、Queenの並列クエリを実際に使ってみましょう。

final List<Integer> evenList = range(1, 100)
    .asParallel()
    .map((Func1) (arg) -> {
        return arg * 2;
    }).toList();

1から100までの自然数のシーケンスをもとに、各要素を並列に標準出力に出力し、単純に2倍し、そこからリストを生成しています。mapの中にある見慣れないラムダ式は、IntelliJ IDEA 12によるもので、実際はJava6のごく普通の匿名クラスです。

1 33 2 3 34 35 36 37 38 39 40 41 42 65 66 67 68 69 70 71 72
73 4 74 43 97 44 75 5 76 45 98 46 77 6 78 47 99 48 49 50 51
52 53 54 79 7 80 55 100 56 57 58 81 8 82 59 83 9 84 60 85
10 86 61 87 11 12 88 89 90 91 92 93 94 95 96 62 13 63 14 64
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 

うまくいきました！

実際は、二倍するなどという単純で十分に速い処理を並列にすべきではありません。並列実行するための余計な作業（オーバーヘッド）のほうが大きくなるため、かえって速度は悪化してしまいます。

では、どれくらいが分岐点なのか、私の環境で調べてみました。測定方法については今回は詳細を省きます。

次のグラフは、シーケンスの要素数（データ量）と１要素の処理時間を変化させ、直列実行に対して並列実行の速度がどれくらい変化したかを測定したものです。Y軸の1より上は並列のほうが速く、下は並列にするとむしろ遅くなったことを意味します。

現在の実装と私の環境においては、要素数が100を超えるなら、処理時間が10,000ナノ秒（0.00001秒）以上の処理を並列にすると、速度ではメリットがあるようです。

要素数が3000を超えるとグラフの傾向が変化したり、処理時間が1,000,000ナノ秒で一様に落ち込みが見られます。これらの原因はまだ良くわかっていません。実装を改善するヒントかもしれませんので、今後分析したりしなかったりします。

同じデータを別の視点からも見てみましょう。今度はヒートマップ分析です。こうすると、要素数＆処理時間の組み合わせで向上するかどうかが分かりやすくなりました。

向上率が４で打ち止めになっているのは、私のPCが実行できるスレッドの数が最大4だからです。つまり、使えるスレッドをフルに活用できているということです。良かったです。

なお、Java8のStream なんちゃらでは、このような並列実行できるストリーム処理も導入されるそうです。労力が水の泡になってしまいました。ですが、まだまだ現役のJava5、6、7でも使おうと思えば使えるようになったので、良かったです。

むすび

私家版 Parallel LINQ for Javaとして Queen をステマ紹介しました。残念ながら、並列実行できるクエリは filter(もといWhere)、map(もといSelect)、fold(もといAggregate)の３つしかまだ実装できていません。これから徐々に実装を進めていく予定です。

• LINQは、プログラミングの道具箱に常に入れておきたいすばらしい道具の１つです。
• Java5〜Java7でも、LINQ to Objectsっぽく並列実行できるストリーム処理ライブラリを作ってみました。
• 実装の解説については、力尽きて書けませんでした…。そのうち書きます。