JAVA同時シリーズ--ForkJoinPool初体験

ForkJoinPool初体験
ForkJoinPoolって何?
ForkJoinPoolはJAVAの中で比較的新しいスレッドプールで、まず勉強して使ってみます.彼は主にサブタスクを生み出すことができるタスクを処理するために使われている.
このスレッドプールはJDK 7に組み込まれており、その名前ForkJoinもその実行メカニズムを記述しており、主な使い方は以前のスレッドプールと同じであり、タスクをスレッドプールに渡して実行し、スレッドプールにもタスクキューがあり、タスクを格納している.しかし、ForkJoinPoolスレッドプールと以前のスレッドプールには2つの大きな違いがあります.1つ目は、サブタスクを生成できるタスクを実行するのに適しています.
図に示すように、私たちはTaskを持っています.このTaskは3つのサブタスクを生成することができます.3つのサブタスクが並列に実行された後、結果をResultにまとめます.例えば、メインタスクは非常に重い計算タスクを実行する必要があります.私たちは計算を3つの部分に分割することができます.この3つの部分は互いに独立に影響を与えません.このようにCPUのマルチコアの優位性を利用することができます.並列計算を行い、結果をまとめます.ここでは主に2つのステップに関連しています.最初のステップは分割、すなわちFork、2番目のステップは要約、つまりJoinです.ここではForkJoinPoolスレッドプールの名前の由来を知っているはずです.
//『Java同時プログラミング78講』より抜粋
典型的なフィボナッチ数列を例にとると、f(n)=f(n-1)+f(n-2)である.1つのタスクは、2つのサブタスクを生成し、最終的にこのタスクの結果にまとめることができます.古典的な実現方法はいくつかあります.

再帰,トップダウンの思想は,f(1)まで再帰される.これにより、ノード数の範囲が約2^nの高いlog(n)のツリーが生成されます.スタックの消費は恐怖の指数級だ.

反復,ボトムアップの考え方から,f(1)からf(n)まで計算することができ,ループのたびに結果は前の項に加えて前の項の値であり,スタックを消費するだけでなく,タスクを生成する需要も分裂しない.

再帰+記憶.アイテムを計算するたびにmapを先に行ったり、arrayコンテナでアイテムが存在するかどうかを問い合せたりして、存在する場合はそのまま返し、存在しない場合はn-1およびn-2アイテムを取り、1つが取れない場合は再帰的に値を取り、最後に結果を加算してコンテナに入れ、返します.[f(n−1)=f(n−2)+f(n−3)のため,f(n−2)は順次押し下げても何度も繰り返し実行される.

反復+記憶.底から上へ計算し,各サイクルの計算結果を容器に保存した[ここでは容器を取らず,加算の時間はmapを取るよりずっと短くなる].それは容器に入れて何の役にも立たない.の用途は次のとおりです.

次回は[1...n]の範囲内の数を取る結果があり、直接取ることができます.

次回取る数mがnより大きい場合、nから下から上へ計算することができ、計算時間の大部分を節約することができる.

うん.少し話が遠くなって、私が実践したいのはForkJoinPoolです.では、上記の4つの古典的な実装と、Fork分割タスクの特性から、再帰的な方法しか使用できないに違いありません.では、3つ目の実装方式に基づいて改造します.
まず、3つ目の実装方法のコードを貼り付けます.

/**
 *       +   
 */
public class Fib3 implements Fib{

    public Map<Integer, Integer> fib = new HashMap<>();
    @Override
    public int fib(int n) {
        Integer result = fib.get(n);
        if (result != null) {
            return result;
        } else {
            doFib(n);
        }
        return fib.get(n);
    }

    private void doFib(int n) {
        if (n <= 2) {
            fib.put(n, 1);
            return;
        }
        fib.put(n, fib(n - 1) + fib(n - 2));
    }
}

ForkJoinPoolの使用

/**
 * FibForkJoin    +   
 */
public class FibForkJoin2 extends RecursiveTask<Integer> {
    private volatile static Map<Integer, Integer> map = new ConcurrentHashMap<Integer, Integer>(50);
    int n;

    public FibForkJoin2(int n) {
        this.n = n;
    }

    @Override
    protected Integer compute() {
        if (n <= 1) {
            return n;
        }
        if (map.get(n) != null) {
            return map.get(n);
        }
        //     
        FibForkJoin2 f1 = new FibForkJoin2(n - 1);
        f1.fork();
        FibForkJoin2 f2 = new FibForkJoin2(n - 2);
        f2.fork();
        //     
        int result = f1.join() + f2.join();
        map.put(n, result);
        return result;
    }
}

MAINメソッドテスト

    public static void main(String[] args) {
        int n = 45;
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        long endTime;
        long startTime = System.currentTimeMillis();
        ForkJoinTask<Integer> task = forkJoinPool.submit(new FibForkJoin2(n));
        try {
            System.out.println(task.get());
            endTime = System.currentTimeMillis();
            System.out.println("forkJoin   ：" + (endTime - startTime) );
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }

        Fib3 fib3 = new Fib3();
        startTime = System.currentTimeMillis();
        System.out.println(fib3.fib(n));

        endTime = System.currentTimeMillis();
        System.out.println("Fib3   ：" + (endTime - startTime) );

    }

テスト結果1

1134903170
forkJoin   ：4
1134903170
Fib3   ：0

Process finished with exit code 0

の結果は「感動的」で、ForkJoinPoolを使うとかえって遅くなり、正常な再帰+記憶は、1ミリ秒もかかりません.フィボナッチ数列計算の1つの関数の消費時間はもともと低く、記憶化を加えた後、getが完了し、スレッドの作成、切り替えなどのオーバーヘッドよりはるかに低いこともよく理解されています.

実際のビジネスシーンでは、スレッドプールで処理するタスクを使用しています.彼はわずかなものを計算するだけでなく、多くの場合非常に時間がかかります.私たちはsleep(30)をシミュレートして試してみました.上の2つのコードにsleepを追加しました.コードは次のように

です.

// FORK
    @Override
    protected Integer compute() {
        if (n <= 1) {
            return n;
        }
        if (map.get(n) != null) {
            try {
                Thread.sleep(30);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            return map.get(n);
        }
        FibForkJoin2 f1 = new FibForkJoin2(n - 1);
        f1.fork();
        FibForkJoin2 f2 = new FibForkJoin2(n - 2);
        f2.fork();
        int result = f1.join() + f2.join();
        map.put(n, result);
        return result;
    }

// FIB3
@Override
    public int fib(int n) {
        Integer result = fib.get(n);
        if (result != null) {
            try {
                Thread.sleep(30);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            return result;
        } else {

            doFib(n);
        }
        return fib.get(n);
    }

実験結果2

1134903170
forkJoin   ：1252
1134903170
Fib3   ：1372

Process finished with exit code 0

実験結果2から見ると,単一のタスクに10ミリ秒しかかからない場合,ForkJoinPoolで優位性を示し始めた.では、500ミリ秒に変更して

を試してみましょう.
実験結果3

1134903170
forkJoin   ：19235
1134903170
Fib3   ：21231

比較結果2および結果3

の実験二消費時間の割合は0.912であり,実験三消費時間の割合は0.90であった.結論1:高時間のタスクでは、時間がかかるほどForkJoinPoolの優位性が大きくなる.

では、さらに時間がかかるかどうかを見て、sleepの時間を1000ミリ秒に調整します.
実験結果4

1134903170
forkJoin   ：38345
1134903170
Fib3   ：42438

Process finished with exit code 0

の結果を比較すると、

の消費時間の割合は0.90で、変化は10ミリ秒から500ミリ秒ほど大きくありません.

フィボナッチ数列の計算にかかる時間は全体的に4 ms未満であることを無視し、実験3と実験4を比較すると、Fib 3の消費時間は元の1.99(2)倍であり、ForkJoinPoolの方式も元の1.99(2)倍であることが分かった.個人的にこの比較をしたのは、ForkJoinPoolはもっと小さい数値で、ちょうど2倍ではなく、例が正確ではないのではないかと思います.だから自分はまた2000ミリ秒のセットを増やして、倍数の両者はすべて1.98であることを発見して、一応線形の最適化に近づくと思っています.