[cvs] / jsr166 / src / jsr166e / RecursiveAction.java Repository:
ViewVC logotype

Annotation of /jsr166/src/jsr166e/RecursiveAction.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.3 - (view) (download)

1 : dl 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/publicdomain/zero/1.0/
5 :     */
6 :    
7 :     package jsr166e;
8 :    
9 :     /**
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 < THRESHOLD)
28 :     * sortSequentially(lo, hi);
29 :     * else {
30 :     * int mid = (lo + hi) >>> 1;
31 :     * invokeAll(new SortTask(array, lo, mid),
32 :     * new SortTask(array, mid, hi));
33 :     * merge(lo, mid, hi);
34 :     * }
35 :     * }
36 :     * // implementation details follow:
37 : jsr166 1.3 * static final int THRESHOLD = 1000;
38 : dl 1.1 * 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, 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 < THRESHOLD) {
61 :     * for (int i = lo; i < hi; ++i)
62 :     * array[i]++;
63 :     * }
64 :     * else {
65 :     * int mid = (lo + hi) >>> 1;
66 :     * invokeAll(new IncrementTask(array, lo, mid),
67 :     * new IncrementTask(array, mid, hi));
68 :     * }
69 :     * }
70 :     * }}</pre>
71 :     *
72 :     * <p>The following example illustrates some refinements and idioms
73 :     * that may lead to better performance: RecursiveActions need not be
74 :     * fully recursive, so long as they maintain the basic
75 :     * divide-and-conquer approach. Here is a class that sums the squares
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 getSurplusQueuedTaskCount}, but
80 :     * counterbalances potential excess partitioning by directly
81 :     * performing leaf actions on unstolen tasks rather than further
82 :     * subdividing.
83 :     *
84 :     * <pre> {@code
85 :     * double sumOfSquares(ForkJoinPool pool, double[] array) {
86 :     * int n = array.length;
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;
95 :     * double result;
96 :     * Applyer next; // keeps track of right-hand-side tasks
97 :     * Applyer(double[] array, int lo, int hi, Applyer next) {
98 :     * this.array = array; this.lo = lo; this.hi = hi;
99 :     * this.next = next;
100 :     * }
101 :     *
102 :     * double atLeaf(int l, int h) {
103 :     * double sum = 0;
104 :     * for (int i = l; i < h; ++i) // perform leftmost base step
105 :     * sum += array[i] * array[i];
106 :     * return sum;
107 :     * }
108 :     *
109 :     * protected void compute() {
110 :     * int l = lo;
111 :     * int h = hi;
112 :     * Applyer right = null;
113 :     * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {
114 : jsr166 1.2 * int mid = (l + h) >>> 1;
115 :     * right = new Applyer(array, mid, h, right);
116 :     * right.fork();
117 :     * h = mid;
118 : dl 1.1 * }
119 :     * double sum = atLeaf(l, h);
120 :     * while (right != null) {
121 : jsr166 1.2 * if (right.tryUnfork()) // directly calculate if not stolen
122 :     * sum += right.atLeaf(right.lo, right.hi);
123 : dl 1.1 * else {
124 : jsr166 1.2 * right.join();
125 :     * sum += right.result;
126 :     * }
127 :     * right = right.next;
128 :     * }
129 : dl 1.1 * result = sum;
130 :     * }
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.
141 :     */
142 :     protected abstract void compute();
143 :    
144 :     /**
145 :     * Always returns {@code null}.
146 :     *
147 :     * @return {@code null} always
148 :     */
149 :     public final Void getRawResult() { return null; }
150 :    
151 :     /**
152 :     * Requires null completion value.
153 :     */
154 :     protected final void setRawResult(Void mustBeNull) { }
155 :    
156 :     /**
157 :     * Implements execution conventions for RecursiveActions.
158 :     */
159 :     protected final boolean exec() {
160 :     compute();
161 :     return true;
162 :     }
163 :    
164 :     }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8