2013-11-18

通算３回目の参加・発表ということで大変お世話になっている 第4回 #渋谷java でお話してきました。5 分の LT では語れなかった内容が多々あるので、それらを盛り込んでエントリを残しておきます。

発表資料は以下です。

発表で使用する予定だったデモコードは komiya-atsushi/shibuya-java4 に置いておきました。

オブジェクト等価比較を怠けたくなった背景

事の発端

元々は SAStruts なとあるお仕事において、JSON を返却する Web API の Action クラスの各メソッドを JUnit でテストしたい、というのが事の発端でした。

このテストの本来の理想的な姿は、Tomcat などの AP サーバを経由して HTTP で実際に Web API を呼び出し、その結果のレスポンス の JSON が期待している内容と同一かどうかを比較する… というものでした。しかし、この構成を JUnit / S2JUnit4 で実施するにはなかなか難儀することが予想された（ぶっちゃけ面倒だった）ため、早々に Action クラスのメソッドを直接呼び出すことで得られる JSON 文字列を (デシリアライズして) アサーションする、という現実的な方針に切り替えました。

そういうわけで、Web API から返されるちょっと複雑なデータの JSON を Java のオブジェクトとして取り扱いつつ、それに対して期待している結果と等しいかどうかの等価比較 ( assertThat(actual, is(expected)); ) をすることが求められたわけですが… まあ Web API の戻り値として返すようなオブジェクトのクラスに Object#equals() がオーバーライド実装されていることなんてそうあるわけでもなく、ただひたすらにオブジェクトにプロパティ経由で値を参照して assertThat(actual.getHoge(), is(expected.getHoge()); する、みたいなテストコードの記述を強いられる残念な状況が生じたわけです（さすがに、さしみたんぽぽ作業をただひたすらに続けられるほど、僕はできているエンジニアではなかったので、2, 3 行試しに書いてみたところで見事に崩折れました）。

Object#equals() の実装

assertThat() の羅列が本当に羅列すぎて生きるのが辛いので、本来は equals() の実装は不要だけれども JUnit でのテストのために致し方なく本末転倒的にオーバーライドすることも念の為に考えてみました。

幸いにして、 Apache commons-lang の EqualsBuilder を使うと、比較的容易に equals() を実装することができます (commons-lang については こちらの資料 が参考になります)。特に、 EqualsBuilder#reflectionEquals() を使うと驚くほど簡単に equals() を実現できます。

しかし一方で、 EqualsBuilder を使って equals() を実装してアサーションを行うようにすると、アサーションに fail したときのメッセージが以下のように役立たずなメッセージになる、というデメリットが存在します。

java.lang.AssertionError: 
Expected: is <foo.bar.HogeBean@9a8d9b>
     but: was <foo.bar.HogeBean@22c6bb6c>

Matcher による解決の試み

Object#equals() を実装していないクラスのオブジェクトに対して等価比較なアサーションをしたい場合、 org.hamcrest.BaseMatcher クラスを継承実装するという手があります。この方法を利用すると、

  • 等価比較だけでなく、値の大小比較などのきめ細かいアサーションが可能になる。
  • fail したときの mismatch メッセージに不一致となった内容や各種コンテキスト情報などを載せることができ、fail メッセージからの不具合の原因追求が容易になる。
  • assertThat() まわりの記述がすっきり・シンプルになる。

というメリットを得ることができます。ただ、Web API のようにエンドポイントごとに返却されるオブジェクトが異なる場合などはエンドポイントの数だけクラスが実装されていることもあり、そのクラスの数だけ BaseMatcher クラスを継承実装するというのは現実的ではありません (そもそもの BaseMatcher の実装コストがかかる、というデメリットもあります)。

汎用的な等価比較用 Matcher を目指す

そういうわけで、「equals() を実装する」わけでもなく「個別 に Matcher を用意する」わけでもない方法で解決するアプローチとして、汎用的に利用できる等価比較用の Matcher である IsEquivalentTo を作成しました。

この Matcher を利用することで、

  • equals() の実装を必要とせず
  • もちろん独自 Matcher も実装不要で
  • assertThat() まわりのコードも比較的シンプルに保ち
  • 等価比較したくないプロパティ / フィールドも明示できる

テストコードの記述が可能になります！ （なる予定です！）

Matcher の汎用化、というわけで、個別に Matcher を実装したときと比べてきめ細かなアサーションは実現が難しくなりますが、等価比較できるところだけをこの汎用化 Matcher を利用して比較し、等価比較ではないアサーションは別途 assertThat() の羅列などで対処する、というアプローチもとれることでしょう。

技術的だったり細かい話

IsEquivalentTo の実装では、以下の工夫を盛り込みつつ、等価比較の汎用化を実現しています。

  • 再帰的なオブジェクトのトラバース ... オブジェクトを木構造なデータ構造と見立て、List / Map / 配列 / その他オブジェクト、の 4 種類ごとに等価比較の戦略を分けています。List / Map / 配列であれば、単純に保有しているオブジェクトに対して等価比較をするようにします。

  • オブジェクトの等価比較 ... Object#equals() をオーバーライド実装していないオブジェクトの場合、単純に equals() による等価比較をしてしまっては残念な結果になることは目に見えているので、以降に示す「プロパティの参照」「public フィールドの参照」を試すようにしています。一方で equals() をオーバーライド実装しているようであれば、その equals() を呼び出すようにします。

  • プロパティの参照 ... JavaBeans の規約に従って定義されているプロパティは、JavaBeans API の java.beans.PropertyDescriptor を利用して、getter メソッド経由で値を読み出すようにしています。

  • public フィールドの参照 ... 最近だと、JavaBeans の規約にあえて従わず、public にフィールドを定義してクラスの外にフィールドをさらけ出すような実装を見かけることも、実際にそのような実装をすることも多くなってきました (MessagePack が要求するクラスがまさにそのようなフィールド構成ですね）。そのため、public なフィールドについてはリフレクション API を利用して、プロパティの場合と同じようにその内部の値を取得・参照するようにしています。

  • 例外的に扱いしたいプロパティ / フィールドなどの指定 ... テスト実行した日時の情報など、不定な値がオブジェクトに含まれる場合は、その値を無視して等価比較したくなるものです。そのようなケースを考慮して、 JSONPath 的な記法で等価比較したくない要素を指定できるようにしています。

  • 比較的親切な fail 時の mismatch メッセージ ... JUnit のテストケースを作成する上で重要なことの一つに、テストケースが fail したときに「何が原因で fail したのか？」ができる限り把握できるメッセージを出力することがあります。 IsEquivalentTo の実装では、オブジェクト階層を意識して、JSONPath 的な表現で、「オブジェクトのどこがおかしいのか？」が把握可能なメッセージ出力ができます。

会場参加者への逆質問

今回話題にした等価比較の問題、他の人はどういうアプローチをとっているのかなー？ と気になったので、会場参加されている方々に 逆質問してみたところ、

  • equals() が実装されていることは確かに少ないけど、 toString() が実装されていることは結構あるので、文字列比較で済ませている。
  • 割り切ってテストはしない。

との回答をいただきました。不定な値がオブジェクトに紛れることがなければ、確かに toString() で比較できますね… 参考になります。

その他、感想などなど

  • build.xml と JSP はそろそろ滅んで欲しい！
  • Groovy / Grails に俄然興味が湧いてきた！
  • TokyoWebmining の新たな講師がゲットできそう！
  • 資格試験 (統計検定) の前日に発表予定を入れるのはもうやめよう…

最後に、会場提供の BizReach さん、そして主催の @seri_k さん、お疲れさまでした＆ありがとうございました！！

2013-09-03

３週間ぐらい前かつ発表前後は業務的に憤死しててもおかしくない時期ではありましたが、ありがたいことに主催者の @overlast さんから今回の発表オファーを頂いたしせっかくだから何か話そう、と心に決めて、いまの会社 でのお仕事でよく取り扱っているコサイン類似度や Jaccard 係数などのいわゆる「類似度計算」の時間／空間計算量的に効率的な処理を実現する方法についてお話してきました。

自分含めた発表内容の一覧は こちら を参照してください。

発表スライドはこちらです。

発表後に頂いた質問はこんな感じだったはず。寝不足ゆえの言語認識力がだいぶ低下した状態で受け答えしたので、質問／回答は超意訳になってます。悪しからず。

  • バスケット分析的な方法の計算量的な話

    • 購買ログなどからバスケット分析的な方法で類似度計算しようとすると、ユーザごとにログを集約しなければならないという追加処理が必要となるものの、計算量的にはあんまり問題になってない。
    • むしろ問題になるのはアイテムの数。アイテム数の２乗に応じて空間計算量が必要になってしまうため、アイテム数が多い場合にはこの方法は向かない。

  • レコメンド精度の面で、Jaccard 係数とかコサイン類似度ってどうなのよ？

    • ビジネス的には、類似度計算によって得られる精度よりもドメイン知識を使ったフィルタリングを良くする方が大事だと考えてる。
    • あと弊社の事情となってしまうが、精度のよい弊社独自の類似度計算のロジックは社外秘的な扱いとなっているためしゃべれない（ので、あえて精度の話は触れなかった）。

今回の発表にあたって b-bit Min-wise hashing を Java で実装してみましたが、精度・処理性能面の特性がまだ把握しきれていないので、もうちょっと追求してみたいですね。現状の実装は以下のとおりです。

https://gist.github.com/komiya-atsushi/6414548

あと、他の方の発表の感想と今回の反省です。

  • ダブル配列の実装テクニック的な話が熱かった。Java で trie を実装するときの参考になるのでとってもためになります。

  • 浮動小数点型数値の圧縮の話、昔のとあるお仕事で FPC を組み込もうかという検討をしたことがあって、そのときのことを思い出してちょっと感慨深いものがあった。整数圧縮の部分を改善する余地がまだあるとのことなので、maropu 先生の次回作に超期待してます！

  • 僕の発表、頂いた時間内でちゃんと発表しきれたのはよかったが、聴講者の反応を見てるとあまり興味ない or 説明が不足しているゆえに理解が追いつかない状態だったっぽい。魅力的な発表テーマ＆必要十分な説明を心がけたいですね。

  • 忙しいときこそ没頭してしまう「艦これ」を断つ勇気を僕にください…

2013-08-21

いままでは IntelliJ IDEA 上で JUnit によるユニットテストを実行していたのですが、Play! のバージョンを 2.1.1 から 2.1.3 にマイグレーションした際に IntelliJ 上での JUnit 実行ができなくなってしまい、解決法を探るのが面倒そうだったので play test で暫定対処しようとしたものの、こちらもこちらでいろいろと地雷が埋まっていたので解消・回避方法をメモしておくことにします。

その 1 : 'play clean' してから 'play test' する

とりあえず play test してその結果が以下の表示になる場合は、 play clean をしましょう。

[warn] 1 warning
[info] No tests to run for test:test

ここ に書かれているとおり、

You might try doing a play clean and then try play test again. I was getting the same "No tests to run" message until I did a clean.

ということで、play clean する必要があるそうです。play のコンソールを立ち上げた状態で clean タスクを実行しても思ったようにクリーンされないようなので、いったん play コンソールを抜けてから play clean するとよいです。

その 2 : junit-interface で work around する

上記の play clean をしてから play test をしても、(テストクラスは認識されるものの) それぞれのテストケースの実行結果が

[info] 0 tests, 0 failures, 0 errors

などと、個々のテストメソッドが実行されないことがあります (というかほぼ確実に実行されない？)。 そのような場合は、こちら に書かれているとおり、Build.scala に junit-interface への依存関係を追加すると問題を回避できます。

以下は Build.scala への追記例です。

  val appDependencies = Seq(
    // Add your project dependencies here,
    javaCore,
    javaJdbc,
    javaEbean,
    "play" %% "play-test" % play.core.PlayVersion.current % "test" exclude("com.novocode", "junit-interface"),
    "com.novocode" % "junit-interface" % "0.9" % "test"
  )

これでやっと play test でユニットテストが実行できるはず！

2013-07-28

Play 2.x で開発していたアプリケーションをステージング環境で play run したり、プロダクション環境で稼動させるために play dist したときに、以下のように、sbt.ResolveException の例外が発生した旨のログ出力がされて異常終了してしまったときの対処法をメモっておきます。

[warn] some of the dependencies were not recompiled properly, so classloader is not avaialable
[info] Updating {file:/path/to/play-app/}play-app...
[warn]  [NOT FOUND  ] org.slf4j#slf4j-api;1.6.6!slf4j-api.jar (1ms)                    
[warn] ==== local: tried
[warn]   /opt/playframework/repository/local/org.slf4j/slf4j-api/1.6.6/jars/slf4j-api.jar
[warn]  ::::::::::::::::::::::::::::::::::::::::::::::
[warn]  ::              FAILED DOWNLOADS            ::
[warn]  :: ^ see resolution messages for details  ^ ::
[warn]  ::::::::::::::::::::::::::::::::::::::::::::::
[warn]  :: org.slf4j#slf4j-api;1.6.6!slf4j-api.jar
[warn]  ::::::::::::::::::::::::::::::::::::::::::::::
sbt.ResolveException: download failed: org.slf4j#slf4j-api;1.6.6!slf4j-api.jar
        at sbt.IvyActions$.sbt$IvyActions$$resolve(IvyActions.scala:214)
            (略)
        at java.lang.Thread.run(Thread.java:724)
[error] (*:update) sbt.ResolveException: download failed: org.slf4j#slf4j-api;1.6.6!slf4j-api.jar

原因

Play プロジェクトを構築した時の Play framework のバージョンと、play run などをしようとしたときのバージョンが異なる場合にこの例外が発生するようです。

より具体的には、Play プロジェクトが利用する sbt-plugin のバージョンは、実行環境の Play のバージョンと合わせる必要がある、ということです。

実は play run を実行したときに、実行直後のログに赤文字で

This project uses Play 2.1.1!
Update the Play sbt-plugin version to 2.1.2 (usually in project/plugins.sbt)

と出力されていたりします。どうしても例外ログの方に真っ先に目が行ってしまいがちですが、ちゃんと Play framework は警告してくれています。

対処法

project/plugins.sbt に記載されている sbt-plugin のバージョンを、実行環境の Play のバージョンと合わせましょう。例えば、Play プロジェクトを作成したときの Play のバージョンが 2.1.1 であれば、

addSbtPlugin("play" % "sbt-plugin" % "2.1.1")

となっているかと思いますが、これを、Play 2.1.2 の環境で稼動させようとするなら

addSbtPlugin("play" % "sbt-plugin" % "2.1.2")

としましょう。

2013-06-29

渋谷java という、渋谷界隈で Java やってる人達が集って LT するイベントが開催される、ということで (僕が勤めている仕事先は拠点が代々木ではありますが) 参加＆お話をしてきました。

話した内容

元々は自社内で開催している「エンジニアリング勉強会」で展開した、Java アプリケーションを開発する際にパフォーマンス上注意すべき Tips を、外部向けに再構成してお話しました。ATND には「初心者向けレベルだとまだjavaを触って日が浅い主催者が泣いて喜びます。」と書いてあったので、初心者がやってしまいがちな、パフォーマンスを悪化させてしまうコーディングを中心にケーススタディとして挙げています (実際の参加者はガチ勢多数という感じでしたけどね！)。

再構成前の資料は５つぐらいのケーススタディを用いて 1 時間の説明をしていたのですが、今回は LT ということでページをバッサリと削って発表に臨みました。それでも、予定時間の 10 分より +6 分ぐらいオーバー、ということで時間内でしゃべりきるというのはやっぱり難しいなあ、と反省する次第です。

感想

以下、他の方のトークも含めた感想です。

  • Java の言語コミュニティなのに、ジャバ = エンタープライズ臭漂う残念めな言語、という認識の参加者が多いこと。
  • 仕事で Java 使っているからといっても Java が好き、というわけではない。Ruby が好きとか、仕方なく使っているとかそういう人もいる。
  • Play framework の認知度が高まってきている印象。Java で Play 2.x は微妙的な意見もあった (し、それを否定する気もさらさらない) けど、Java の世界でもっと流行ってくれるといいなー。
  • BizReach 社のセミナールーム (?)、オシャレですね！
  • 渋谷Java、今後も継続開催していただけることを期待してまーす！

2013-06-19

イラッとしたのでメモ。

概要

Linux など UNIX 系 OS に Play framework 本体をインストールし、${PLAY_HOME}/play コマンドで play clean compile stage などをした場合に、

java.io.FileNotFoundException: /path/to/play/framework/sbt/boot/sbt.boot.lock (Permission denied)
        at java.io.FileOutputStream.open(Native Method)

とか

java.io.FileNotFoundException: /path/to/play/repository/.sbt.ivy.lock (許可がありません)
        at java.io.FileOutputStream.open(Native Method)

などの Java の IOException が発生してしまうことがある件への暫定対処です。

原因

そもそも何でこの例外が発生するのかというと、Play framework 本体をインストールした際のユーザ (所有者) であったりパーミッションの設定が厳しかったりすることが原因となり、上記した類のロックファイルの作成や書き込みができないことによります。

※ play コマンドを実行したときに、${PLAY_HOME} ディレクトリ以下に書き込みをする Play framework もどうかと思いますがね…

(暫定) 対処法

本当はもうちょっとスマートな方法があるんじゃないか… と思ったのですが何かと面倒そうなので、

chmod -R go+wx ${PLAY_HOME}/framework/sbt/boot
chmod -R go+wx ${PLAY_HOME}/repository

こんな感じで解決するのがいいでしょう。

2013.8.21 追記

よくよく Play! 2.x の公式ドキュメント http://www.playframework.com/documentation/2.1.3/Installing を読んでみると、

Download the latest Play binary package (take the latest official version) and extract the archive to a location where you have both read and write access. (Running play writes some files to directories within the archive, so don’t install to /opt, /usr/local or anywhere else you’d need special permission to write to.)
と書かれていました。つまり「(ファイル／ディレクトリ書き込みなどをするから) /opt, /usr/local にはインストールするなボケ！」ということですね。

2013-06-03

主催者の方に発表内容をかっちりと決めずになんとなく「発表したいです！」と参加表明してみたものの、いざ開催日が近づくと「やばいな発表できるネタができない…」という状態に陥ってちょっとお腹痛くなる思いをしましたが、何とか発表し切れてホッと一息ついたのでエントリ起こしておきます。

Jubatus って何？

PFI & NTT によって共同開発されている、「機械学習の各種タスクをオンライン (かつ分散) で処理できるようにする」ことを目的としたプロダクトです。「機械学習」と一口に言ってもいろいろありますが、例えば「クラス分類」とか「回帰」とか「レコメンド」とかが Jubatus ではできるようですね。

詳しくは 公式 をご覧ください。

お話したこと

「Java で楽して Jubatus したい！」というタイトルで、Java から Jubatus を利用する際にお世話になる Jubatus Java Client に関してお話をしました。

他の方々の発表は軒並み「Jubatus を使って◯◯しました」というとっても実践的な内容、というか ガチュアルな内容も盛りだくさんで、Jubatus を使わないネタで発表をする身としては肩身が狭いことこの上ありませんでしたが、まあ多少盛り上がった (?) ようでしたのでよしとしましょう…

発表内容は以下のスライドをご覧いただくとして、ざっくり要約すると

  • Java から Jubatus を使ってみようかなー
  • Jubatus Java Client を使う必要があるらしいけど… こ、これを使うのははちょっと辛いな…
  • よし、楽に使えるラッパーライブラリを作ろう → Jubaba (ゆばーば) 爆誕！

こんな感じです。

 

Jubaba (ゆばーば)

そういうわけで、Java から Jubatus をカジュアルに利用するためのラッパーライブラリ、 Jubaba プロトタイプ版を作り始めました！

まだまだインタフェースも試行錯誤を重ねていて流動的だったり、多値分類 (Classifier) しかサポートできていないので完成には程遠い状態ですが、ちょっとずつ開発を進めていく予定です。ご要望、ご意見等ありましたらご連絡いただけると幸いです。あ、pull request くれてもよかですよ！！

その他・感想

発表機会をくださいました @unnonouno さんこと海野さん、Jubatus 関係者の方々、そして拙い発表を忍耐強く聞いてくださった会場参加者の方々、ありがとうございました！

  • Jubatus 開発チームの、Java に対する如何ともし難い黒いオーラが滲み出ているところを深くえぐってしまった (※後述) 感がありますねこの発表は… ははは。ごめんなさい…
    • 懇親会のときの、海野先生のコード生成裏話 LT は涙なしには聞けなかったです、はい。
  • Java で機械学習している人、前からわかっていたことですが少ないですねー。Java エンジニアとしては、もっと盛り上げていきたいなあ。
    • 今回の開催でも、他の参加者はみんな Python だったり Ruby を使ってるし、それらとの対比で Java での煩わしさを引き合いに出されるし… 特徴抽出を試行錯誤するなら LL な言語でやるのが定石ですね。
  • 異常検知、熱いですね！ このみなさんの注目度は意外だったー。

そんなわけで、また機会がありましたらお邪魔させてください＆ネタがありましたら発表させてください！ (今度はガチュアルな話をしたい…)

※補足

えぐってはいけないものをえぐってしまってごめんなさいごめんなさいごめんなさい…

2013-05-20

Java 7 になって String#split() の実装が変更されたことに今更ながら気付いたので、Pattern#split() や Java 6 との性能の比較をしてみたメモです。

Java 6 以前の文字列分割処理

古くから Java を触っているエンジニアであればみな当然知っていることだと思いますが、 TSV ファイルを Java のプログラムで読み込んで処理をするときなど、特定のデリミタで区切られた文字列を個々の要素に分割するときは String#split() を利用せず、事前にデリミタに対する java.util.regex.Pattern オブジェクトを生成しておき、そのオブジェクトを使い回す形で Pattern#split() を利用した方が処理効率 (処理時間) がよくなります。

これは、 String#split() の実装が実質的に Pattern.compile(delimiter).split(str) と等価であることによります。つまり String#split() メソッドは、そのメソッドの呼び出し毎に Pattern オブジェクトを生成するため、オブジェクト生成のオーバーヘッド (と GC 発生頻度の増加) によって処理性能が悪化する、ということです。

Java 7 での String#split() 実装

一方で、Java 7 ではこの String#split() に手が加えられ、Java 6 以前と少し事情が異なっています。

public String[] split(String regex, int limit) {
    /* fastpath if the regex is a
     (1)one-char String and this character is not one of the
        RegEx's meta characters ".$|()[{^?*+\\", or
     (2)two-char String and the first char is the backslash and
        the second is not the ascii digit or ascii letter.
     */

上記は Oracle 社の JDK 1.7 src.zip に含まれる String.java より拝借してきた String#split() のメソッド冒頭のコメントです。

この英語をざっくり翻訳すると『指定された正規表現が次の 2 つのどちらか

  • 1 文字で構成されていて、正規表現におけるメタ文字 ".$|()[{^?*+\\" のいずれでもない
  • 2 文字で構成されていて 1 文字目がバックスラッシュ、2 文字目が 英数字以外 である

に合致する場合に、より手短に済む処理をする』となります。

これはつまり「実質的に特定 1 文字の正規表現として取り扱える場合は、(Pattern#split()) より高速な文字列分割処理できる」ことを意味しています。事実、上記コメント以降の String#split() 実装を見てもらえるとわかりますが、 Pattern オブジェクトを生成することなく、 String#indexOf() を用いた単純な文字探索ベースでの文字列分割を実現しています。

ところで Java エンジニアとしては、この Java 7 での変更により、どの程度性能に影響が現れるのかが気になるところです。そういうわけで、

  • Java 6 での String#split() と Pattern#split()
  • Java 7 での String#split() と Pattern#split()

それぞれの処理性能を比較してみることにしました。

文字列分割処理の性能比較

性能比較は こちらのデモプログラム を用いて実施しました。

結果は こちらの Google ドキュメント にまとめました。

結果を見ると明らかですが、Java 7 で特定の 1 文字を現す正規表現 (" ") を指定した場合は String#split() の方が Pattern#split() よりも 2 倍以上速くなっています。一方で、複数種類の文字に一致する正規表現 ("\s") を指定した場合は、Java 6 と同じ傾向になっていることがわかります。

Google ドキュメントには正規表現を複雑にしたときの性能比較と、ガベージコレクションの発生回数も参考までに掲載しておきました。この結果より、

  • Java 6 → Java 7 では、 Pattern クラスの各種処理性能が若干劣化している？
  • 正規表現を複雑にすると String#split() 側の性能が劣化する (＝ Pattern.compile() の処理のオーバーヘッドが効いてくる)
  • 選択の正規表現は (Pattern.compile() もそうだけど) マッチング処理がとにかく重い

ということが窺えますね。

まとめ

今回のまとめは以下のとおり。

  • Java 7 以降なら、TSV ファイルの 1 行を分割するなど、特定の 1 文字で構成されたデリミタを指定するときは迷わず String#split() しよう
  • Java 6、もしくは複数文字や複雑な正規表現で分割したい場合は、 Pattern オブジェクトを事前に定数的に生成しておき、使いまわして Pattern#split() しよう

2013-03-29

巷では「ArrayBlockingQueue よりも LinkedBlockingQueue の方がスループット性能がいいよ」なんてまことしやかに言われているけど、どうにも気になったので検証してみたら、実は ArrayBlockingQueue の方が性能いいんじゃない？ という結論に至った話です。

Producer-Consumer デザインパターンと BlockingQueue

Java で Producer-Consumer デザインパターン を実現するときによくお世話になる BlockingQueue インタフェース。このインタフェースには ArrayBlockingQueue クラス と LinkedBlockingQueue クラス の二つの実装が標準 API として提供されています。

高い処理性能を要求されるプログラムを Java で書こうとしたときに、CPU のすべてのコアをフル稼動させることを狙って Producer-Consumer パターンによって処理フローをパイプライン的に構成することがあります。そのときにいつも気になっていたのが、「ArrayBlockingQueue と LinkedBlockingQueue、果たしてどちらを利用した方がスループットが高くなるのだろうか？」ということ。

この疑問に対して、海外でも 議論 されていたり、検証 されていたりされているようで、それらの 結論 としては概ね「LinkedBlockingQueue の方が ArrayBlockingQueue よりも高スループットだよ」というものになっています。

しかし、ArrayBlockingQueue と LinkedBlockingQueue の双方の実装やデータ構造の特性を考えると「LinkedBlockingQueue の方が高スループット」という結論がにわかに信じ難かったので、実際に検証をしてみることにしました。

双方のデータ構造と実装の特性

検証を始める前にまず、それぞれのデータ構造および実装の特性を確認してみることにします。参考にした実装は Oracle の JDK 1.7 (update 17) です。

ArrayBlockingQueue クラス

  • 配列をベースとしたキュー実装で、配列をリングバッファとして扱います。
    • エンキュー (add() / offer() / put()) 操作、デキュー (remove() / poll() / take()) 操作をする配列上のインデックスを、それぞれ別々に保持しています (putIndex フィールドと takeIndex フィールド)。
  • キューの大きさは固定長で、その大きさを超える要素数を保持することはできません。
  • エンキュー操作において、余計なオブジェクトが生成されることはありません。
  • エンキュー／デキュー操作では、一つのロックオブジェクト (lock フィールドの ReentrantLock オブジェクト) を共用して排他制御をします。
    • エンキューとデキュー操作のメソッド呼び出しが重なると、一方の処理にてロック解除待ちが生じてしまいます。

LinkedBlockingQueue クラス

  • 片方向の連結リストをベースとしたキュー実装です。
    • 要素の数に応じて、リストが伸長・縮退します。
  • 連結リストの先頭 (head フィールド) より要素をデキューし、末尾 (last フィールド) に要素をエンキューします。
  • 保持できる要素数は最大で Integer.MAX_VALUE になります。
    • コンストラクタで capacity を指定することで、保持する要素数を制限することもできます。
  • 要素のエンキュー操作ごとに、連結リストの Node オブジェクトの生成操作が発生します。
    • 1 つの要素につき 16 バイトほどのヒープを余計に消費します。
  • エンキュー／デキュー操作の排他制御はそれぞれ別々のロックオブジェクト (putLock フィールド、takeLock フィールド) を利用します。
    • エンキューとデキュー操作のメソッド呼び出しが重なったとしても、ロック解除待ちは発生せず並列に処理することができます。

これら上記の双方の特性を比較すると、

  • ArrayBlockingQueue は処理が単純な分、エンキュー／デキュー操作の処理コストが小さく、一方で LinkedBlockingQueue はオブジェクト生成が必要となるために特にエンキュー操作の処理コストが高い。
  • ArrayBlockingQueue は、エンキュー／デキュー操作においてロックオブジェクトを共有するために Producer / Consumer の並列性が低くなるが、LinkedBlockingQueue は別々のロックオブジェクトが用意されているため、Producer / Consumer の並列性が高まる。

と言うことができそうです。 LinkedBlockingQueue の方がスループットが高い、というのは後者の並列性が根拠になっていると思われますね。

性能検証する

続いて、実際に両者の BlockingQueue 実装を利用したプログラムを作成し、各種性能を測定してみました。

測定方法

検証用プログラム を用いて、エンキュー操作、デキュー操作を独立して 1,600 万回ほど行ったときの処理時間、およびエンキュー／デキュー操作を複数の別スレッド (Producer / Consumer) で同時並列に 1,600 万回実施したときのスループットを ArrayBlockingQueue, LinkedBlockingQueue それぞれの実装ごとに測定してみました。

また測定を進めていく上で、Java VM の 32 bit と 64 bit の違いや、Java コンパイラ (JDK / Eclipse)、ハードウェア・OS (Windows / Mac) の違いが性能に影響を与えることが明らかになったため、これらの構成の組み合わせも合わせて検証してみることにしました。

検証環境

  • ハードウェア・OS
    • Windows PC
      • Windows 7 (64 bit)
      • Core i5-3450 (3.10GHz)
      • 8GB Memory
    • Mac
      • Mac OS X 10.8.2
      • 1.7GHz Core i5-3317U
      • 4GB Memory
  • Java
    • Java VM (オプション : Xms1200m)
      • Java 7 Update 17 (32 bit & 64 bit)
    • Java コンパイラ
      • JDK 1.7 Update 17
      • Eclipse Compiler for Java 3.8.2

測定項目

  • エンキュー／デキュー操作を行う各種メソッドの呼び出しにかかる時間 [ミリ秒]
    • エンキュー
      • add()
      • offer()
      • put()
    • デキュー
      • remove()
      • poll()
      • take()
  • スループット [メッセージ/秒]
    • Producer x 1 スレッド, Consumer x 1 スレッド
    • Producer x 1 スレッド, Consumer x 2 スレッド
    • Producer x 2 スレッド, Consumer x 1 スレッド
    • Producer x 2 スレッド, Consumer x 2 スレッド

測定結果と考察

上記の内容で測定した結果を Google ドキュメントで公開 しています。数値に対するカラースケールは行（横一列）のグループに対して設定されており、緑色が良い性能であることを、黄色がほどほどの性能を、赤色が性能が悪いことを示します。

Java VM (64 bit / 32 bit) の違い

さてこの結果を見てすぐに分かることは、ArrayBlockingQueue と LinkedBlockingQueue のどちらについても、32 bit Java VM よりも 64 bit の方が性能がよい、ということになりますね。メソッド単体の呼び出し性能もスループットも、どちらも下は 1.5x から上は 4x ぐらいまでの性能が 64 bit VM では出ています。

メソッドの呼び出し性能に着目すると、32 bit VM ではメソッド間で性能差が大きく開きバラつきがあり、ArrayBlockingQueue も LinkedBlockingQueue もそれぞれの性能特徴がよく分かる結果となっています。一方で 64 bit VM では、メソッド間の性能差は 32 bit ほどの開きは見られず、安定した性能が出せていることがうかがえます。

スループットについては、64 bit VM を使うことで ArrayBlockingQueue の性能が 32 bit VM のときより大幅に性能向上することが見て取れます。LinkedBlockingQueue も 64 bit VM による性能劣化はなく、ArrayBlockingQueue ほどではないものの多少の性能向上がうかがえます。

Java VM の違いにおいて ArrayBlockingQueue と LinkedBlockingQueue の結果を比較すると、

  • 32 bit VM では LinkedBlockingQueue の方が性能がよい。
  • 64 bit VM では ArrayBlockingQueue の方が性能がよい。

と言えるでしょう。

Java コンパイラ (JDK / Eclipse) の違い

コンパイラの違いについては、今回の測定結果では優劣が明確になるほどの性能差は出ませんでした。

ハードウェア・OS の違い

Mac の場合、ArrayBlockingQueue と比べて LinkedBlockingQueue の性能が全体的に悪いことがわかります。メソッドの呼び出しについては、特にエンキュー操作の性能が極端に悪いですね。

スループットも、エンキュー操作メソッドの性能に引きづられてか、LinkedBlockingQueue の性能は芳しくありません。エンキュー操作が競合しやすい Producer x 2 の構成での落ち込みが大きいですね。

Mac では、 ArrayBlockingQueue 択一 と言ってしまっていいと思います。

まとめ

ArrayBlockingQueue を使うべきか、それとも LinkedBlockingQueue を使うべきかの判断は Java VM 次第、すなわち

  • (Mac を含む) 64 bit の Java VM を利用するなら ArrayBlockingQueue がよい。
  • 32 bit の Java VM なら LinkedBlockingQueue がよい。

と言ってしまっていいでしょう。ただ今後のことを考えれば 64 bit VM の利用が多くなっていくと考えられるため、開発時点では 32 bit の VM 利用を想定していても、ArrayBlockingQueue を採用しておくのが無難じゃないかと思います。はい。

だいじなこと

今回は Windows と Mac とで性能検証をしてきたのですが、実際に Java アプリが利用される環境は Linux など Unix 系の OS が多いかと思います。今回の検証でなんとなく傾向はつかめた (64 bit なら ArrayBlockingQueue) のですが、これがそのまま Linux でも通じるかどうかはまた別の話、つまりは要検証、ということです。

2013-02-07

ざっくり要約すると、お好きなテキストエディタとブラウザさえあれば OK な、ちょっと便利な Markdown リアルタイムレンダリング＆プレビューツールを 車輪 の 再発明 の再発明したよ、ということです。

Markdown のリアルタイムプレビューの現状

動機は言わずもがなですが改めて書くと、github で公開するプロダクトの README など、Markdown のフォーマットでドキュメントを書く機会がここ最近増えてきています。ですが、Markdown の書式に慣れないうちは、HTML レンダリング結果をブラウザで確認しながら編集したいもので、実際にプレビューを確認しながら書くのとそうでないのとでは生産性に結構な差が生じることは、経験者の多くの方々に頷いてもらえるかと思います。

このような欲求があれば当然、それを解決するツールが生み出されるのが世の常なわけでして、すでに Markdown のリアルタイムレンダリングツールの類はいくつか世に出ています。

Showdown は、外部サービスを利用せず JS で実装された Markdown レンダリングエンジンを利用してプレビューを実現するツールで、ブラウザだけで完結するのが強み（でもあり弱みでもある）となっています。一方で Jxck 先生の markup とたむたむ先生の rdoc-view は、いずれもローカル環境に AP サーバを立てて、そのサーバ経由でローカルのファイルシステム上にある Markdown ファイルのプレビューを提供します。この方式の強みはなんといっても、「好きなエディタを使って Markdown の編集ができる」ということに尽きます。

markup にしても rdoc-view にしても、利用するために必要となる実行コマンドは２つだけですが、その前に Node.js の環境やら Ruby の環境やらを整えなくてはいけないという、私みたいなものぐさ人間にはそれなりの高さのハードルがあります。

Markdown Previewer

そんなわけで、「自分の好きなエディタ」を利用できて、かつ「面倒なインストール作業も要らない」Markdown リアルタイムプレビューのサービス (?) を作りました。

Markdown Previewer

利用方法は「これでもか！」というぐらいに簡単（なはず）で、上記サイトを表示して、"Drop your markdown file here" と大きな文字で表示されている領域にローカルにある Markdown ファイルをドラッグ＆ドロップするだけです。後はお好きなエディタでそのファイルを編集するだけ。編集内容を保存すると、その内容がすぐにプレビューに反映されます。

お手軽リアルタイムプレビューを実現している仕組み

エンジニアの方であれば上記の説明から仕組みが簡単に想像できちゃうかと思いますが、JS の File API を利用することで、ローカルの Markdown ファイルの読み込み＆更新検知を実現し、また先の Showdown を利用して Markdown のレンダリングプレビューを実現しています。オリジナルなコードは高々数十行です。

詳しくは markdown-previewer の github リポジトリをご覧ください。

制限事項と今後の展開

今回は自分だけが使えればいいや、ということでブラウザ/OS は Google Chrome 24 (Mac OS X / Windows) のみをターゲットとしています。(2013.2.8 追記) Firefox (Mac/Ubuntu/Windows), Safari (Mac), Chrome (Ubuntu) に追加対応しました。 ですが、できるならば Firefox や Safari などでも使えるように対応していく予定でいます (IE は知らん)。

また、Markdown だけではなくて RDoc などの他の記法にも対応していく予定でいます。

登録: 投稿 (Atom)