質問
Fork-Join は現在の誇大広告であり、多くの回答で推奨されているように思われるため、実際の速度について調査してみませんか?
これを測定するために、数値の加算を行う小さなプログラム (以下のコードを参照) を作成し、スレッド数、フォークの深さ、フォークの広がりなどのさまざまなパラメーターを使用して分岐し、実行時間を測定しました。実際の計算に費やされた時間と分岐に費やされた時間。
抽象的な答え
ForkJoin は適切に実装されていますが、各フォークのコストが非常に高いため、タスクを並列化する方法としては非常に非効率的です。素朴な問題に最適化された実装は、99% のスレッド実行時間 (Fork-Join で測定されたすべてのものを上回る) を簡単に達成できるため、そのような実装は常にFork-Join 実装よりも高速です。さらに、フォークごとの実際のタスクが小さい場合、Fork-Join 実装は、シングルスレッドの線形実装よりもはるかに遅くなる可能性があります。
したがって、Fork-Join は、他の実装に比べてパフォーマンス上の利点がないため、コードのアーキテクチャに役立つかどうかの問題です。したがって、Fork-Join は次の場合にのみ使用する必要があります。
パフォーマンスは重要ではなく、タスクは他のタスクの結果が続行されるまで頻繁に待機する必要があります。したがって、基本的に、Fork-Join 構造が単純な実装よりもタスクを大幅に簡素化する場合です。
実際のタスクは fork のコストを大幅に上回るため、損失は無視できます。私のテストでは、2 つの値を追加するループは、妥当なパフォーマンスを得るために、フォークごとに少なくとも 10000 回ループする必要がありました。
編集：私が指摘したより詳細な分析については、こちらを参照してください。
テスト設定
私のプログラムでは、RecursiveTask に与えられた N のフィボナッチ数列を計算させました。これにより、実際の計算が 3 つの代入と 1 つの追加に削減されました。特定の CPU では、これはマイナーなタスクです。
テストでは、スレッドの量、タスクごとのフォークの量、およびフィボナッチ ループの長さを変化させました。さらに、async パラメーターを使用していくつかのテストを行いましたが、これを false に設定しても計算時間がわずかに短縮されるだけだったので、スキップしました。結果に大きな違いがなかったため、拡散パラメーター (フォークごとのフォーク) もほとんどスキップされました。
一般に、計算時間は非常に安定しており、タスクに費やされる実際の時間の割合は通常 1% 未満で変動します。したがって、各テスト セットは、アイドル状態のシステムで約 5 回 (数値が不安定な場合はそれ以上) 実行されました。 4 コア (+4 ハイパーコア) の場合、実行時間の中央値が選択されています。
適切な実行は、さまざまなテスト変数を通じて検証されています。特に、使用される実際のスレッドの数は、最初に指定された並列処理パラメーターと決して変わらないことが検証されています。
詳細なテスト結果
どこ：
Time totalメインスレッドの観点から全体の計算にかかった合計時間です。Time taskは、すべてのフォークを組み合わせたフィボナッチ数列を実際に計算するのに費やされた時間です。Time task percentageは、スレッド化による相対的なゲインです (時間タスク / 合計時間)。spread->depth(設定された) スプレッド (フォークごとのフォーク) と (計算された) フォークの深さです。threads実際に使用されたスレッドの量です。task-time/threadフィボナッチ数列全体の計算に各スレッドが実際に費やした時間です。
拡散 -> 深度テスト:
Time total: 8766.670 ms, time task: 1717.418 ms ( 19.59%), spread->depth: 2->26, thread#: 1, task-time/thread: 19.59%
Time total: 7872.244 ms, time task: 1421.478 ms ( 18.06%), spread->depth: 10-> 8, thread#: 1, task-time/thread: 18.06%
Time total: 7336.052 ms, time task: 1280.036 ms ( 17.45%), spread->depth: 100-> 4, thread#: 1, task-time/thread: 17.45%
結論: フォークの数はマイナーな影響しか与えません (フォークが少ないほど良い)。実装はかなり洗練されているようです。他の設定でも同様の結果が得られたので、ここでは省略します。
Fib(0) (分岐に費やされたほぼすべての時間)
Time total: 7866.777 ms, time task: 1421.488 ms ( 18.07%), spread->depth: 10-> 8, thread#: 1, task-time/thread: 18.07%
Time total: 7085.142 ms, time task: 1349.207 ms ( 19.04%), spread->depth: 10-> 8, thread#: 2, task-time/thread: 9.52%
Time total: 6580.609 ms, time task: 1476.467 ms ( 22.44%), spread->depth: 10-> 8, thread#: 4, task-time/thread: 5.61%
結論: 非常に小さなタスクでは、ほとんどの時間が fork に費やされ、単一スレッドの実装は fork-join セットアップよりも約 5 倍速くなります。複数のスレッドがあっても、Fork-Join を使用してパフォーマンスを向上させることは不可能です。
フィブ(100)
Time total: 12487.634 ms, time task: 5707.720 ms ( 45.71%), spread->depth: 10-> 8, thread#: 1, task-time/thread: 45.71%
Time total: 8386.855 ms, time task: 5768.881 ms ( 68.78%), spread->depth: 10-> 8, thread#: 2, task-time/thread: 34.39%
Time total: 7078.769 ms, time task: 6086.997 ms ( 85.99%), spread->depth: 10-> 8, thread#: 4, task-time/thread: 21.50%
結論: マルチスレッドが影響を及ぼし始めている一方で、シングルスレッド実行の損益分岐点に近づいているようです。それでも、シングル スレッドの実装は、どの Fork-Join セットアップよりも高速です。
フィブ(1000)
Time total: 5941.344 ms, time task: 5228.258 ms ( 88.00%), spread->depth: 10-> 7, thread#: 1, task-time/thread: 88.00%
Time total: 3160.818 ms, time task: 5244.241 ms (165.91%), spread->depth: 10-> 7, thread#: 2, task-time/thread: 82.96%
Time total: 16301.697 ms, time task: 53351.694 ms (327.28%), spread->depth: 10-> 8, thread#: 4, task-time/thread: 81.82%
結論: マルチスレッド実行の時間はほぼ線形のゲインで安定し始めますが、スレッドあたりの計算時間の約 20% はフォークに費やされます。この時点で、フォークはスレッド化によってパフォーマンスを向上させることができますが、単純な実装は依然として著しく高速です。
Fib(10000)
Time total: 5204.786 ms, time task: 5119.133 ms ( 98.35%), spread->depth: 10-> 6, thread#: 1, task-time/thread: 98.35%
Time total: 26033.889 ms, time task: 51084.118 ms (196.22%), spread->depth: 10-> 7, thread#: 2, task-time/thread: 98.11%
Time total: 13183.573 ms, time task: 51637.471 ms (391.68%), spread->depth: 10-> 7, thread#: 4, task-time/thread: 97.92%
結論: この数では、計算はフォークのコストを上回ります。単純な実装でもわずかに高速ですが、別の方法でタスクを実装するのがはるかに困難であった場合、分岐による損失は無視できます。
コード
public class Test {
static final int NUM_THREADS = 4;
static final int SPREAD = 10;
static final int LOOPS = 4000000;
static final int CALCULATION_N = 10000;
static final boolean DO_ASYNC = true;
//---
static final long MAX_DEPTH = Math.round(Math.log(LOOPS) / Math.log(SPREAD)); // try to have the execution take about the same time
private static class Task extends RecursiveTask<Integer> {
final static AtomicLong timeExecute = new AtomicLong(0);
final static AtomicLong totalLoops = new AtomicLong(0);
final long depth;
public Task(final long depth) {
this.depth = depth;
}
@Override
protected Integer compute() {
if (depth < MAX_DEPTH) {
final Task[] subTasks = new Task[SPREAD];
for (int i = 0; i < subTasks.length; ++i) {
subTasks[i] = new Task(depth + 1);
}
try {
invokeAll(subTasks);
final long startTime = System.nanoTime();
int result = 0;
for (final Task task : subTasks) {
if (task.isCompletedNormally()) {
result += task.get();
}
}
timeExecute.addAndGet(System.nanoTime() - startTime);
return result;
} catch (Exception e) {
this.completeExceptionally(e);
return null;
}
} else {
totalLoops.incrementAndGet();
final long startTime = System.nanoTime();
int a = 0, b = 1, h;
for (int n = 0; n < CALCULATION_N; ++n) {
h = b;
b = a + b;
a = h;
}
timeExecute.addAndGet(System.nanoTime() - startTime);
return b;
}
}
}
public static void main(String[] args) {
final AtomicInteger threadCount = new AtomicInteger(0);
final ForkJoinPool pool = new ForkJoinPool(NUM_THREADS, new ForkJoinPool.ForkJoinWorkerThreadFactory() {
@Override
public ForkJoinWorkerThread newThread(ForkJoinPool pool) {
threadCount.getAndIncrement();
final ForkJoinWorkerThread result = ForkJoinPool.defaultForkJoinWorkerThreadFactory.newThread(pool);
result.setPriority(Thread.MIN_PRIORITY);
return result;
}
}, null, DO_ASYNC);
final long startTime = System.nanoTime();
final Integer result = pool.invoke(new Task(0));
final double duration = ((double) (System.nanoTime() - startTime)) / 1000000.0;
final double executionDuration = ((double) Task.timeExecute.get()) / 1000000.0;
final double executionPercent = executionDuration / duration * 100.0;
final double executionPercentPerThread = executionPercent / ((double) NUM_THREADS);
System.out.println("Completed: " + result + " in " + Task.totalLoops.get() + " loops.");
System.out.println(String.format("Time total: %8.3f ms, time task: %8.3f ms (%6.2f%%), spread->depth: %2d->%2d, thread#: %1d, task-time/thread: %5.2f%%", duration, executionDuration, executionPercent, SPREAD, MAX_DEPTH, threadCount.get(), executionPercentPerThread));
}
}
間違いを指摘したり、改善のための提案をしたりしてください。いくつかのボーナスポイントについて、最も価値のある回答を受け入れます。