こっぱみぢんこ

fork/join

jdk7 から導入された、マルチスレッドのための fork/join フレームワークについて。

仕事で使う java のほとんどが web アプリで、そのまたほとんどが struts ベースのフレームワーク上だったりするので、自分でスレッドを生成して何か処理をするってことが無い。なので fork/join も、名前は知っているって程度だった。本当に名前だけ。要は今の俺には必要ないってことなのだが、でもやっぱりどこかで必要があったから追加されたんだよな。 GUI や socket ならもう定型的なやり方が確立されているだろうし、わざわざ新しくフレームワークとして導入するのって、いったいどんな必要だったんだろうか。

と、今日の帰りのバスの中、ぼんやり窓の外を眺めていて、ふと気になったのだった。

で、家に帰ってググってみたら、最初に出てきたサンプルがフィボナッチ数列の計算だった。


F₀ = 0
F₁ = 1
F_n+2 = F_n+1 + F_n

これがフィボナッチ数列の定義。フィボナッチ数列は花弁の枚数とか種のでき方とかといった身近な自然の中に隠れていたりして、これはこれでなかなか面白いものなのだが、それは今は置いておくとして。

こんな簡単な計算を、それも各ステップをスレッドで処理するのってどうなんだろう。このレベルだと、実際の処理時間のほとんどはスレッド生成と待ちになってしまって、スレッドを使う有難味が無いんじゃないだろうか。

見つけたサンプルの処理はこんな感じ。まずはスレッドを管理／実行する側。


package fibonacci;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class FibonacciDemo {

    public FibonacciDemo(RecursiveTask<Long> fibonacci) {
        ForkJoinPool pool = new ForkJoinPool();
        System.out.println(pool.invoke(fibonacci));
    }

    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        new FibonacciDemo(new FibonacciTask(50));
        System.out.println(System.currentTimeMillis() - t0);
    }
}

ForkJoinPool オブジェクトを作って、この invoke メソッドに RecursiveTask インターフェースを実装したオブジェクトを渡す。ここで渡すオブジェクトがフィボナッチ数を計算するもので、ここでは F₅₀ を計算させている。

次いで、スレッドを生成してフィボナッチ数を計算する側。


package fibonacci;

import java.util.concurrent.RecursiveTask;

public class FibonacciTask extends RecursiveTask<Long> {

    private final int n;

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Long compute() {
        if (n <= 1) {
            return (long)n;
        }
        FibonacciTask f1 = new FibonacciTask(n - 1);
        f1.fork();
        FibonacciTask f2 = new FibonacciTask(n - 2);
        return f2.compute() + f1.join();
    }
}

compute が forkJoinPool から非同期処理として実行されるメソッド。この中の fork で更に F_n-1 を計算するスレッドを生成し、join でその結果を得て、 F_n-2 の結果と足し合わせて答えとして返す。

オリジナルは計算を int でやっていたのだが、ちょっと大きい n を計算させたら溢れてしまったので long に変えた。あと、かかった時間をミリ秒単位で表示する処理も追加した。

まあ簡単だよな。だからこそのサンプルなんだし、サンプルが示すべきは「何をやるか」ではなくて「どうやるか」だから、その題材にケチを付けるのもどうかと思う。思うのだが…

これを実行した結果。


12586269025
159763

上が F₅₀ の値。下が処理に要した時間で、単位はミリ秒。およそ2分40秒。しかもこの計算をしている間、CPU はずっと 100% でファンが凄い勢いで回る状態。

CPU 100% は、コア／スレッドを遊ばせなかった結果であって、マルチスレッド化の目的を果たせてるんだけど、そこまでやって実行時間がこれってどうよ。しかも CPU や時間のほとんどはスレッド絡みで費されていて、実際の計算にはほとんど使われていないのだ。

実際に使われて無いことを確かめるために、単一スレッド内で再帰するように書き直して試してみた。


package fibonacci;

import java.util.concurrent.RecursiveTask;

public class FibonacciTask extends RecursiveTask<Long> {

    private final int n;

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Long compute() {
        return calc(n);
    }

    private static long calc(int m) {
        if (m <= 1) {
            return (long) m;
        }
        return calc(m - 1) + calc(m - 2);
    }
}

フィボナッチ数列の定義そのままがコードになっていて判り易い。マルチスレッド版も、途中に fork/join が入っているけどほぼ定義通りで判り易いと思ったのだが、よけいなものが何も入らないのとでは比べ物にならないな。

この実行結果。


12586269025
66867

今度は1分7秒でさっきの半分以下。処理中の CPU は 13% 強でさっきの1/7程度。もう圧倒的。そういう話じゃないのは判ってるんだけど、これじゃあマルチスレッド化の弊害しか示せてないってのが、ねえ。

あ、でもこっちはインスタンスの生成も無くて、スピードアップにはこの違いの方が効いている可能性もあるのか。先のはインスタンス生成がスレッド生成と直接紐づいているのだから、インスタンス生成もスレッド絡みと考えて良いと思うけど、原因をきちんと切り分けるために、毎回インスタンスを生成するようにして計ってみよう。


package fibonacci;

import java.util.concurrent.RecursiveTask;

public class FibonacciTask extends RecursiveTask<Long> {

    private final int n;

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Long compute() {
        return calc();
    }

    private long calc() {
        if (n <= 1) {
            return (long) n;
        }
        return (new FibonacciTask(n - 1)).calc() + (new FibonacciTask(n - 2)).calc();
    }
}

この実行結果。


12586269025
107905

意外にかかったな。この間、CPU はだいたい 16% ぐらいだが、ファンは勢いよく回る。

ここまでの3パターンは、それぞれ何度か繰り返してみたが、処理時間はそれぞれだいたい同じになった。ということで、各パターンの比較から以下を得る。

スレッド関連処理 = 1回目 - 3回目 = およそ50秒
インスタンス生成 = 3回目 - 2回目 = およそ40秒

スレッド関連の方がちょっと重いが、どっちもだいたい同じぐらい足を引っ張っているのだな。まあ、だからどうってことも無いんだけどさ。 fork/join を使うなら、インスタンス生成は必須なんだし。

せっかくなので、再帰を使わずに F₂ から順番に計算する方法でも試してみた。


package fibonacci;

import java.util.concurrent.RecursiveTask;

public class FibonacciTask3 extends RecursiveTask {

    private final int n;

    FibonacciTask3(int n) {
        this.n = n;
    }

    @Override
    protected Long compute() {
        return calc(n);
    }

    private static long calc(int m) {
        if (m <= 1) {
            return (long) m;
        }
        long m0 = 0;
        long m1 = 1;
        long m2 = m1 + m0;
        for (int i = 2; i < m; i++) {
            m0 = m1;
            m1 = m2;
            m2 = m1 + m0;
        }
        return m2;
    }
}

この実行結果。


12586269025
0

ああ…

定義じゃなくて手順を記述しているので、これまでと比べると長ったらしくて判り難いが、実行速度はもう圧倒的。ミリ秒単位じゃ計れない。まあ、単純な足し算と変数の入れ替えのループが50回弱なので当然なんだけどさ。再帰じゃないので、メモリの使用効率もこっちの方が圧倒的に良いだろう。 CPU 使用率はアクティビティモニターの目測なので、これまた計れない。と言うか 1ms 以下の時間の CPU 使用率なんてどうでもいいよな。

しかし、実行時間が 0 と表示されると、妙な満足感があるな。サンプルに求めるものは何かって話だったんだけど、もうそんなことはどうでも良くなってきた。

そう言えば、パソコン黎明期の頃はまだこの先があったんだよな。ループを展開するとか、3つの変数の値を毎回入れ替える処理が勿体無いとか、アセンブラ目線の細かい世界へ。いや、先って言うか、出発点が全然違うのか。当時はメモリが少なくて、再帰処理なんてスタックオーバーフローで即死だし。

最後に実行環境について。

サンプルその他は全て eclipse 上で実行している。マシンは MacBookPro で、スペックは以下の通り。

CPU	2.2GHz Intel Core i7
memory	8GB 1333MHz DDR3 SDRAM

2014 03 01

fork/join