先月に引き続き、今月もFork/Join Frameworkについて紹介していきます。
ハードウエアのトレンドはマルチコア、そしてメニーコアに向かっており、それにあわせてソフトウエアも変化していかなくてはいけません。そのためには、細分化したタスクを複数のコアに対してまんべんなく処理させることが必要になってきます。
そこで、タスクを細分化する手法として前回紹介したのが、分割統治法です。 分割統治法は問題領域を分割し、再帰して処理する手法です。再帰ごとに分割を行い、領域が十分に小さくなったら直接処理を行います。このようにすることで、タスクを細分化することができます。
分割統治法はソートや検索、行列操作などに応用することができます。これ以外にも数値積分や、チェスやオセロなどのゲームの枝狩りにも応用することができます。
そして、分割統治法を並行処理するためのフレームワークとしてJava SE 7に導入されたのがFork/Join Frameworkです。
Fork/Join FrameworkはWork Stealing手法をベースに実装されています。Work Stealingをベースにすることで、タスクごとのオーバヘッドが少なく、競合も起きにくくなっています。
今回は、まずFork/Join Frameworkの例としてマージソートを取りあげてみます。
Fork/Join Frameworkのパフォーマンス
ご存じの方も多いはずですが、コレクションのソートはjava.util.Collectionsクラスのsortメソッドで行うことができます。このsortメソッドはマージソートがベースになっています。
マージソートはソートする対象を再帰を使用して分割し、分割した領域のソート結果をまとめてマージすることでソートしていく手法です。
Collectionsクラスのsortメソッドは、java.util.ArraysクラスのmergeSortメソッドに委譲されています。mergeSortメソッドは実際に再帰を用いて分割し、ソートを行っています。
そこで、ArraysクラスのmergeSortメソッドを、Fork/Join Frameworkを使用して書き直してみましょう。ここでは、OpenJDKで公開されているArraysクラスをベースに使用しました。
MergeSortDemo.java
以下にタスク部分のソースを示します。
private final static int INSERTIONSORT_THRESHOLD = 7;
static class MergeSortTask extends RecursiveAction {
final Object[] src;
final Object[] dest;
int low;
int high;
public MergeSortTask(Object[] src, Object[] dest, int low, int high) {
this.src = src;
this.dest = dest;
this.low = low;
this.high = high;
}
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
protected void compute() {
int length = high - low;
if (length <= INSERTIONSORT_THRESHOLD) {
for (int i = low; i < high; i++) {
for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) {
swap(dest, j, j - 1);
}
}
return;
}
int destLow = low;
int destHigh = high;
int mid = (low + high) >>> 1;
MergeSortTask left = new MergeSortTask(dest, src, low, mid);
left.fork();
MergeSortTask right = new MergeSortTask(dest, src, mid, high);
right.compute();
left.join();
if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0) {
dest[i] = src[p++];
} else {
dest[i] = src[q++];
}
}
}
}
ここでは、マージソートのアルゴリズムについては説明を省略しますが、興味深いコードなので、ぜひ読解してみてください。
前回示したように、java.util.concurrent.RecursiveActionクラスは処理をcomputeメソッドに記述します。再帰で処理する部分をforkし、joinで処理の終了を待ちます(赤字部分)。RecursiveActionクラスを使用しているので、joinの戻り値はありません。
タスクが記述できたので、実際に動かしてみましょう。
ここでは3.2GHzで動作する4コアのIntel Xeon X5482を使用したコンピュータで実行してみました。メモリーは4GB、OSにはWindows 7 32bit版を使用しています。また、JavaはJDK 7 build 146を使用し、サーバーVMで実行しています。
ソートの対象は要素数が10,000,000の整数の配列です。ここではワークスレッドの数を1から4まで変化させて計測しました。また、参考のためにArrays.sortメソッドでも一緒にソートを行っています。
計測には、まず5回ソートを行い、その後の10回のソートの平均値を採用しています。