Upgrade to Pro — share decks privately, control downloads, hide ads and more …

#JJUG Fork/Join フレームワークを効率的に正しく使いたい

#JJUG Fork/Join フレームワークを効率的に正しく使いたい

2019 年 9 月開催の「JJUG ナイトセミナー: ビール片手にLT大会」発表資料です。

Fork/join parallelism in the wild の論文の内容をもとに、Fork/Join フレームワークを使う上でのデザインパターン (ベストプラクティス) とアンチパターンが速度パフォーマンスにどのような影響を及ぼすかをベンチマークを測定して評価してみました。

イベント: https://jjug.doorkeeper.jp/events/95987
論文: https://dl.acm.org/citation.cfm?id=2647511
関連ブログ: https://k11i.biz/blog/2019/09/07/jjug-lt-fork-join-framework-benchmark/

KOMIYA Atsushi

September 06, 2019
Tweet

More Decks by KOMIYA Atsushi

Other Decks in Programming

Transcript

  1. どういう処理に使える・適しているのか? • 処理の特性 ◦ CPU-intensive である ◦ 並列化できる ◦ 小さな問題に再帰的に分割できる

    • 例 ◦ 分割統治法に基づく処理 ▪ マージソート、クイックソート ◦ 数値計算、シミュレーション ▪ 単純計算をひたすら繰り返す類のもの
  2. Fork/Join フレームワークの使い方 1. ForkJoinTask を継承したクラスで処理を実装する ◦ ForkJoinTask よりも RecursiveAction や

    RecursiveTask を継承した方が実装しやすい 2. ForkJoinPool オブジェクトを用意する ◦ ForkJoinPool.commonPool() ◦ new ForkJoinPool(int parallelism) 3. ForkJoinPool#invoke(task) で処理を実行する
  3. public class QuickSortTask extends java.util.concurrent.RecursiveAction { private final double[] values;

    private final int start, end; public QuickSortTask(double[] values, int start, int end) { this.values = values; this.start = start; this.end = end; } @Override protected void compute() { if (end - start < 30) { insertionSort(); return; } int p = partition(); invokeAll(new QuickSortTask(values, start, p), new QuickSortTask(values, p, end)); } private void insertionSort() { ... } private int partition() { ... } }
  4. デザインパターン • Linked Subtasks ◦ 不定個数のサブタスクを保持する方法についてのパターン • Leaf Tasks ◦

    サブタスクに処理を分割をするタスクと、実際に計算などの処理を するタスクの実装クラスを分ける • Avoid unnecessary forking ◦ 不必要な ForkJoinTask#fork() の呼び出しを避ける • Sequential Cutoff ◦ タスクの粒度が小さくなったところでサブタスクへの分割を止めて (並列処理せずに) 直列的に計算をする
  5. アンチパターン • Heavyweight Splitting ◦ サブタスクへの分割でオーバーヘッドの大きい処理をしてし まう • Heavyweight Merging

    ◦ サブタスクの処理結果をマージする際にオーバーヘッドの大 きい処理をしてしまう • Inappropriate Sharing of Resources among Tasks ◦ 並列実行されるタスク間で不適切なリソース共有をしてしまう
  6. Design pattern: Sequential Cutoff • Fork/Join のタスクで処理すべきデータの大きさ (e.g. 配列やリストのサイズ) に着目する

    ◦ Fork/Join で再帰的にデータを分割する • データの大きさが適度に小さくなったら、再帰的な分割 を止めて具体的な処理を実行する • 分割を止める「閾値」の調整がパフォーマンスを左右す る
  7. 例: マージソート • 乱数生成された長さ 30 万の double の配列を マージソートでソートする ◦

    配列の大きさが閾値以下となったら分割を止めて Arrays.sort() でソートする • 10 / 100 / 1,000 / 10,000 / 100,000 の 5 つの閾値を 適用して評価する • 1秒あたりの処理回数を計測する
  8. public class MergeSortTask extends RecursiveAction { private static final int

    THRESHOLD = 1000; private final double[] x, work; private final int start, end; public MergeSortTask(double[] x, double[] work, int start, int end) { this.x = x; this.work = work; this.start = start; this.end = end; } @Override protected void compute() { int n = end - start; if (n > THRESHOLD) { int mid = start + (n >>> 1); invokeAll(new MergeSortTask(work, x, start, mid), new MergeSortTask(work, x, mid, end)); merge(mid); } else { Arrays.sort(x, start, end); } } private void merge(int mid) { ... } }
  9. Anti-pattern: Inappropriate Resource Sharing • タスク間で共有するリソースの排他制御 (ロック) が適 切でない ◦

    ロックが不要である、ロック粒度が粗い、リソース競合しうる のにロックしていない… など
  10. 例: double の配列から k 以上の値を抽出する • 乱数生成された長さ 50 万の double

    配列から k 以上 の値を抽出して最終的に List<Double> として出力す る • Fork/Join フレームワークにより、タスクが担当 すべき配列上の範囲を再帰的に分割する ◦ 一定の大きさになったところで、範囲内にある k 以上の値を 抽出してサブタスクの処理結果とする
  11. 例: double の配列から k 以上の値を抽出する • Heavyweight Merging ◦ List<Double>

    をタスクの戻り値とする ◦ 親のタスクにおいて、サブタスクの戻り値を List#addAll(Collection) でマージする • Inappropriate Resource Sharing ◦ Collections.synchronizedList() で包まれた List<Double> をグローバルなリソースとして扱う ◦ この List に抽出された値を List#add() する
  12. 例: double の配列から k 以上の値を抽出する • Baseline ◦ タスクの結果を木構造で保持する ▪

    葉ノードにおいて抽出された値を List<Double> のまま で保持する ◦ Fork/Join フレームワークによる並列処理を終えた後に、木 構造を辿って抽出結果を一つの List<Double> に集約する
  13. Fork/Join フレームワークを効率的に使うには? • リソースの共有方法には十分気をつける ◦ Inappropriate Resource Sharing • オーバーヘッドの大きい処理は避ける

    ◦ Heavyweight Splitting/Merging • 適切なタスクの粒度を見定める ◦ Sequential cutoff • 実装次第では Stream#parallel() よりもよい パフォーマンスを達成できることも!