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.3 by jsr166, Mon Jul 20 21:54:51 2009 UTC vs.
Revision 1.19 by jsr166, Mon Jun 27 02:47:32 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 {@code Void}
12 < * ForkJoinTasks. Because {@code null} is the only valid value of
13 < * {@code Void}, methods such as join always return {@code null}
14 < * upon completion.
15 < *
16 < * <p><b>Sample Usages.</b> Here is a sketch of a ForkJoin sort that
17 < * sorts a given {@code long[]} array:
18 < *
19 < * <pre>
20 < * class SortTask extends RecursiveAction {
21 < *   final long[] array; final int lo; final int hi;
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 simple but complete ForkJoin
17 > * sort that sorts a given {@code long[]} array:
18 > *
19 > *  <pre> {@code
20 > * static class SortTask extends RecursiveAction {
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 + *   SortTask(long[] array) { this(array, 0, array.length); }
26   *   protected void compute() {
27 < *     if (hi - lo &lt; THRESHOLD)
28 < *       sequentiallySort(array, lo, hi);
27 > *     if (hi - lo < THRESHOLD)
28 > *       sortSequentially(lo, hi);
29   *     else {
30 < *       int mid = (lo + hi) &gt;&gt;&gt; 1;
30 > *       int mid = (lo + hi) >>> 1;
31   *       invokeAll(new SortTask(array, lo, mid),
32   *                 new SortTask(array, mid, hi));
33 < *       merge(array, lo, hi);
33 > *       merge(lo, mid, hi);
34   *     }
35   *   }
36 < * }
37 < * </pre>
38 < *
39 < * You could then sort anArray by creating {@code new SortTask(anArray, 0,
40 < * anArray.length-1) } and invoking it in a ForkJoinPool.
41 < * As a more concrete simple example, the following task increments
42 < * each element of an array:
43 < * <pre>
36 > *   // implementation details follow:
37 > *   final static int THRESHOLD = 1000;
38 > *   void sortSequentially(int lo, int hi) {
39 > *     Arrays.sort(array, lo, hi);
40 > *   }
41 > *   void merge(int lo, int mid, int hi) {
42 > *     long[] buf = Arrays.copyOfRange(array, lo, mid);
43 > *     for (int i = 0, j = lo, k = mid; i < buf.length; j++)
44 > *       array[j] = (k == hi || buf[i] < array[k]) ?
45 > *         buf[i++] : array[k++];
46 > *   }
47 > * }}</pre>
48 > *
49 > * You could then sort {@code anArray} by creating {@code new
50 > * SortTask(anArray)} and invoking it in a ForkJoinPool.  As a more
51 > * concrete simple example, the following task increments each element
52 > * of an array:
53 > *  <pre> {@code
54   * class IncrementTask extends RecursiveAction {
55 < *   final long[] array; final int lo; final int hi;
55 > *   final long[] array; final int lo, hi;
56   *   IncrementTask(long[] array, int lo, int hi) {
57   *     this.array = array; this.lo = lo; this.hi = hi;
58   *   }
59   *   protected void compute() {
60 < *     if (hi - lo &lt; THRESHOLD) {
61 < *       for (int i = lo; i &lt; hi; ++i)
60 > *     if (hi - lo < THRESHOLD) {
61 > *       for (int i = lo; i < hi; ++i)
62   *         array[i]++;
63   *     }
64   *     else {
65 < *       int mid = (lo + hi) &gt;&gt;&gt; 1;
65 > *       int mid = (lo + hi) >>> 1;
66   *       invokeAll(new IncrementTask(array, lo, mid),
67   *                 new IncrementTask(array, mid, hi));
68   *     }
69   *   }
70 < * }
60 < * </pre>
61 < *
70 > * }}</pre>
71   *
72   * <p>The following example illustrates some refinements and idioms
73   * that may lead to better performance: RecursiveActions need not be
# Line 67 | Line 76 | package jsr166y;
76   * of each element of a double array, by subdividing out only the
77   * right-hand-sides of repeated divisions by two, and keeping track of
78   * them with a chain of {@code next} references. It uses a dynamic
79 < * threshold based on method {@code surplus}, but counterbalances
80 < * potential excess partitioning by directly performing leaf actions
81 < * on unstolen tasks rather than further subdividing.
79 > * threshold based on method {@code getSurplusQueuedTaskCount}, but
80 > * counterbalances potential excess partitioning by directly
81 > * performing leaf actions on unstolen tasks rather than further
82 > * subdividing.
83   *
84 < * <pre>
84 > *  <pre> {@code
85   * double sumOfSquares(ForkJoinPool pool, double[] array) {
86   *   int n = array.length;
87 < *   int seqSize = 1 + n / (8 * pool.getParallelism());
78 < *   Applyer a = new Applyer(array, 0, n, seqSize, null);
87 > *   Applyer a = new Applyer(array, 0, n, null);
88   *   pool.invoke(a);
89   *   return a.result;
90   * }
91   *
92   * class Applyer extends RecursiveAction {
93   *   final double[] array;
94 < *   final int lo, hi, seqSize;
94 > *   final int lo, hi;
95   *   double result;
96   *   Applyer next; // keeps track of right-hand-side tasks
97 < *   Applyer(double[] array, int lo, int hi, int seqSize, Applyer next) {
97 > *   Applyer(double[] array, int lo, int hi, Applyer next) {
98   *     this.array = array; this.lo = lo; this.hi = hi;
99 < *     this.seqSize = seqSize; this.next = next;
99 > *     this.next = next;
100   *   }
101   *
102 < *   double atLeaf(int l, int r) {
102 > *   double atLeaf(int l, int h) {
103   *     double sum = 0;
104 < *     for (int i = l; i &lt; h; ++i) // perform leftmost base step
104 > *     for (int i = l; i < h; ++i) // perform leftmost base step
105   *       sum += array[i] * array[i];
106   *     return sum;
107   *   }
# Line 101 | Line 110 | package jsr166y;
110   *     int l = lo;
111   *     int h = hi;
112   *     Applyer right = null;
113 < *     while (h - l &gt; 1 &amp;&amp;
114 < *        ForkJoinWorkerThread.getEstimatedSurplusTaskCount() &lt;= 3) {
115 < *        int mid = (l + h) &gt;&gt;&gt; 1;
107 < *        right = new Applyer(array, mid, h, seqSize, right);
113 > *     while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
114 > *        int mid = (l + h) >>> 1;
115 > *        right = new Applyer(array, mid, h, right);
116   *        right.fork();
117   *        h = mid;
118   *     }
# Line 113 | Line 121 | package jsr166y;
121   *        if (right.tryUnfork()) // directly calculate if not stolen
122   *          sum += right.atLeaf(right.lo, right.hi);
123   *       else {
124 < *          right.helpJoin();
124 > *          right.join();
125   *          sum += right.result;
126   *        }
127   *        right = right.next;
128   *      }
129   *     result = sum;
130   *   }
131 < * }
132 < * </pre>
131 > * }}</pre>
132 > *
133 > * @since 1.7
134 > * @author Doug Lea
135   */
136   public abstract class RecursiveAction extends ForkJoinTask<Void> {
137 +    private static final long serialVersionUID = 5232453952276485070L;
138  
139      /**
140       * The main computation performed by this task.
# Line 131 | Line 142 | public abstract class RecursiveAction ex
142      protected abstract void compute();
143  
144      /**
145 <     * Always returns null
145 >     * Always returns {@code null}.
146 >     *
147 >     * @return {@code null} always
148       */
149      public final Void getRawResult() { return null; }
150  
# Line 141 | Line 154 | public abstract class RecursiveAction ex
154      protected final void setRawResult(Void mustBeNull) { }
155  
156      /**
157 <     * Implements execution conventions for RecursiveActions
157 >     * Implements execution conventions for RecursiveActions.
158       */
159      protected final boolean exec() {
160          compute();

Diff Legend

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