Class RecursiveAction

java.lang.Object

java.util.concurrent.ForkJoinTask<Void>

java.util.concurrent.RecursiveAction

All Implemented Interfaces:

Serializable, Future<Void>

public abstract class RecursiveAction
extends ForkJoinTask<Void>

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++];
  }
}

You could then sort anArray by creating new SortTask(anArray) and invoking it in a ForkJoinPool. As a more concrete simple example, the following task increments each element of an array:

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;
  }
}

Since:

1.7

See Also:

• Serialized Form

Nested Class Summary

Nested classes/interfaces declared in interface Future

Future.State

Modifier and Type	Interface	Description
static enum	Future.State	Represents the computation state.

Constructor Summary

Constructors

Constructor	Description
RecursiveAction()	Constructor for subclasses to call.

Method Summary

Modifier and Type	Method	Description
protected abstract void	compute()	The main computation performed by this task.
protected final boolean	exec()	Implements execution conventions for RecursiveActions.
final Void	getRawResult()	Always returns null.
protected final void	setRawResult(Void mustBeNull)	Requires null completion value.

Methods declared in class ForkJoinTask

adapt, adapt, adapt, adaptInterruptible, adaptInterruptible, adaptInterruptible, cancel, compareAndSetForkJoinTaskTag, complete, completeExceptionally, exceptionNow, fork, get, get, getException, getForkJoinTaskTag, getPool, getQueuedTaskCount, getSurplusQueuedTaskCount, helpQuiesce, inForkJoinPool, invoke, invokeAll, invokeAll, invokeAll, isCancelled, isCompletedAbnormally, isCompletedNormally, isDone, join, peekNextLocalTask, pollNextLocalTask, pollSubmission, pollTask, quietlyComplete, quietlyInvoke, quietlyJoin, quietlyJoin, quietlyJoinUninterruptibly, reinitialize, resultNow, setForkJoinTaskTag, state, tryUnfork

Modifier and Type	Method	Description
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 ForkJoinTask.join().
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 ForkJoinTask.join().
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 ForkJoinTask.join(), translating any checked exceptions encountered into RuntimeException.
static ForkJoinTask<?>	adaptInterruptible(Runnable runnable)	Returns a new ForkJoinTask that performs the run method of the given Runnable as its action, and returns null upon ForkJoinTask.join(), translating any checked exceptions encountered into RuntimeException.
static <T> ForkJoinTask<T>	adaptInterruptible(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 ForkJoinTask.join(), translating any checked exceptions encountered into RuntimeException.
static <T> ForkJoinTask<T>	adaptInterruptible(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 ForkJoinTask.join(), translating any checked exceptions encountered into RuntimeException.
boolean	cancel(boolean mayInterruptIfRunning)	Attempts to cancel execution of this task.
final boolean	compareAndSetForkJoinTaskTag(short expect, short update)	Atomically conditionally sets the tag value for this task.
void	complete(Void 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.
Throwable	exceptionNow()	Returns the exception thrown by the task, without waiting.
final ForkJoinTask<Void>	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 ForkJoinTask.inForkJoinPool().
final Void	get()	Waits if necessary for the computation to complete, and then retrieves its result.
final Void	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 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.
final short	getForkJoinTaskTag()	Returns the tag for this task.
static ForkJoinPool	getPool()	Returns the pool hosting the current thread, or null if the current thread 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.
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 Void	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 <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.
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.
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 Void	join()	Returns the result of the computation when it is done.
protected 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.
protected 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.
protected static ForkJoinTask<?>	pollSubmission()	If the current thread is operating in a ForkJoinPool, unschedules and returns, without executing, a task externally submitted to the pool, if one is available.
protected 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	quietlyComplete()	Completes this task normally without setting a value.
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.
final boolean	quietlyJoin(long timeout, TimeUnit unit)	Tries to join this task, returning true if it completed (possibly exceptionally) before the given timeout elapsed and the current thread has not been interrupted.
final boolean	quietlyJoinUninterruptibly(long timeout, TimeUnit unit)	Tries to join this task, returning true if it completed (possibly exceptionally) before the given timeout elapsed.
void	reinitialize()	Resets the internal bookkeeping state of this task, allowing a subsequent fork.
Void	resultNow()	Returns the computed result, without waiting.
final short	setForkJoinTaskTag(short newValue)	Atomically sets the tag value for this task and returns the old value.
Future.State	state()	Returns the computation state.
boolean	tryUnfork()	Tries to unschedule this task for execution.

Methods declared in class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Modifier and Type	Method	Description
protected Object	clone()	Answers a new instance of the same class as the receiver, whose slots have been filled in with the values in the slots of the receiver.
boolean	equals(Object o)	Compares the argument to the receiver, and answers true if they represent the same object using a class specific comparison.
protected void	finalize()	Deprecated, for removal: This API element is subject to removal in a future version. May cause performance issues, deadlocks and hangs.
final Class<? extends Object>	getClass()	Answers the unique instance of java.lang.Class which represents the class of the receiver.
int	hashCode()	Answers an integer hash code for the receiver.
final void	notify()	Causes one thread which is waiting on the receiver to be made ready to run.
final void	notifyAll()	Causes all threads which are waiting on the receiver to be made ready to run.
String	toString()	Answers a string containing a concise, human-readable description of the receiver.
final void	wait()	Causes the thread which sent this message to be made not ready to run pending some change in the receiver (as indicated by notify or notifyAll).
final void	wait(long time)	Causes the thread which sent this message to be made not ready to run either pending some change in the receiver (as indicated by notify or notifyAll) or the expiration of the timeout.
final void	wait(long time, int frac)	Causes the thread which sent this message to be made not ready to run either pending some change in the receiver (as indicated by notify or notifyAll) or the expiration of the timeout.

Constructor Details

RecursiveAction

public RecursiveAction()

Constructor for subclasses to call.

Method Details

compute

protected abstract void compute()

The main computation performed by this task.

getRawResult

public final Void getRawResult()

Always returns null.

Specified by:

getRawResult in class ForkJoinTask<Void>

Returns:

null always

setRawResult

protected final void setRawResult(Void mustBeNull)

Requires null completion value.

Specified by:

setRawResult in class ForkJoinTask<Void>

Parameters:

mustBeNull - the value

exec

protected final boolean exec()

Implements execution conventions for RecursiveActions.

Specified by:

exec in class ForkJoinTask<Void>

Returns:

true if this task is known to have completed normally