CountedCompleter

public abstract class CountedCompleter
extends ForkJoinTask<T>

A ForkJoinTask with a completion action performed when triggered and there are no remaining pending actions. CountedCompleters are in general more robust in the presence of subtask stalls and blockage than are other forms of ForkJoinTasks, but are less intuitive to program. Uses of CountedCompleter are similar to those of other completion based components except that multiple pending completions may be necessary to trigger the completion action onCompletion(CountedCompleter), not just one. Unless initialized otherwise, the pending count starts at zero, but may be (atomically) changed using methods setPendingCount(int), addToPendingCount(int), and compareAndSetPendingCount(int, int). Upon invocation of tryComplete(), if the pending action count is nonzero, it is decremented; otherwise, the completion action is performed, and if this completer itself has a completer, the process is continued with its completer. As is the case with related synchronization components such as Phaser and Semaphore, these methods affect only internal counts; they do not establish any further internal bookkeeping. In particular, the identities of pending tasks are not maintained. As illustrated below, you can create subclasses that do record some or all pending tasks or their results when needed. As illustrated below, utility methods supporting customization of completion traversals are also provided. However, because CountedCompleters provide only basic synchronization mechanisms, it may be useful to create further abstract subclasses that maintain linkages, fields, and additional support methods appropriate for a set of related usages.

A concrete CountedCompleter class must define method compute(), that should in most cases (as illustrated below), invoke tryComplete() once before returning. The class may also optionally override method onCompletion(CountedCompleter) to perform an action upon normal completion, and method 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 CountedCompleter<Void>, and will always return null as a result value. In other cases, you should override method getRawResult() to provide a result from join(), invoke(), and related methods. In general, this method should return the value of a field (or a function of one or more fields) of the CountedCompleter object that holds the result upon completion. Method setRawResult(T) by default plays no role in CountedCompleters. It is possible, but rarely applicable, to override this method to maintain other objects or fields holding result data.

A CountedCompleter that does not itself have a completer (i.e., one for which getCompleter() returns 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 isDone()) is arbitrary; this status changes only upon explicit invocations of complete(T), cancel(boolean), completeExceptionally(Throwable) or upon exceptional completion of method 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 RecursiveActions, 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 threads need not block waiting to perform them.

For example, here is an initial version of a class 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 its parent (because no result combination is performed, the default no-op implementation of method onCompletion is not overridden). A static utility method sets up the base task and invokes it (here, implicitly using the commonPool()).

 class MyOperation<E> { void apply(E e) { ... }  }

 class ForEach<E> extends CountedCompleter<Void> {

   public static <E> void forEach(E[] array, MyOperation<E> op) {
     new ForEach<E>(null, array, op, 0, array.length).invoke();
   }

   final E[] array; final MyOperation<E> op; final int lo, hi;
   ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) {
     super(p);
     this.array = array; this.op = op; this.lo = lo; this.hi = hi;
   }

   public void compute() { // version 1
     if (hi - lo >= 2) {
       int mid = (lo + hi) >>> 1;
       setPendingCount(2); // must set pending count before fork
       new ForEach(this, array, op, mid, hi).fork(); // right child
       new ForEach(this, array, op, lo, mid).fork(); // left child
     }
     else if (hi > lo)
       op.apply(array[lo]);
     tryComplete();
   }
 }

 class ForEach<E> ... {
   ...
   public void compute() { // version 2
     if (hi - lo >= 2) {
       int mid = (lo + hi) >>> 1;
       setPendingCount(1); // only one pending
       new ForEach(this, array, op, mid, hi).fork(); // right child
       new ForEach(this, array, op, lo, mid).compute(); // direct invoke
     }
     else {
       if (hi > lo)
         op.apply(array[lo]);
       tryComplete();
     }
   }
 }

 class ForEach<E> ... {
   ...
   public void compute() { // version 3
     int l = lo, h = hi;
     while (h - l >= 2) {
       int mid = (l + h) >>> 1;
       addToPendingCount(1);
       new ForEach(this, array, op, mid, h).fork(); // right child
       h = mid;
     }
     if (h > l)
       op.apply(array[l]);
     propagateCompletion();
   }
 }

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 AtomicReference as soon as one is found. The others can poll the result to avoid unnecessary work. (You could additionally 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):

 class Searcher<E> extends CountedCompleter<E> {
   final E[] array; final AtomicReference<E> result; final int lo, hi;
   Searcher(CountedCompleter<?> p, E[] array, AtomicReference<E> result, int lo, int hi) {
     super(p);
     this.array = array; this.result = result; this.lo = lo; this.hi = hi;
   }
   public E getRawResult() { return result.get(); }
   public void compute() { // similar to ForEach version 3
     int l = lo, h = hi;
     while (result.get() == null && h >= l) {
       if (h - l >= 2) {
         int mid = (l + h) >>> 1;
         addToPendingCount(1);
         new Searcher(this, array, result, mid, h).fork();
         h = mid;
       }
       else {
         E x = array[l];
         if (matches(x) && result.compareAndSet(null, x))
           quietlyCompleteRoot(); // root task is now joinable
         break;
       }
     }
     tryComplete(); // normally complete whether or not found
   }
   boolean matches(E e) { ... } // return true if found

   public static <E> E search(E[] array) {
       return new Searcher<E>(null, array, new AtomicReference<E>(), 0, array.length).invoke();
   }
 }

Recording subtasks. CountedCompleter tasks that combine results of multiple subtasks usually need to access these results in method onCompletion(CountedCompleter). As illustrated in the following class (that performs a simplified form of map-reduce where mappings and reductions are all of type 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 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.

 class MyMapper<E> { E apply(E v) {  ...  } }
 class MyReducer<E> { E apply(E x, E y) {  ...  } }
 class MapReducer<E> extends CountedCompleter<E> {
   final E[] array; final MyMapper<E> mapper;
   final MyReducer<E> reducer; final int lo, hi;
   MapReducer<E> sibling;
   E result;
   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
              MyReducer<E> reducer, int lo, int hi) {
     super(p);
     this.array = array; this.mapper = mapper;
     this.reducer = reducer; this.lo = lo; this.hi = hi;
   }
   public void compute() {
     if (hi - lo >= 2) {
       int mid = (lo + hi) >>> 1;
       MapReducer<E> left = new MapReducer(this, array, mapper, reducer, lo, mid);
       MapReducer<E> right = new MapReducer(this, array, mapper, reducer, mid, hi);
       left.sibling = right;
       right.sibling = left;
       setPendingCount(1); // only right is pending
       right.fork();
       left.compute();     // directly execute left
     }
     else {
       if (hi > lo)
           result = mapper.apply(array[lo]);
       tryComplete();
     }
   }
   public void onCompletion(CountedCompleter<?> caller) {
     if (caller != this) {
       MapReducer<E> child = (MapReducer<E>)caller;
       MapReducer<E> sib = child.sibling;
       if (sib == null || sib.result == null)
         result = child.result;
       else
         result = reducer.apply(child.result, sib.result);
     }
   }
   public E getRawResult() { return result; }

   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
     return new MapReducer<E>(null, array, mapper, reducer,
                              0, array.length).invoke();
   }
 }

Completion Traversals. If using onCompletion to process completions is inapplicable or inconvenient, you can use methods firstComplete() and 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:

 class MapReducer<E> extends CountedCompleter<E> { // version 2
   final E[] array; final MyMapper<E> mapper;
   final MyReducer<E> reducer; final int lo, hi;
   MapReducer<E> forks, next; // record subtask forks in list
   E result;
   MapReducer(CountedCompleter<?> p, E[] array, MyMapper<E> mapper,
              MyReducer<E> reducer, int lo, int hi, MapReducer<E> next) {
     super(p);
     this.array = array; this.mapper = mapper;
     this.reducer = reducer; this.lo = lo; this.hi = hi;
     this.next = next;
   }
   public void compute() {
     int l = lo, h = hi;
     while (h - l >= 2) {
       int mid = (l + h) >>> 1;
       addToPendingCount(1);
       (forks = new MapReducer(this, array, mapper, reducer, mid, h, forks)).fork();
       h = mid;
     }
     if (h > l)
       result = mapper.apply(array[l]);
     // process completions by reducing along and advancing subtask links
     for (CountedCompleter<?> c = firstComplete(); c != null; c = c.nextComplete()) {
       for (MapReducer t = (MapReducer)c, s = t.forks; s != null; s = t.forks = s.next)
         t.result = reducer.apply(t.result, s.result);
     }
   }
   public E getRawResult() { return result; }

   public static <E> E mapReduce(E[] array, MyMapper<E> mapper, MyReducer<E> reducer) {
     return new MapReducer<E>(null, array, mapper, reducer,
                              0, array.length, null).invoke();
   }
 }

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:

 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();

Summary

Inherited methods
From class java.util.concurrent.ForkJoinTask 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(). 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. 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(T 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<T> fork() Arranges to asynchronously execute this task in the pool the current task is running in, if applicable, or using the commonPool() if not inForkJoinPool(). final T 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 T 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. 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. abstract T 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 T 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...<?> 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. 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. 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 T 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 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. void reinitialize() Resets the internal bookkeeping state of this task, allowing a subsequent fork. final short setForkJoinTaskTag(short newValue) Atomically sets the tag value for this task and returns the old value. abstract void setRawResult(T 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 obj) Indicates whether some other object is "equal to" this one. void finalize() Called by the garbage collector on an object when garbage collection determines that there are no more references to the object. final Class<?> getClass() Returns the runtime class of this Object. int hashCode() Returns a hash code value for the object. final void notify() Wakes up a single thread that is waiting on this object's monitor. final void notifyAll() Wakes up all threads that are waiting on this object's monitor. String toString() Returns a string representation of the object. final void wait(long millis, int nanos) Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed. final void wait(long millis) Causes the current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object, or a specified amount of time has elapsed. final void wait() Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
From interface java.util.concurrent.Future abstract boolean cancel(boolean mayInterruptIfRunning) Attempts to cancel execution of this task. abstract T 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 T get() Waits if necessary for the computation to complete, and then retrieves its result. abstract boolean isCancelled() Returns true if this task was cancelled before it completed normally. abstract boolean isDone() Returns true if this task completed.

Protected constructors

CountedCompleter (CountedCompleter<?> completer, 
                int initialPendingCount)

CountedCompleter (CountedCompleter<?> completer)

CountedCompleter ()

Public methods

void addToPendingCount (int delta)

boolean compareAndSetPendingCount (int expected, 
                int count)

void complete (T rawResult)

void compute ()

int decrementPendingCountUnlessZero ()

CountedCompleter<?> firstComplete ()

CountedCompleter<?> getCompleter ()

int getPendingCount ()

T getRawResult ()

CountedCompleter<?> getRoot ()

void helpComplete (int maxTasks)

CountedCompleter<?> nextComplete ()

 for (CountedCompleter<?> c = firstComplete();
      c != null;
      c = c.nextComplete()) {
   // ... process c ...
 }

void onCompletion (CountedCompleter<?> caller)

boolean onExceptionalCompletion (Throwable ex, 
                CountedCompleter<?> caller)

void propagateCompletion ()

void quietlyCompleteRoot ()

void setPendingCount (int count)

void tryComplete ()

Protected methods

boolean exec ()

void setRawResult (T t)