ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166y/RecursiveAction.java
(Generate patch)

Comparing jsr166/src/jsr166y/RecursiveAction.java (file contents):
Revision 1.2 by jsr166, Mon Jul 20 21:45:06 2009 UTC vs.
Revision 1.18 by jsr166, Sat Jun 25 03:25:00 2011 UTC

# Line 1 | Line 1
1   /*
2   * Written by Doug Lea with assistance from members of JCP JSR-166
3   * Expert Group and released to the public domain, as explained at
4 < * http://creativecommons.org/licenses/publicdomain
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7   package jsr166y;
8  
9   /**
10 < * Recursive resultless ForkJoinTasks. This class establishes
11 < * conventions to parameterize resultless actions as <tt>Void</tt>
12 < * ForkJoinTasks. Because <tt>null</tt> is the only valid value of
13 < * <tt>Void</tt>, methods such as join always return <tt>null</tt>
14 < * upon completion.
10 > * A recursive resultless {@link ForkJoinTask}.  This class
11 > * establishes conventions to parameterize resultless actions as
12 > * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the
13 > * only valid value of type {@code Void}, methods such as {@code join}
14 > * always return {@code null} upon completion.
15   *
16   * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that
17 < * sorts a given <tt>long[]</tt> array:
17 > * sorts a given {@code long[]} array:
18   *
19 < * <pre>
19 > *  <pre> {@code
20   * class SortTask extends RecursiveAction {
21 < *   final long[] array; final int lo; final int hi;
21 > *   final long[] array; final int lo, hi;
22   *   SortTask(long[] array, int lo, int hi) {
23   *     this.array = array; this.lo = lo; this.hi = hi;
24   *   }
25   *   protected void compute() {
26 < *     if (hi - lo &lt; THRESHOLD)
26 > *     if (hi - lo < THRESHOLD)
27   *       sequentiallySort(array, lo, hi);
28   *     else {
29 < *       int mid = (lo + hi) &gt;&gt;&gt; 1;
29 > *       int mid = (lo + hi) >>> 1;
30   *       invokeAll(new SortTask(array, lo, mid),
31   *                 new SortTask(array, mid, hi));
32 < *       merge(array, lo, hi);
32 > *       merge(array, lo, mid, hi);
33   *     }
34   *   }
35 < * }
36 < * </pre>
35 > * }}</pre>
36   *
37 < * You could then sort anArray by creating <tt>new SortTask(anArray, 0,
38 < * anArray.length-1) </tt> and invoking it in a ForkJoinPool.
39 < * As a more concrete simple example, the following task increments
40 < * each element of an array:
41 < * <pre>
37 > * You could then sort {@code anArray} by creating {@code new
38 > * SortTask(anArray, 0, anArray.length) } and invoking it in a
39 > * ForkJoinPool.  As a more concrete simple example, the following
40 > * task increments each element of an array:
41 > *  <pre> {@code
42   * class IncrementTask extends RecursiveAction {
43 < *   final long[] array; final int lo; final int hi;
43 > *   final long[] array; final int lo, hi;
44   *   IncrementTask(long[] array, int lo, int hi) {
45   *     this.array = array; this.lo = lo; this.hi = hi;
46   *   }
47   *   protected void compute() {
48 < *     if (hi - lo &lt; THRESHOLD) {
49 < *       for (int i = lo; i &lt; hi; ++i)
48 > *     if (hi - lo < THRESHOLD) {
49 > *       for (int i = lo; i < hi; ++i)
50   *         array[i]++;
51   *     }
52   *     else {
53 < *       int mid = (lo + hi) &gt;&gt;&gt; 1;
53 > *       int mid = (lo + hi) >>> 1;
54   *       invokeAll(new IncrementTask(array, lo, mid),
55   *                 new IncrementTask(array, mid, hi));
56   *     }
57   *   }
58 < * }
60 < * </pre>
61 < *
58 > * }}</pre>
59   *
60   * <p>The following example illustrates some refinements and idioms
61   * that may lead to better performance: RecursiveActions need not be
# Line 66 | Line 63 | package jsr166y;
63   * divide-and-conquer approach. Here is a class that sums the squares
64   * of each element of a double array, by subdividing out only the
65   * right-hand-sides of repeated divisions by two, and keeping track of
66 < * them with a chain of <tt>next</tt> references. It uses a dynamic
67 < * threshold based on method <tt>surplus</tt>, but counterbalances
68 < * potential excess partitioning by directly performing leaf actions
69 < * on unstolen tasks rather than further subdividing.
66 > * them with a chain of {@code next} references. It uses a dynamic
67 > * threshold based on method {@code getSurplusQueuedTaskCount}, but
68 > * counterbalances potential excess partitioning by directly
69 > * performing leaf actions on unstolen tasks rather than further
70 > * subdividing.
71   *
72 < * <pre>
72 > *  <pre> {@code
73   * double sumOfSquares(ForkJoinPool pool, double[] array) {
74   *   int n = array.length;
75 < *   int seqSize = 1 + n / (8 * pool.getParallelism());
78 < *   Applyer a = new Applyer(array, 0, n, seqSize, null);
75 > *   Applyer a = new Applyer(array, 0, n, null);
76   *   pool.invoke(a);
77   *   return a.result;
78   * }
79   *
80   * class Applyer extends RecursiveAction {
81   *   final double[] array;
82 < *   final int lo, hi, seqSize;
82 > *   final int lo, hi;
83   *   double result;
84   *   Applyer next; // keeps track of right-hand-side tasks
85 < *   Applyer(double[] array, int lo, int hi, int seqSize, Applyer next) {
85 > *   Applyer(double[] array, int lo, int hi, Applyer next) {
86   *     this.array = array; this.lo = lo; this.hi = hi;
87 < *     this.seqSize = seqSize; this.next = next;
87 > *     this.next = next;
88   *   }
89   *
90 < *   double atLeaf(int l, int r) {
90 > *   double atLeaf(int l, int h) {
91   *     double sum = 0;
92 < *     for (int i = l; i &lt; h; ++i) // perform leftmost base step
92 > *     for (int i = l; i < h; ++i) // perform leftmost base step
93   *       sum += array[i] * array[i];
94   *     return sum;
95   *   }
# Line 101 | Line 98 | package jsr166y;
98   *     int l = lo;
99   *     int h = hi;
100   *     Applyer right = null;
101 < *     while (h - l &gt; 1 &amp;&amp;
102 < *        ForkJoinWorkerThread.getEstimatedSurplusTaskCount() &lt;= 3) {
103 < *        int mid = (l + h) &gt;&gt;&gt; 1;
107 < *        right = new Applyer(array, mid, h, seqSize, right);
101 > *     while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
102 > *        int mid = (l + h) >>> 1;
103 > *        right = new Applyer(array, mid, h, right);
104   *        right.fork();
105   *        h = mid;
106   *     }
# Line 113 | Line 109 | package jsr166y;
109   *        if (right.tryUnfork()) // directly calculate if not stolen
110   *          sum += right.atLeaf(right.lo, right.hi);
111   *       else {
112 < *          right.helpJoin();
112 > *          right.join();
113   *          sum += right.result;
114   *        }
115   *        right = right.next;
116   *      }
117   *     result = sum;
118   *   }
119 < * }
120 < * </pre>
119 > * }}</pre>
120 > *
121 > * @since 1.7
122 > * @author Doug Lea
123   */
124   public abstract class RecursiveAction extends ForkJoinTask<Void> {
125 +    private static final long serialVersionUID = 5232453952276485070L;
126  
127      /**
128       * The main computation performed by this task.
# Line 131 | Line 130 | public abstract class RecursiveAction ex
130      protected abstract void compute();
131  
132      /**
133 <     * Always returns null
133 >     * Always returns {@code null}.
134 >     *
135 >     * @return {@code null} always
136       */
137      public final Void getRawResult() { return null; }
138  
# Line 141 | Line 142 | public abstract class RecursiveAction ex
142      protected final void setRawResult(Void mustBeNull) { }
143  
144      /**
145 <     * Implements execution conventions for RecursiveActions
145 >     * Implements execution conventions for RecursiveActions.
146       */
147      protected final boolean exec() {
148          compute();

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines