/* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/licenses/publicdomain */ package jsr166y; /** * Recursive resultless ForkJoinTasks. This class establishes * conventions to parameterize resultless actions as {@code Void} * ForkJoinTasks. Because {@code null} is the only valid value of * type {@code Void}, methods such as join always return {@code null} * upon completion. * *
Sample Usages. Here is a sketch of a ForkJoin sort that * sorts a given {@code long[]} array: * *
{@code * class SortTask extends RecursiveAction { * final long[] array; final int lo; final int hi; * SortTask(long[] array, int lo, int hi) { * this.array = array; this.lo = lo; this.hi = hi; * } * protected void compute() { * if (hi - lo < THRESHOLD) * sequentiallySort(array, lo, hi); * else { * int mid = (lo + hi) >>> 1; * invokeAll(new SortTask(array, lo, mid), * new SortTask(array, mid, hi)); * merge(array, lo, hi); * } * } * }}* * You could then sort anArray by creating {@code new SortTask(anArray, 0, * anArray.length-1) } and invoking it in a ForkJoinPool. * As a more concrete simple example, the following task increments * each element of an array: *
{@code * class IncrementTask extends RecursiveAction { * final long[] array; final int lo; final int hi; * IncrementTask(long[] array, int lo, int hi) { * this.array = array; this.lo = lo; this.hi = hi; * } * protected void compute() { * if (hi - lo < THRESHOLD) { * for (int i = lo; i < hi; ++i) * array[i]++; * } * else { * int mid = (lo + hi) >>> 1; * invokeAll(new IncrementTask(array, lo, mid), * new IncrementTask(array, mid, hi)); * } * } * }}* *
The following example illustrates some refinements and idioms * that may lead to better performance: RecursiveActions need not be * fully recursive, so long as they maintain the basic * divide-and-conquer approach. Here is a class that sums the squares * of each element of a double array, by subdividing out only the * right-hand-sides of repeated divisions by two, and keeping track of * them with a chain of {@code next} references. It uses a dynamic * threshold based on method {@code surplus}, but counterbalances * potential excess partitioning by directly performing leaf actions * on unstolen tasks rather than further subdividing. * *
{@code * double sumOfSquares(ForkJoinPool pool, double[] array) { * int n = array.length; * int seqSize = 1 + n / (8 * pool.getParallelism()); * Applyer a = new Applyer(array, 0, n, seqSize, null); * pool.invoke(a); * return a.result; * } * * class Applyer extends RecursiveAction { * final double[] array; * final int lo, hi, seqSize; * double result; * Applyer next; // keeps track of right-hand-side tasks * Applyer(double[] array, int lo, int hi, int seqSize, Applyer next) { * this.array = array; this.lo = lo; this.hi = hi; * this.seqSize = seqSize; this.next = next; * } * * double atLeaf(int l, int r) { * double sum = 0; * for (int i = l; i < h; ++i) // perform leftmost base step * sum += array[i] * array[i]; * return sum; * } * * protected void compute() { * int l = lo; * int h = hi; * Applyer right = null; * while (h - l > 1 && * ForkJoinWorkerThread.getEstimatedSurplusTaskCount() <= 3) { * int mid = (l + h) >>> 1; * right = new Applyer(array, mid, h, seqSize, right); * right.fork(); * h = mid; * } * double sum = atLeaf(l, h); * while (right != null) { * if (right.tryUnfork()) // directly calculate if not stolen * sum += right.atLeaf(right.lo, right.hi); * else { * right.helpJoin(); * sum += right.result; * } * right = right.next; * } * result = sum; * } * }}*/ public abstract class RecursiveAction extends ForkJoinTask