Packages

p

akka.dispatch

forkjoin

package forkjoin

Type Members

  1. class ForkJoinPool extends AbstractExecutorService

    An ExecutorService for running ForkJoinTasks.

    An ExecutorService for running ForkJoinTasks. A ForkJoinPool provides the entry point for submissions from non-ForkJoinTask clients, as well as management and monitoring operations.

    A ForkJoinPool differs from other kinds of ExecutorService mainly by virtue of employing work-stealing: all threads in the pool attempt to find and execute tasks submitted to the pool and/or created by other active tasks (eventually blocking waiting for work if none exist). This enables efficient processing when most tasks spawn other subtasks (as do most ForkJoinTasks), as well as when many small tasks are submitted to the pool from external clients. Especially when setting asyncMode to true in constructors, ForkJoinPools may also be appropriate for use with event-style tasks that are never joined.

    A static #commonPool() is available and appropriate for most applications. The common pool is used by any ForkJoinTask that is not explicitly submitted to a specified pool. Using the common pool normally reduces resource usage (its threads are slowly reclaimed during periods of non-use, and reinstated upon subsequent use).

    For applications that require separate or custom pools, a ForkJoinPool may be constructed with a given target parallelism level; by default, equal to the number of available processors. The pool attempts to maintain enough active (or available) threads by dynamically adding, suspending, or resuming internal worker threads, even if some tasks are stalled waiting to join others. However, no such adjustments are guaranteed in the face of blocked I/O or other unmanaged synchronization. The nested ManagedBlocker interface enables extension of the kinds of synchronization accommodated.

    In addition to execution and lifecycle control methods, this class provides status check methods (for example #getStealCount) that are intended to aid in developing, tuning, and monitoring fork/join applications. Also, method #toString returns indications of pool state in a convenient form for informal monitoring.

    As is the case with other ExecutorServices, there are three main task execution methods summarized in the following table. These are designed to be used primarily by clients not already engaged in fork/join computations in the current pool. The main forms of these methods accept instances of ForkJoinTask, but overloaded forms also allow mixed execution of plain Runnable- or Callable- based activities as well. However, tasks that are already executing in a pool should normally instead use the within-computation forms listed in the table unless using async event-style tasks that are not usually joined, in which case there is little difference among choice of methods.

    Call from non-fork/join clients Call from within fork/join computations
    Arrange async execution `[[#execute(ForkJoinTask)]]` `[[ForkJoinTask#fork]]`
    Await and obtain result `[[#invoke(ForkJoinTask)]]` `[[ForkJoinTask#invoke]]`
    Arrange exec and obtain Future `[[#submit(ForkJoinTask)]]` `[[ForkJoinTask#fork]]` (ForkJoinTasks are Futures)
    The common pool is by default constructed with default parameters, but these may be controlled by setting three `[[ System#getProperty system properties]]` with prefix java.util.concurrent.ForkJoinPool.common: parallelism -- an integer greater than zero, threadFactory -- the class name of a `[[ForkJoinWorkerThreadFactory]]`, and exceptionHandler -- the class name of a `[[ java.lang.Thread.UncaughtExceptionHandler Thread.UncaughtExceptionHandler]]`. Upon any error in establishing these settings, default parameters are used. Implementation notes: This implementation restricts the maximum number of running threads to 32767. Attempts to create pools with greater than the maximum number result in IllegalArgumentException. This implementation rejects submitted tasks (that is, by throwing `[[RejectedExecutionException]]`) only when the pool is shut down or internal resources have been exhausted.

    Since

    1.7

  2. abstract class ForkJoinTask[V] extends Future[V] with Serializable

    Abstract base class for tasks that run within a ForkJoinPool.

    Abstract base class for tasks that run within a ForkJoinPool. A ForkJoinTask is a thread-like entity that is much lighter weight than a normal thread. Huge numbers of tasks and subtasks may be hosted by a small number of actual threads in a ForkJoinPool, at the price of some usage limitations.

    A "main" ForkJoinTask begins execution when it is explicitly submitted to a ForkJoinPool, or, if not already engaged in a ForkJoin computation, commenced in the ForkJoinPool#commonPool() via #fork, #invoke, or related methods. Once started, it will usually in turn start other subtasks. As indicated by the name of this class, many programs using ForkJoinTask employ only methods #fork and #join, or derivatives such as #invokeAll(ForkJoinTask...) invokeAll. However, this class also provides a number of other methods that can come into play in advanced usages, as well as extension mechanics that allow support of new forms of fork/join processing.

    A ForkJoinTask is a lightweight form of Future. The efficiency of ForkJoinTasks stems from a set of restrictions (that are only partially statically enforceable) reflecting their main use as computational tasks calculating pure functions or operating on purely isolated objects. The primary coordination mechanisms are #fork, that arranges asynchronous execution, and #join, that doesn't proceed until the task's result has been computed. Computations should ideally avoid synchronized methods or blocks, and should minimize other blocking synchronization apart from joining other tasks or using synchronizers such as Phasers that are advertised to cooperate with fork/join scheduling. Subdividable tasks should also not perform blocking I/O, and should ideally access variables that are completely independent of those accessed by other running tasks. These guidelines are loosely enforced by not permitting checked exceptions such as IOExceptions to be thrown. However, computations may still encounter unchecked exceptions, that are rethrown to callers attempting to join them. These exceptions may additionally include RejectedExecutionException stemming from internal resource exhaustion, such as failure to allocate internal task queues. Rethrown exceptions behave in the same way as regular exceptions, but, when possible, contain stack traces (as displayed for example using ex.printStackTrace()) of both the thread that initiated the computation as well as the thread actually encountering the exception; minimally only the latter.

    It is possible to define and use ForkJoinTasks that may block, but doing do requires three further considerations: (1) Completion of few if any other tasks should be dependent on a task that blocks on external synchronization or I/O. Event-style async tasks that are never joined (for example, those subclassing CountedCompleter) often fall into this category. (2) To minimize resource impact, tasks should be small; ideally performing only the (possibly) blocking action. (3) Unless the ForkJoinPool.ManagedBlocker API is used, or the number of possibly blocked tasks is known to be less than the pool's ForkJoinPool#getParallelism level, the pool cannot guarantee that enough threads will be available to ensure progress or good performance.

    The primary method for awaiting completion and extracting results of a task is #join, but there are several variants: The Future#get methods support interruptible and/or timed waits for completion and report results using Future conventions. Method #invoke is semantically equivalent to fork(); join() but always attempts to begin execution in the current thread. The "quiet" forms of these methods do not extract results or report exceptions. These may be useful when a set of tasks are being executed, and you need to delay processing of results or exceptions until all complete. Method invokeAll (available in multiple versions) performs the most common form of parallel invocation: forking a set of tasks and joining them all.

    In the most typical usages, a fork-join pair act like a call (fork) and return (join) from a parallel recursive function. As is the case with other forms of recursive calls, returns (joins) should be performed innermost-first. For example, a.fork(); b.fork(); b.join(); a.join(); is likely to be substantially more efficient than joining a before b.

    The execution status of tasks may be queried at several levels of detail: #isDone is true if a task completed in any way (including the case where a task was cancelled without executing); #isCompletedNormally is true if a task completed without cancellation or encountering an exception; #isCancelled is true if the task was cancelled (in which case #getException returns a java.util.concurrent.CancellationException); and #isCompletedAbnormally is true if a task was either cancelled or encountered an exception, in which case #getException will return either the encountered exception or java.util.concurrent.CancellationException.

    The ForkJoinTask class is not usually directly subclassed. Instead, you subclass one of the abstract classes that support a particular style of fork/join processing, typically RecursiveAction for most computations that do not return results, RecursiveTask for those that do, and CountedCompleter for those in which completed actions trigger other actions. Normally, a concrete ForkJoinTask subclass declares fields comprising its parameters, established in a constructor, and then defines a compute method that somehow uses the control methods supplied by this base class.

    Method #join and its variants are appropriate for use only when completion dependencies are acyclic; that is, the parallel computation can be described as a directed acyclic graph (DAG). Otherwise, executions may encounter a form of deadlock as tasks cyclically wait for each other. However, this framework supports other methods and techniques (for example the use of Phaser, #helpQuiesce, and #complete) that may be of use in constructing custom subclasses for problems that are not statically structured as DAGs. To support such usages a ForkJoinTask may be atomically tagged with a short value using #setForkJoinTaskTag or #compareAndSetForkJoinTaskTag and checked using #getForkJoinTaskTag. The ForkJoinTask implementation does not use these protected methods or tags for any purpose, but they may be of use in the construction of specialized subclasses. For example, parallel graph traversals can use the supplied methods to avoid revisiting nodes/tasks that have already been processed. (Method names for tagging are bulky in part to encourage definition of methods that reflect their usage patterns.)

    Most base support methods are final, to prevent overriding of implementations that are intrinsically tied to the underlying lightweight task scheduling framework. Developers creating new basic styles of fork/join processing should minimally implement protected methods #exec, #setRawResult, and #getRawResult, while also introducing an abstract computational method that can be implemented in its subclasses, possibly relying on other protected methods provided by this class.

    ForkJoinTasks should perform relatively small amounts of computation. Large tasks should be split into smaller subtasks, usually via recursive decomposition. As a very rough rule of thumb, a task should perform more than 100 and less than 10000 basic computational steps, and should avoid indefinite looping. If tasks are too big, then parallelism cannot improve throughput. If too small, then memory and internal task maintenance overhead may overwhelm processing.

    This class provides adapt methods for Runnable and Callable, that may be of use when mixing execution of ForkJoinTasks with other kinds of tasks. When all tasks are of this form, consider using a pool constructed in asyncMode.

    ForkJoinTasks are Serializable, which enables them to be used in extensions such as remote execution frameworks. It is sensible to serialize tasks only before or after, but not during, execution. Serialization is not relied on during execution itself.

    Since

    1.7

  3. class ForkJoinWorkerThread extends Thread

    A thread managed by a ForkJoinPool, which executes ForkJoinTasks.

    A thread managed by a ForkJoinPool, which executes ForkJoinTasks. This class is subclassable solely for the sake of adding functionality -- there are no overridable methods dealing with scheduling or execution. However, you can override initialization and termination methods surrounding the main task processing loop. If you do create such a subclass, you will also need to supply a custom ForkJoinPool.ForkJoinWorkerThreadFactory to use it in a ForkJoinPool.

    Since

    1.7

  4. class LinkedTransferQueue[E] extends AbstractQueue[E] with TransferQueue[E] with Serializable

    An unbounded TransferQueue based on linked nodes.

    An unbounded TransferQueue based on linked nodes. This queue orders elements FIFO (first-in-first-out) with respect to any given producer. The head of the queue is that element that has been on the queue the longest time for some producer. The tail of the queue is that element that has been on the queue the shortest time for some producer.

    Beware that, unlike in most collections, the size method is NOT a constant-time operation. Because of the asynchronous nature of these queues, determining the current number of elements requires a traversal of the elements, and so may report inaccurate results if this collection is modified during traversal. Additionally, the bulk operations addAll, removeAll, retainAll, containsAll, equals, and toArray are not guaranteed to be performed atomically. For example, an iterator operating concurrently with an addAll operation might view only some of the added elements.

    This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.

    Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a LinkedTransferQueue happen-before actions subsequent to the access or removal of that element from the LinkedTransferQueue in another thread.

    This class is a member of the Java Collections Framework.

    Since

    1.7

  5. abstract class RecursiveAction extends ForkJoinTask[Void]

    A recursive resultless ForkJoinTask.

    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:
      final static 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

  6. abstract class RecursiveTask[V] extends ForkJoinTask[V]

    A recursive result-bearing ForkJoinTask.

    A recursive result-bearing ForkJoinTask.

    For a classic example, here is a task computing Fibonacci numbers:

     
    class Fibonacci extends RecursiveTask {
      final int n;
      Fibonacci(int n) { this.n = n; 
      Integer compute() {
        if (n <= 1)
           return n;
        Fibonacci f1 = new Fibonacci(n - 1);
        f1.fork();
        Fibonacci f2 = new Fibonacci(n - 2);
        return f2.compute() + f1.join();
      }
    }}
    

    However, besides being a dumb way to compute Fibonacci functions (there is a simple fast linear algorithm that you'd use in practice), this is likely to perform poorly because the smallest subtasks are too small to be worthwhile splitting up. Instead, as is the case for nearly all fork/join applications, you'd pick some minimum granularity size (for example 10 here) for which you always sequentially solve rather than subdividing.

    Since

    1.7

  7. class ThreadLocalRandom extends Random

    A random number generator isolated to the current thread.

    A random number generator isolated to the current thread. Like the global java.util.Random generator used by the java.lang.Math class, a ThreadLocalRandom is initialized with an internally generated seed that may not otherwise be modified. When applicable, use of ThreadLocalRandom rather than shared Random objects in concurrent programs will typically encounter much less overhead and contention. Use of ThreadLocalRandom is particularly appropriate when multiple tasks (for example, each a ForkJoinTask) use random numbers in parallel in thread pools.

    Usages of this class should typically be of the form: ThreadLocalRandom.current().nextX(...) (where X is Int, Long, etc). When all usages are of this form, it is never possible to accidentally share a ThreadLocalRandom across multiple threads.

    This class also provides additional commonly used bounded random generation methods.

    Since

    1.7

  8. trait TransferQueue[E] extends BlockingQueue[E]

    A BlockingQueue in which producers may wait for consumers to receive elements.

    A BlockingQueue in which producers may wait for consumers to receive elements. A TransferQueue may be useful for example in message passing applications in which producers sometimes (using method #transfer) await receipt of elements by consumers invoking take or poll, while at other times enqueue elements (via method put) without waiting for receipt. Non-blocking and time-out versions of tryTransfer are also available. A TransferQueue may also be queried, via #hasWaitingConsumer, whether there are any threads waiting for items, which is a converse analogy to a peek operation.

    Like other blocking queues, a TransferQueue may be capacity bounded. If so, an attempted transfer operation may initially block waiting for available space, and/or subsequently block waiting for reception by a consumer. Note that in a queue with zero capacity, such as SynchronousQueue, put and transfer are effectively synonymous.

    This interface is a member of the Java Collections Framework.

    Since

    1.7

Ungrouped