読者です 読者をやめる 読者になる 読者になる

"Java SE 7 リリース記念 特別イベント"懇親会LTでのGParsのFork/Joinについての宿題の解答

java groovy

最後が若干投げやりですが、やっとまとまりました。

はじめに

先週の7/7(木)に"Java SE 7 リリース記念 特別イベント"の懇親会でLTをしてきました。

"Java7のその機能Groovyには既にありますが何か?"という釣りサブタイトルがついてますが、よくよく読むと...

  • Anything in Switch
    • これはGroovyすごいでしょーという自慢話でOk
  • Lambda/Closure
    • これもGroovyのクロージャ便利だよーという自慢話でOk
  • try-with-resouces/Loan Pattern
    • ま、クロージャがあったらこうなるよねという話だから、自慢話系ということになるかな

この辺までは自慢していい話かとは思いますが、こっから怪しくて

  • Diamond/Generics
    • オプショナルタイピングとしての割り切りの話であって、決してGroovyの方が良いよね、という話ではない
  • Fork/Join
    • GParsは結局Fork/Join Frameworkの実装(jsr166y-xxxxx.jar)を裏で使ってるのでGroovyの方が進んでる、という話ではない

ということで、ちょっとフェアじゃないというかまあ懇親会だしLTだし「ま、いいか」的なノリでどーもすいませんでした。

GParsのFork/Joinサンプルの課題

それはそれとして、資料のP.21とP.22でparalell処理のサンプルとしてよくあるフィボナッチ数を算出する以下のようなコードを示してました。

Java7のFork/Join Frameworkのサンプル
import java.util.concurrent.*;

public class Fibonacci extends RecursiveTask<Integer> {
   final int n;
   public Fibonacci(int n) { this.n = n; }
   public Integer compute() {
     if (n <= 1)
        return n;
     Fibonacci f1 = new Fibonacci(n - 1);
     f1.fork();
     Fibonacci f2 = new Fibonacci(n - 2);
     return f2.compute() + f1.join(); // .....[1]f2は直接同一スレッドでcompute()を呼んでる
   }
}
GroovyのGPars0.11のサンプル*1
import static groovyx.gpars.GParsPool.*

def fibo(num) {
    withPool {
        runForkJoin(num) { n ->
            switch (n) {
                case 0..1:
                    return n
                default:
                    forkOffChild(n - 1)
                    forkOffChild(n - 2) // .....[2]これが問題! 「え、それもフォークするの!?」
                    childrenResults.sum()
            }
        }
    }
}
assert fibo(10) == 55
assert fibo(20) == 6765

発表中にすかさずid:skrbさんに突っ込まれたんですけど、これforkしすぎで無駄にスレッドを使っているという問題があるんですね。
[2]の部分が問題の部分です。

Java7のRecursiveTaskの方は、(n - 2)の方をカレントスレッド内でcomputeしていて、(n - 1)だけforkしてます。それに対して、GParsのサンプルでは(n - 1)も(n - 2)も両方ともforkしてます。カレントスレッドは単にfork×2をした後、joinで待ち受けるだけの暇なスレッドになってます。parallel効果である程度速くなるかもしれないけど、まあ、RecursiveTaskと比べると無駄が多いよね、という感じ。

で、「GParsは悪くないんだ!オレの、オレの書き方が悪いだけなんだッ!」と謝罪と賠償をしてLTは乗り切ったのですが、週明け*2に色々調査してみたら、驚愕の事実が!!

GPars 0.11では、あの記述が限界だった!!!

解決編

色々とあがいて、GPars 0.11のAPIをさぐったり、むりやりClosureのcallで再帰呼出しようとしたりしたのですが、どれも全然だめでした。
あきらめかけたそのとき、最新のGPars 0.12のユーザガイドを見てみると...

Fork / Join

...(snip)...
The runChildDirectly() method allowing to mix asynchronous and synchronous child task execution

http://gpars.org/0.12/guide/guide/single.html

ちょw待てwwwww


GPars 0.12 でforkせずに直接サブタスクを実行するためのrunChildDirectly()が追加されてました!なんと!


4月にリリースされた最新のGroovy1.8.0にバンドルされているGParsは0.11なので、ちょっと一手間かかりますが、$GROOVY_HOME/lib配下にあるgpars-0.11.jarをどっかに避けてから、以下のようにGPars 0.12を@Grabで指定しましょう。いつも通りGrapeがGPars 0.12をダウンロードしてクラスパスに通してくれるので、そのままrunChildDirectlyを使うことができます。

GroovyのGPars0.12のサンプル
@Grab('org.codehaus.gpars:gpars:0.12')
import static groovyx.gpars.GParsPool.*

def fibo2(num) {
    withPool { pool ->
        runForkJoin(num) { n ->
            switch (n) {
                case 0..1:
                    return n
                default:
                    forkOffChild(n - 1)
                    return runChildDirectly(n - 2) + childrenResults.sum() // .....[3]
            }
        }
    }
}
assert fibo2(10) == 55
assert fibo2(20) == 6765

Java7のRecursiveTaskのサンプルコードとほぼ同じ構造になりましたね!

で、効率はどうなのよ?

で、結局forkOffChild×2のときと、forkOffChild+runChildDirectlyでは、実効効率とかどうなんですかね、ってことで、GBenchという素敵なツール*3を使ってすごくざっくりと計ってみました。

import gbench.*

def benchmarks = new BenchmarkBuilder().run(idling:5, times:10, average:true, trim:true) {
    with "forkOffChild + runChildDirectly (since GPars 0.12)", {
        assert fibo2(20) == 6765
    }
    with "forkOffChild x 2", {
        assert fibo(20) == 6765
    }
}
benchmarks.sort().prettyPrint()

という感じのスクリプトを実行すると(fibo, fibo2は前述の関数)...

$ groovy fib_forkjoin.groovy
Begin...
                                                                                         user   system           cpu             real

forkOffChild + runChildDirectly (since GPars 0.12)      1807125 220875  2028000 228502125
forkOffChild x 2                                                          1446500   97375  1543750 241445250
Done.

とまあこんな感じで(単位はナノ秒)、何度か繰り返してもrunChildDirectlyありの方がほんのちょっとだけ早い感じなので、やはり効果はあるようですね。大雑把ですが。

おわりに

GPars 0.12は単体として既にリリース済みなのですが、Groovy1.8.0と併用したい人はさっき書いたように

  • バンドルされている$GROOVY_HOME/lib/gpars-0.11.jarを削除して、Grapeで0.12を指定する
  • バンドルされている$GROOVY_HOME/lib/gpars-0.11.jarをjarを0.12のものに置き換える

のいずれかが必要です。

1.8.0以前のGroovyを使ってる場合は、単純にGPars 0.12を@GrabするだけでOk.

次のGroovy 1.8.1には、GPars 0.12(もしくは0.13?)が同梱される予定なので、それまではしばらくは不便ですがそんな感じで暑い夏を乗り切りましょう ;-)

追記 07/25

7/21にGroovy 1.8.1がリリースされましたが、GParsは0.11のままでした。残念。というわけで、首を長くして次の 1.8.2を待ちましょう。

*1:Groovy1.8からGparsが標準バンドルされるようになってます。ちなみにgroovy1.8.0にはgpars0.11が入ってます。

*2:週末はちょっと帰省イベントが発動したのでお休み

*3: http://nagaimasato-ja.blogspot.com/2011/06/gbench-benchmark-annotation.html の7/13バージョンを改造したものを$HOME/.groovy/libに突っ込んで利用。その後ながいさんにマージしていただいてます。