package forkjoin
Type Members
-
class
ForkJoinPool extends AbstractExecutorService
An
ExecutorService
for runningForkJoinTask
s.An
ExecutorService
for runningForkJoinTask
s. AForkJoinPool
provides the entry point for submissions from non-ForkJoinTask
clients, as well as management and monitoring operations.A
ForkJoinPool
differs from other kinds ofExecutorService
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 mostForkJoinTask
s), as well as when many small tasks are submitted to the pool from external clients. Especially when setting asyncMode to true in constructors,ForkJoinPool
s 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 nestedManagedBlocker
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 plainRunnable
- orCallable
- 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) java.util.concurrent.ForkJoinPool.common
:parallelism
-- an integer greater than zero,threadFactory
-- the class name of a `[[ForkJoinWorkerThreadFactory]]`, andexceptionHandler
-- 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 inIllegalArgumentException
. 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
-
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
. AForkJoinTask
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 aForkJoinPool
, or, if not already engaged in a ForkJoin computation, commenced in theForkJoinPool#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 usingForkJoinTask
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 ofFuture
. The efficiency ofForkJoinTask
s 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 avoidsynchronized
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 asIOExceptions
to be thrown. However, computations may still encounter unchecked exceptions, that are rethrown to callers attempting to join them. These exceptions may additionally includeRejectedExecutionException
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 usingex.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 theForkJoinPool.ManagedBlocker
API is used, or the number of possibly blocked tasks is known to be less than the pool'sForkJoinPool#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: TheFuture#get
methods support interruptible and/or timed waits for completion and report results usingFuture
conventions. Method#invoke
is semantically equivalent tofork(); 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. MethodinvokeAll
(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 joininga
beforeb
.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 ajava.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 orjava.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, andCountedCompleter
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 acompute
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 ofPhaser
,#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 ashort
value using#setForkJoinTaskTag
or#compareAndSetForkJoinTaskTag
and checked using#getForkJoinTaskTag
. The ForkJoinTask implementation does not use theseprotected
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 implementprotected
methods#exec
,#setRawResult
, and#getRawResult
, while also introducing an abstract computational method that can be implemented in its subclasses, possibly relying on otherprotected
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 forRunnable
andCallable
, that may be of use when mixing execution ofForkJoinTasks
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
-
class
ForkJoinWorkerThread extends Thread
A thread managed by a
ForkJoinPool
, which executesForkJoinTask
s.A thread managed by a
ForkJoinPool
, which executesForkJoinTask
s. 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 customForkJoinPool.ForkJoinWorkerThreadFactory
to use it in aForkJoinPool
.- Since
1.7
-
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 operationsaddAll
,removeAll
,retainAll
,containsAll
,equals
, andtoArray
are not guaranteed to be performed atomically. For example, an iterator operating concurrently with anaddAll
operation might view only some of the added elements.This class and its iterator implement all of the optional methods of the
Collection
andIterator
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 theLinkedTransferQueue
in another thread.This class is a member of the Java Collections Framework.
- Since
1.7
-
abstract
class
RecursiveAction extends ForkJoinTask[Void]
A recursive resultless
ForkJoinTask
.A recursive resultless
ForkJoinTask
. This class establishes conventions to parameterize resultless actions asVoid
ForkJoinTask
s. Becausenull
is the only valid value of typeVoid
, methods such asjoin
always returnnull
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 creatingnew 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 methodgetSurplusQueuedTaskCount
, 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
-
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
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(); } }}{ final int n; Fibonacci(int n) { this.n = n; 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
-
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 thejava.lang.Math
class, aThreadLocalRandom
is initialized with an internally generated seed that may not otherwise be modified. When applicable, use ofThreadLocalRandom
rather than sharedRandom
objects in concurrent programs will typically encounter much less overhead and contention. Use ofThreadLocalRandom
is particularly appropriate when multiple tasks (for example, each aForkJoinTask
) use random numbers in parallel in thread pools.Usages of this class should typically be of the form:
ThreadLocalRandom.current().nextX(...)
(whereX
isInt
,Long
, etc). When all usages are of this form, it is never possible to accidentally share aThreadLocalRandom
across multiple threads.This class also provides additional commonly used bounded random generation methods.
- Since
1.7
-
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. ATransferQueue
may be useful for example in message passing applications in which producers sometimes (using method#transfer
) await receipt of elements by consumers invokingtake
orpoll
, while at other times enqueue elements (via methodput
) without waiting for receipt. Non-blocking and time-out versions oftryTransfer
are also available. ATransferQueue
may also be queried, via#hasWaitingConsumer
, whether there are any threads waiting for items, which is a converse analogy to apeek
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 asSynchronousQueue
,put
andtransfer
are effectively synonymous.This interface is a member of the Java Collections Framework.
- Since
1.7