--- jsr166/src/jsr166y/CountedCompleter.java 2012/04/21 11:45:20 1.2 +++ jsr166/src/jsr166y/CountedCompleter.java 2012/11/19 18:12:42 1.14 @@ -7,34 +7,52 @@ package jsr166y; /** - * A resultless {@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 + * 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 for + * ForkJoinTasks, but are in general 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 {@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 * #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. Because CountedCompleters provide only basic + * synchronization mechanisms, it may be useful to create further + * abstract subclasses that maintain linkages and fields and 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
@@ -48,14 +66,16 @@ 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.
*
* 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. Even though they entail a bit more
+ * 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
@@ -66,7 +86,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
@@ -75,19 +95,20 @@ 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):
+ *
+ * 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 of 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 {@code getRoot().quietlyComplete();}.
+ *
+ * @param rawResult the raw result
+ */
+ public void complete(T rawResult) {
+ CountedCompleter> p;
+ setRawResult(rawResult);
onCompletion(this);
quietlyComplete();
if ((p = completer) != null)
@@ -409,7 +516,7 @@ public abstract class CountedCompleter e
* Support for FJT exception propagation
*/
void internalPropagateException(Throwable ex) {
- CountedCompleter a = this, s = a;
+ CountedCompleter> a = this, s = a;
while (a.onExceptionalCompletion(ex, s) &&
(a = (s = a).completer) != null && a.status >= 0)
a.recordExceptionalCompletion(ex);
@@ -424,23 +531,28 @@ public abstract class CountedCompleter e
}
/**
- * Always returns {@code null}.
+ * 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.
*
- * @return {@code null} always
+ * @return the result of the computation
*/
- public final Void getRawResult() { return null; }
+ public T getRawResult() { return null; }
/**
- * Requires null completion value.
+ * A method that result-bearing CountedCompleters may optionally
+ * use to help maintain result data. By default, does nothing.
+ * If this method is overridden to update existing objects or
+ * fields, then it must in general be defined to be thread-safe.
*/
- protected final void setRawResult(Void mustBeNull) { }
+ protected void setRawResult(T t) { }
// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long PENDING;
static {
try {
- U = getUnsafe();
+ U = sun.misc.Unsafe.getUnsafe();
PENDING = U.objectFieldOffset
(CountedCompleter.class.getDeclaredField("pending"));
} catch (Exception e) {
@@ -448,7 +560,6 @@ public abstract class CountedCompleter e
}
}
-
/**
* Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package.
* Replace with a simple call to Unsafe.getUnsafe when integrating
@@ -476,5 +587,4 @@ public abstract class CountedCompleter e
}
}
}
-
}
{@code
* class MyOperation
{@code
* class ForEach
{@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. Asuuming 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 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 HeaderBuilder extends CountedCompleter { ... }
- * class BodyBuilder extends CountedCompleter { ... }
- * class PacketSender extends CountedCompleter {
+ * 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(); }
+ * public void onCompletion(CountedCompleter> caller) { sendPacket(); }
* }
* // sample use:
* PacketSender p = new PacketSender();
@@ -239,11 +322,11 @@ package jsr166y;
* @since 1.8
* @author Doug Lea
*/
-public abstract class CountedCompleter extends ForkJoinTask