--- jsr166/src/jsr166y/CountedCompleter.java 2012/08/16 12:25:03 1.3 +++ jsr166/src/jsr166y/CountedCompleter.java 2012/11/26 05:55:05 1.25 @@ -7,43 +7,54 @@ package jsr166y; /** - * A {@link ForkJoinTask} with a completion action - * performed when triggered and there are no remaining pending - * actions. Uses of CountedCompleter are similar to those of other - * completion based components (such as {@link - * java.nio.channels.CompletionHandler}) except that multiple - * pending completions may be necessary to trigger the {@link - * #onCompletion} action, not just one. Unless initialized otherwise, - * the {@link #getPendingCount pending count} starts at zero, but may - * be (atomically) changed using methods {@link #setPendingCount}, - * {@link #addToPendingCount}, and {@link - * #compareAndSetPendingCount}. Upon invocation of {@link + * A {@link 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 (such as {@link java.nio.channels.CompletionHandler}) + * except that multiple pending completions may be necessary + * to trigger the completion action {@link #onCompletion}, not just one. + * Unless initialized otherwise, the {@linkplain #getPendingCount pending + * count} starts at zero, but may be (atomically) changed using + * methods {@link #setPendingCount}, {@link #addToPendingCount}, and + * {@link #compareAndSetPendingCount}. Upon invocation of {@link * #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 {@link Phaser} and {@link - * java.util.concurrent.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 pended tasks or their results when needed. + * components such as {@link java.util.concurrent.Phaser Phaser} and + * {@link java.util.concurrent.Semaphore 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 {@link - * #compute}, that should, in almost all use cases, invoke {@code - * tryComplete()} once before returning. The class may also optionally - * override method {@link #onCompletion} to perform an action upon - * normal completion, and method {@link #onExceptionalCompletion} to - * perform an action upon any exception. + * #compute}, that should in most cases (as illustrated below), invoke + * {@code tryComplete()} once before returning. The class may also + * optionally override method {@link #onCompletion} to perform an + * action upon normal completion, and method {@link + * #onExceptionalCompletion} 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
@@ -57,7 +68,8 @@ package jsr166y;
* 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.
+ * completed. Similarly, cancelling an internal CountedCompleter has
+ * only a local effect on that completer, so is not often useful.
*
* Sample Usages.
*
@@ -76,7 +88,7 @@ package jsr166y;
* continuations, other threads need not block waiting to perform
* them.
*
- * For example, here is an initial version of a class that uses
+ * 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
@@ -85,78 +97,82 @@ package jsr166y;
* pair of subtasks to finish triggers completion of its parent
* (because no result combination is performed, the default no-op
* implementation of method {@code onCompletion} is not overridden). A
- * static utility method sets up the base task and invokes it:
+ * static utility method sets up the base task and invokes it
+ * (here, implicitly using the {@link ForkJoinPool#commonPool()}).
*
* 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.AtomicReference}
+ * as soon as one is found. The others can poll the result to avoid
+ * unnecessary work. (You could additionally {@link #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}. As illustrated in the following
@@ -181,51 +248,111 @@ package jsr166y;
* class MyMapper 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;
@@ -236,9 +363,9 @@ package jsr166y;
* 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(); }
+ * 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();
@@ -261,7 +388,7 @@ public abstract class CountedCompleter 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 {@code quietlyCompleteRoot();}.
*
* @param rawResult the raw result
*/
public void complete(T rawResult) {
CountedCompleter> p;
- onCompletion(this);
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 (U.compareAndSwapInt(this, PENDING, c, c - 1))
+ return null;
+ }
+ }
+
+ /**
+ * If this task does not have a completer, invokes {@link
+ * ForkJoinTask#quietlyComplete} and returns {@code null}. Or, if
+ * this task's pending count is non-zero, decrements its 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
* class MyOperation
+ * else if (hi > lo)
+ * op.apply(array[lo]);
+ * tryComplete();
+ * }
+ * }}
*
* 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, because the task returns upon
* executing its left task (rather than falling through to invoke
- * tryComplete) the pending count is set to one:
+ * {@code tryComplete}) the pending count is set to one:
*
* {@code
* class ForEach
*
* As a further improvement, notice that the left task need not even
* exist. Instead of creating a new one, we can iterate using the
- * original task, and add a pending count for each fork:
+ * original task, and add a pending count for each fork. Additionally,
+ * because no task in this tree implements an {@link #onCompletion}
+ * method, {@code tryComplete()} can be replaced with {@link
+ * #propagateCompletion}.
*
* {@code
* class ForEach
*
* Additional improvements of such classes might entail precomputing
@@ -165,6 +181,57 @@ package jsr166y;
* 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 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 MapReducer
+ * 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 {@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;
+ }
+ }
+
/**
- * Support for FJT exception propagation
+ * Supports ForkJoinTask exception propagation.
*/
void internalPropagateException(Throwable ex) {
CountedCompleter> a = this, s = a;
@@ -429,7 +671,7 @@ public abstract class CountedCompleter