A concrete CountedCompleter class must define method {@link * #compute}, that should in most cases (as illustrated below), invoke * {@code tryComplete()} once before returning. The class may also * optionally override method {@link #onCompletion(CountedCompleter)} * to perform an action upon normal completion, and method * {@link #onExceptionalCompletion(Throwable, CountedCompleter)} to * perform an action upon any exception. * *
CountedCompleters most often do not bear results, in which case
* they are normally declared as {@code CountedCompleter A CountedCompleter that does not itself have a completer (i.e.,
* one for which {@link #getCompleter} returns {@code null}) can be
* used as a regular ForkJoinTask with this added functionality.
* However, any completer that in turn has another completer serves
* only as an internal helper for other computations, so its own task
* status (as reported in methods such as {@link ForkJoinTask#isDone})
* is arbitrary; this status changes only upon explicit invocations of
* {@link #complete}, {@link ForkJoinTask#cancel},
* {@link ForkJoinTask#completeExceptionally(Throwable)} or upon
* exceptional completion of method {@code compute}. Upon any
* exceptional completion, the exception may be relayed to a task's
* completer (and its completer, and so on), if one exists and it has
* not otherwise already completed. Similarly, cancelling an internal
* CountedCompleter has only a local effect on that completer, so is
* not often useful.
*
* Sample Usages.
*
* Parallel recursive decomposition. CountedCompleters may
* be arranged in trees similar to those often used with {@link
* RecursiveAction}s, although the constructions involved in setting
* them up typically vary. Here, the completer of each task is its
* parent in the computation tree. Even though they entail a bit more
* bookkeeping, CountedCompleters may be better choices when applying
* a possibly time-consuming operation (that cannot be further
* subdivided) to each element of an array or collection; especially
* when the operation takes a significantly different amount of time
* to complete for some elements than others, either because of
* intrinsic variation (for example I/O) or auxiliary effects such as
* garbage collection. Because CountedCompleters provide their own
* continuations, other tasks need not block waiting to perform them.
*
* For example, here is an initial version of a utility method that
* uses divide-by-two recursive decomposition to divide work into
* single pieces (leaf tasks). Even when work is split into individual
* calls, tree-based techniques are usually preferable to directly
* forking leaf tasks, because they reduce inter-thread communication
* and improve load balancing. In the recursive case, the second of
* each pair of subtasks to finish triggers completion of their parent
* (because no result combination is performed, the default no-op
* implementation of method {@code onCompletion} is not overridden).
* The utility method sets up the root task and invokes it (here,
* implicitly using the {@link ForkJoinPool#commonPool()}). It is
* straightforward and reliable (but not optimal) to always set the
* pending count to the number of child tasks and call {@code
* tryComplete()} immediately before returning.
*
* Searching. A tree of CountedCompleters can search for a
* value or property in different parts of a data structure, and
* report a result in an {@link
* java.util.concurrent.atomic.AtomicReference AtomicReference} as
* soon as one is found. The others can poll the result to avoid
* unnecessary work. (You could additionally {@linkplain #cancel
* cancel} other tasks, but it is usually simpler and more efficient
* to just let them notice that the result is set and if so skip
* further processing.) Illustrating again with an array using full
* partitioning (again, in practice, leaf tasks will almost always
* process more than one element):
*
* Recording subtasks. CountedCompleter tasks that combine
* results of multiple subtasks usually need to access these results
* in method {@link #onCompletion(CountedCompleter)}. As illustrated in the following
* class (that performs a simplified form of map-reduce where mappings
* and reductions are all of type {@code E}), one way to do this in
* divide and conquer designs is to have each subtask record its
* sibling, so that it can be accessed in method {@code onCompletion}.
* This technique applies to reductions in which the order of
* combining left and right results does not matter; ordered
* reductions require explicit left/right designations. Variants of
* other streamlinings seen in the above examples may also apply.
*
* Completion Traversals. If using {@code onCompletion} to
* process completions is inapplicable or inconvenient, you can use
* methods {@link #firstComplete} and {@link #nextComplete} to create
* custom traversals. For example, to define a MapReducer that only
* splits out right-hand tasks in the form of the third ForEach
* example, the completions must cooperatively reduce along
* unexhausted subtask links, which can be done as follows:
*
* Triggers. Some CountedCompleters are themselves never
* forked, but instead serve as bits of plumbing in other designs;
* including those in which the completion of one or more async tasks
* triggers another async task. For example:
*
* This method may be useful when forcing completion as soon as
* any one (versus all) of several subtask results are obtained.
* However, in the common (and recommended) case in which {@code
* setRawResult} is not overridden, this effect can be obtained
* more simply using {@link #quietlyCompleteRoot()}.
*
* @param rawResult the raw result
*/
public void complete(T rawResult) {
CountedCompleter p;
setRawResult(rawResult);
onCompletion(this);
quietlyComplete();
if ((p = completer) != null)
p.tryComplete();
}
/**
* If this task's pending count is zero, returns this task;
* otherwise decrements its pending count and returns {@code null}.
* This method is designed to be used with {@link #nextComplete} in
* completion traversal loops.
*
* @return this task, if pending count was zero, else {@code null}
*/
public final CountedCompleter firstComplete() {
for (int c;;) {
if ((c = pending) == 0)
return this;
else if (weakCompareAndSetPendingCount(c, c - 1))
return null;
}
}
/**
* If this task does not have a completer, invokes {@link
* ForkJoinTask#quietlyComplete} and returns {@code null}. Or, if
* the completer's pending count is non-zero, decrements that
* pending count and returns {@code null}. Otherwise, returns the
* completer. This method can be used as part of a completion
* traversal loop for homogeneous task hierarchies:
*
* {@code
* public static
*
* This design can be improved by noticing that in the recursive case,
* the task has nothing to do after forking its right task, so can
* directly invoke its left task before returning. (This is an analog
* of tail recursion removal.) Also, when the last action in a task
* is to fork or invoke a subtask (a "tail call"), the call to {@code
* tryComplete()} can be optimized away, at the cost of making the
* pending count look "off by one".
*
* {@code
* public void compute() {
* if (hi - lo >= 2) {
* int mid = (lo + hi) >>> 1;
* setPendingCount(1); // looks off by one, but correct!
* new Task(this, mid, hi).fork(); // right child
* new Task(this, lo, mid).compute(); // direct invoke
* } else {
* if (hi > lo)
* action.accept(array[lo]);
* tryComplete();
* }
* }}
*
* As a further optimization, notice that the left task need not even exist.
* Instead of creating a new one, we can continue using the original task,
* and add a pending count for each fork. Additionally, because no task
* in this tree implements an {@link #onCompletion(CountedCompleter)} method,
* {@code tryComplete} can be replaced with {@link #propagateCompletion}.
*
* {@code
* public void compute() {
* int n = hi - lo;
* for (; n >= 2; n /= 2) {
* addToPendingCount(1);
* new Task(this, lo + n/2, lo + n).fork();
* }
* if (n > 0)
* action.accept(array[lo]);
* propagateCompletion();
* }}
*
* When pending counts can be precomputed, they can be established in
* the constructor:
*
* {@code
* public static
*
* Additional optimizations of such classes might entail specializing
* classes for leaf steps, subdividing by say, four, instead of two
* per iteration, and using an adaptive threshold instead of always
* subdividing down to single elements.
*
* {@code
* class Searcher
*
* In this example, as well as others in which tasks have no other
* effects except to {@code compareAndSet} a common result, the
* trailing unconditional invocation of {@code tryComplete} could be
* made conditional ({@code if (result.get() == null) tryComplete();})
* because no further bookkeeping is required to manage completions
* once the root task completes.
*
* {@code
* class MyMapper
*
* Here, method {@code onCompletion} takes a form common to many
* completion designs that combine results. This callback-style method
* is triggered once per task, in either of the two different contexts
* in which the pending count is, or becomes, zero: (1) by a task
* itself, if its pending count is zero upon invocation of {@code
* tryComplete}, or (2) by any of its subtasks when they complete and
* decrement the pending count to zero. The {@code caller} argument
* distinguishes cases. Most often, when the caller is {@code this},
* no action is necessary. Otherwise the caller argument can be used
* (usually via a cast) to supply a value (and/or links to other
* values) to be combined. Assuming proper use of pending counts, the
* actions inside {@code onCompletion} occur (once) upon completion of
* a task and its subtasks. No additional synchronization is required
* within this method to ensure thread safety of accesses to fields of
* this task or other completed tasks.
*
* {@code
* class MapReducer
*
* {@code
* class HeaderBuilder extends CountedCompleter<...> { ... }
* class BodyBuilder extends CountedCompleter<...> { ... }
* class PacketSender extends CountedCompleter<...> {
* PacketSender(...) { super(null, 1); ... } // trigger on second completion
* public void compute() { } // never called
* public void onCompletion(CountedCompleter caller) { sendPacket(); }
* }
* // sample use:
* PacketSender p = new PacketSender();
* new HeaderBuilder(p, ...).fork();
* new BodyBuilder(p, ...).fork();}
*
* @since 1.8
* @author Doug Lea
*/
public abstract class CountedCompleter {@code
* for (CountedCompleter c = firstComplete();
* c != null;
* c = c.nextComplete()) {
* // ... process c ...
* }}
*
* @return the completer, or {@code null} if none
*/
public final CountedCompleter nextComplete() {
CountedCompleter p;
if ((p = completer) != null)
return p.firstComplete();
else {
quietlyComplete();
return null;
}
}
/**
* Equivalent to {@code getRoot().quietlyComplete()}.
*/
public final void quietlyCompleteRoot() {
for (CountedCompleter a = this, p;;) {
if ((p = a.completer) == null) {
a.quietlyComplete();
return;
}
a = p;
}
}
/**
* If this task has not completed, attempts to process at most the
* given number of other unprocessed tasks for which this task is
* on the completion path, if any are known to exist.
*
* @param maxTasks the maximum number of tasks to process. If
* less than or equal to zero, then no tasks are
* processed.
*/
public final void helpComplete(int maxTasks) {
ForkJoinPool.WorkQueue q; Thread t; boolean owned;
if (owned = (t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
q = ((ForkJoinWorkerThread)t).workQueue;
else
q = ForkJoinPool.commonQueue();
if (q != null && maxTasks > 0)
q.helpComplete(this, owned, maxTasks);
}
// ForkJoinTask overrides
/**
* Supports ForkJoinTask exception propagation.
*/
@Override
final int trySetException(Throwable ex) {
CountedCompleter a = this, p = a;
do {} while (isExceptionalStatus(a.trySetThrown(ex)) &&
a.onExceptionalCompletion(ex, p) &&
(a = (p = a).completer) != null && a.status >= 0);
return status;
}
/**
* Implements execution conventions for CountedCompleters.
*/
@Override
protected final boolean exec() {
compute();
return false;
}
/**
* Returns the result of the computation. By default,
* returns {@code null}, which is appropriate for {@code Void}
* actions, but in other cases should be overridden, almost
* always to return a field or function of a field that
* holds the result upon completion.
*
* @return the result of the computation
*/
@Override
public T getRawResult() { return null; }
/**
* A method that result-bearing CountedCompleters may optionally
* use to help maintain result data. By default, does nothing.
* Overrides are not recommended. However, if this method is
* overridden to update existing objects or fields, then it must
* in general be defined to be thread-safe.
*/
@Override
protected void setRawResult(T t) { }
// VarHandle mechanics
private static final VarHandle PENDING;
static {
try {
MethodHandles.Lookup l = MethodHandles.lookup();
PENDING = l.findVarHandle(CountedCompleter.class, "pending", int.class);
} catch (ReflectiveOperationException e) {
throw new ExceptionInInitializerError(e);
}
}
}