kagamihogeの日記

kagamihogeの日記です。

The Java TutorialsのFork/Joinのところをテキトーに訳した

The Java TutorialsFork/Joinのところをテキトーに読んで訳した。さすがに本格的なことは書いてないんで、まぁふーんって感じ。

Fork/Join

fork/joinフレームワークは、マルチプロセッサの利点を生かすためのExecutorServiceインタフェースの実装です。再帰的に小さな断片に分割して動作するように設計されています。その目的は、アプリケーションのパフォーマンスを向上させるために、すべての利用可能なプロセッサの能力を使うことです。

どのExecutorService実装を使うとしても、fork/joinフレームワークはスレッドプールのワーカスレッドにタスクを分配します。fork/joinフレームワークはwork-stealingアルゴリズムを使用するので、独立しています。やることがなくなったワーカースレッドはビジー状態の他スレッドからタスクをスチール*1できます。

fork/joinフレームワークのコアクラスはForkJoinPoolで、AbstractExecutorServiceクラスを拡張しています。ForkJoinPoolは核となるwork-stealingアルゴリズムを実装し、ForkJoinTaskプロセスを実行可能です。

Basic Use

fork/joinフレームワークを使用するための最初のステップは、ある問題のセグメントを処理するコードを書くことです。以下の疑似コードのようになるべきです。

if (ある問題の部分が十分に小さい)
  問題を直接解く
else
  問題を二つの断片に分割する
  二つの断片を実行して結果を待機する

ForkJoinTaskサブクラスである、RecursiveTask(結果を返すことが可能)かRecursiveActionのどちらかを一般的には使用して、この疑似コードをラップします。

ForkJoinTaskサブクラスが用意できたら、実行すべきすべての問題を表現するオブジェクトを生成し、ForkJoinPoolインスタンスinvoke()メソッドに渡します。

Blurring for Clarity

fork/joinフレームワークがどのように動作するのかの理解を助けるために、以下の例を考えてみます。いま、ぼかし画像を作ろうとしている、と仮定します。元画像は整数の配列によって表現されており、各整数は単一ピクセルの色値です。また、ぼかしを入れた先の画像も元画像と同一サイズの整数配列によって表現されます。

元画像の配列を一度に一ピクセル処理することでぼかし作業は完了します。各ピクセルは周囲のピクセルの平均値で、その結果を変換先の配列に配置します。画像は巨大な配列なので、この処理は長時間かかる可能性があります。fork/joinフレームワークを使用するアルゴリズムを実装するためのマルチプロセッサーのシステムでコンカレント処理の利点を生かすことができます。

public class ForkBlur extends RecursiveAction {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;
  
    // Processing window size; should be odd.
    private int mBlurWidth = 15;
  
    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    protected void computeDirectly() {
        int sidePixels = (mBlurWidth - 1) / 2;
        for (int index = mStart; index < mStart + mLength; index++) {
            // Calculate average.
            float rt = 0, gt = 0, bt = 0;
            for (int mi = -sidePixels; mi <= sidePixels; mi++) {
                int mindex = Math.min(Math.max(mi + index, 0),
                                    mSource.length - 1);
                int pixel = mSource[mindex];
                rt += (float)((pixel & 0x00ff0000) >> 16)
                      / mBlurWidth;
                gt += (float)((pixel & 0x0000ff00) >>  8)
                      / mBlurWidth;
                bt += (float)((pixel & 0x000000ff) >>  0)
                      / mBlurWidth;
            }
          
            // Reassemble destination pixel.
            int dpixel = (0xff000000     ) |
                   (((int)rt) << 16) |
                   (((int)gt) <<  8) |
                   (((int)bt) <<  0);
            mDestination[index] = dpixel;
        }
    }
  
  ...

まず、compute()抽象メソッドを実装し、これはぼかし作業か二つの小タスクへの分割か、どちらかを実行します。作業を実行するか分割するかは、単純に配列長としきい値が決定します。

protected static int sThreshold = 100000;

protected void compute() {
    if (mLength < sThreshold) {
        computeDirectly();
        return;
    }
    
    int split = mLength / 2;
    
    invokeAll(new ForkBlur(mSource, mStart, split, mDestination),
              new ForkBlur(mSource, mStart + split, mLength - split,
                           mDestination));
}

RecursiveActionのサブクラスを使用する場合、ForkJoinPoolで実行するためのタスクのセットアップは簡単で、以下のステップの通りです。

1. 実行すべき全作業を表現するタスクを生成。

// src に変換元画像のイメージのピクセル
// dst に変換先画像のイメージのピクセル
ForkBlur fb = new ForkBlur(src, 0, src.length, dst);

2. タスクを実行するForkJoinPoolを生成。

ForkJoinPool pool = new ForkJoinPool();

3. タスクの実行。

pool.invoke(fb);

ソースコード全体には、変換先イメージファイルを生成するその他のコードも含まれており、詳細はForkBlurを参照してください。

Standard Implementations

マルチプロセッサシステムでコンカレントに実行するタスクのためにカスタムアルゴリズム(前のセクションのForkBlur.javaなど)を実装するfork/joinフレームワークの使用法に加えて、Java SEにはfork/joinフレームワークを使用して実装されている一般的で有用な機能があります。Java SE 8で導入されたそうした実装の一つが、java.util.ArraysparallelSort()メソッドで使用されています。これらのメソッドsortに似ていますが、fork/joinフレームワークを使用してコンカレントの利点を取り入れています。マルチプロセッサシステムで実行するとき、大規模配列のパラレルソートはシーケンシャルソートよりも高速です。しかし、fork/joinフレームワークがどのようにそれらのメソッドで活用されているかについてはJava Tutorialsの範囲外です。詳細な情報についてはJava APIドキュメントを参照してください。

fork/joinフレームワークのその他の実装はJava SE 8でリリース予定のProject Lambdaの一部であるjava.util.streamsパッケージのメソッドで使用されています。詳細な情報についてはLambda Expressionsを参照してください。

*1:原文 steal 他のスレッドから横取りするからこの単語なわけだが、日本語ではどうしてるのかと軽くぐぐると「ワークスチール」とかそのまんまにしてるのも多いのでそうした。