RecursiveAction

Class Overview

A recursive resultless ForkJoinTask. This class establishes conventions to parameterize resultless actions as Void ForkJoinTasks. Because null is the only valid value of type Void, methods such as join always return null upon completion.

Sample Usages. Here is a simple but complete ForkJoin sort that sorts a given long[] array:

 static class SortTask extends RecursiveAction {
   final long[] array; final int lo, hi;
   SortTask(long[] array, int lo, int hi) {
     this.array = array; this.lo = lo; this.hi = hi;
   
   SortTask(long[] array) { this(array, 0, array.length); }
   protected void compute() {
     if (hi - lo < THRESHOLD)
       sortSequentially(lo, hi);
     else {
       int mid = (lo + hi) >>> 1;
       invokeAll(new SortTask(array, lo, mid),
                 new SortTask(array, mid, hi));
       merge(lo, mid, hi);
     }
   }
   // implementation details follow:
   static final int THRESHOLD = 1000;
   void sortSequentially(int lo, int hi) {
     Arrays.sort(array, lo, hi);
   }
   void merge(int lo, int mid, int hi) {
     long[] buf = Arrays.copyOfRange(array, lo, mid);
     for (int i = 0, j = lo, k = mid; i < buf.length; j++)
       array[j] = (k == hi || buf[i] < array[k]) ?
         buf[i++] : array[k++];
   }
 }}

 class IncrementTask extends RecursiveAction {
   final long[] array; final int lo, 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 next references. It uses a dynamic threshold based on method getSurplusQueuedTaskCount, but counterbalances potential excess partitioning by directly performing leaf actions on unstolen tasks rather than further subdividing.

 double sumOfSquares(ForkJoinPool pool, double[] array) {
   int n = array.length;
   Applyer a = new Applyer(array, 0, n, null);
   pool.invoke(a);
   return a.result;
 

 class Applyer extends RecursiveAction {
   final double[] array;
   final int lo, hi;
   double result;
   Applyer next; // keeps track of right-hand-side tasks
   Applyer(double[] array, int lo, int hi, Applyer next) {
     this.array = array; this.lo = lo; this.hi = hi;
     this.next = next;
   }

   double atLeaf(int l, int h) {
     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 && getSurplusQueuedTaskCount() <= 3) {
       int mid = (l + h) >>> 1;
       right = new Applyer(array, mid, h, 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.join();
         sum += right.result;
       }
       right = right.next;
     }
     result = sum;
   }
 }}

Summary

[Expand] Inherited Methods
From class java.util.concurrent.ForkJoinTask static <T> ForkJoinTask<T> adapt(Callable<? extends T> callable) Returns a new ForkJoinTask that performs the call method of the given Callable as its action, and returns its result upon join(), translating any checked exceptions encountered into RuntimeException. static <T> ForkJoinTask<T> adapt(Runnable runnable, T result) Returns a new ForkJoinTask that performs the run method of the given Runnable as its action, and returns the given result upon join(). static ForkJoinTask<?> adapt(Runnable runnable) Returns a new ForkJoinTask that performs the run method of the given Runnable as its action, and returns a null result upon join(). boolean cancel(boolean mayInterruptIfRunning) Attempts to cancel execution of this task. void complete(V value) Completes this task, and if not already aborted or cancelled, returning the given value as the result of subsequent invocations of join and related operations. void completeExceptionally(Throwable ex) Completes this task abnormally, and if not already aborted or cancelled, causes it to throw the given exception upon join and related operations. abstract boolean exec() Immediately performs the base action of this task and returns true if, upon return from this method, this task is guaranteed to have completed normally. final ForkJoinTask<V> fork() Arranges to asynchronously execute this task in the pool the current task is running in, if applicable, or using the ForkJoinPool.commonPool() if not inForkJoinPool(). final V get(long timeout, TimeUnit unit) Waits if necessary for at most the given time for the computation to complete, and then retrieves its result, if available. final V get() Waits if necessary for the computation to complete, and then retrieves its result. final Throwable getException() Returns the exception thrown by the base computation, or a CancellationException if cancelled, or null if none or if the method has not yet completed. static ForkJoinPool getPool() Returns the pool hosting the current task execution, or null if this task is executing outside of any ForkJoinPool. static int getQueuedTaskCount() Returns an estimate of the number of tasks that have been forked by the current worker thread but not yet executed. abstract V getRawResult() Returns the result that would be returned by join(), even if this task completed abnormally, or null if this task is not known to have been completed. static int getSurplusQueuedTaskCount() Returns an estimate of how many more locally queued tasks are held by the current worker thread than there are other worker threads that might steal them, or zero if this thread is not operating in a ForkJoinPool. static void helpQuiesce() Possibly executes tasks until the pool hosting the current task is quiescent. static boolean inForkJoinPool() Returns true if the current thread is a ForkJoinWorkerThread executing as a ForkJoinPool computation. final V invoke() Commences performing this task, awaits its completion if necessary, and returns its result, or throws an (unchecked) RuntimeException or Error if the underlying computation did so. static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) Forks the given tasks, returning when isDone holds for each task or an (unchecked) exception is encountered, in which case the exception is rethrown. static <T extends ForkJoinTask<?>> Collection<T> invokeAll(Collection<T> tasks) Forks all tasks in the specified collection, returning when isDone holds for each task or an (unchecked) exception is encountered, in which case the exception is rethrown. static void invokeAll(ForkJoinTask...<?> tasks) Forks the given tasks, returning when isDone holds for each task or an (unchecked) exception is encountered, in which case the exception is rethrown. final boolean isCancelled() Returns true if this task was cancelled before it completed normally. final boolean isCompletedAbnormally() Returns true if this task threw an exception or was cancelled. final boolean isCompletedNormally() Returns true if this task completed without throwing an exception and was not cancelled. final boolean isDone() Returns true if this task completed. final V join() Returns the result of the computation when it is done. static ForkJoinTask<?> peekNextLocalTask() Returns, but does not unschedule or execute, a task queued by the current thread but not yet executed, if one is immediately available. static ForkJoinTask<?> pollNextLocalTask() Unschedules and returns, without executing, the next task queued by the current thread but not yet executed, if the current thread is operating in a ForkJoinPool. static ForkJoinTask<?> pollTask() If the current thread is operating in a ForkJoinPool, unschedules and returns, without executing, the next task queued by the current thread but not yet executed, if one is available, or if not available, a task that was forked by some other thread, if available. final void quietlyInvoke() Commences performing this task and awaits its completion if necessary, without returning its result or throwing its exception. final void quietlyJoin() Joins this task, without returning its result or throwing its exception. void reinitialize() Resets the internal bookkeeping state of this task, allowing a subsequent fork. abstract void setRawResult(V value) Forces the given value to be returned as a result. boolean tryUnfork() Tries to unschedule this task for execution.
From class java.lang.Object Object clone() Creates and returns a copy of this Object. boolean equals(Object o) Compares this instance with the specified object and indicates if they are equal. void finalize() Invoked when the garbage collector has detected that this instance is no longer reachable. final Class<?> getClass() Returns the unique instance of Class that represents this object's class. int hashCode() Returns an integer hash code for this object. final void notify() Causes a thread which is waiting on this object's monitor (by means of calling one of the wait() methods) to be woken up. final void notifyAll() Causes all threads which are waiting on this object's monitor (by means of calling one of the wait() methods) to be woken up. String toString() Returns a string containing a concise, human-readable description of this object. final void wait() Causes the calling thread to wait until another thread calls the notify() or notifyAll() method of this object. final void wait(long millis, int nanos) Causes the calling thread to wait until another thread calls the notify() or notifyAll() method of this object or until the specified timeout expires. final void wait(long millis) Causes the calling thread to wait until another thread calls the notify() or notifyAll() method of this object or until the specified timeout expires.
From interface java.util.concurrent.Future abstract boolean cancel(boolean mayInterruptIfRunning) Attempts to cancel execution of this task. abstract V get() Waits if necessary for the computation to complete, and then retrieves its result. abstract V get(long timeout, TimeUnit unit) Waits if necessary for at most the given time for the computation to complete, and then retrieves its result, if available. abstract boolean isCancelled() Returns true if this task was cancelled before it completed normally. abstract boolean isDone() Returns true if this task completed.