| 91 |
|
* to complete for some elements than others, either because of |
| 92 |
|
* intrinsic variation (for example I/O) or auxiliary effects such as |
| 93 |
|
* garbage collection. Because CountedCompleters provide their own |
| 94 |
< |
* continuations, other threads need not block waiting to perform |
| 95 |
< |
* them. |
| 94 |
> |
* continuations, other tasks need not block waiting to perform them. |
| 95 |
|
* |
| 96 |
< |
* <p>For example, here is an initial version of a class that uses |
| 97 |
< |
* divide-by-two recursive decomposition to divide work into single |
| 98 |
< |
* pieces (leaf tasks). Even when work is split into individual calls, |
| 99 |
< |
* tree-based techniques are usually preferable to directly forking |
| 100 |
< |
* leaf tasks, because they reduce inter-thread communication and |
| 101 |
< |
* improve load balancing. In the recursive case, the second of each |
| 102 |
< |
* pair of subtasks to finish triggers completion of its parent |
| 96 |
> |
* <p>For example, here is an initial version of a utility method that |
| 97 |
> |
* uses divide-by-two recursive decomposition to divide work into |
| 98 |
> |
* single pieces (leaf tasks). Even when work is split into individual |
| 99 |
> |
* calls, tree-based techniques are usually preferable to directly |
| 100 |
> |
* forking leaf tasks, because they reduce inter-thread communication |
| 101 |
> |
* and improve load balancing. In the recursive case, the second of |
| 102 |
> |
* each pair of subtasks to finish triggers completion of their parent |
| 103 |
|
* (because no result combination is performed, the default no-op |
| 104 |
|
* implementation of method {@code onCompletion} is not overridden). |
| 105 |
< |
* A static utility method sets up the base task and invokes it |
| 106 |
< |
* (here, implicitly using the {@link ForkJoinPool#commonPool()}). |
| 105 |
> |
* The utility method sets up the root task and invokes it (here, |
| 106 |
> |
* implicitly using the {@link ForkJoinPool#commonPool()}). It is |
| 107 |
> |
* straightforward and reliable (but not optimal) to always set the |
| 108 |
> |
* pending count to the number of child tasks and call {@code |
| 109 |
> |
* tryComplete()} immediately before returning. |
| 110 |
|
* |
| 111 |
|
* <pre> {@code |
| 112 |
< |
* class MyOperation<E> { void apply(E e) { ... } } |
| 113 |
< |
* |
| 114 |
< |
* class ForEach<E> extends CountedCompleter<Void> { |
| 115 |
< |
* |
| 116 |
< |
* public static <E> void forEach(E[] array, MyOperation<E> op) { |
| 117 |
< |
* new ForEach<E>(null, array, op, 0, array.length).invoke(); |
| 118 |
< |
* } |
| 119 |
< |
* |
| 120 |
< |
* final E[] array; final MyOperation<E> op; final int lo, hi; |
| 121 |
< |
* ForEach(CountedCompleter<?> p, E[] array, MyOperation<E> op, int lo, int hi) { |
| 122 |
< |
* super(p); |
| 123 |
< |
* this.array = array; this.op = op; this.lo = lo; this.hi = hi; |
| 124 |
< |
* } |
| 125 |
< |
* |
| 126 |
< |
* public void compute() { // version 1 |
| 127 |
< |
* if (hi - lo >= 2) { |
| 128 |
< |
* int mid = (lo + hi) >>> 1; |
| 129 |
< |
* setPendingCount(2); // must set pending count before fork |
| 130 |
< |
* new ForEach(this, array, op, mid, hi).fork(); // right child |
| 129 |
< |
* new ForEach(this, array, op, lo, mid).fork(); // left child |
| 130 |
< |
* } |
| 131 |
< |
* else if (hi > lo) |
| 132 |
< |
* op.apply(array[lo]); |
| 133 |
< |
* tryComplete(); |
| 112 |
> |
* public static <E> void forEach(E[] array, Consumer<E> action) { |
| 113 |
> |
* class Task extends CountedCompleter<Void> { |
| 114 |
> |
* final int lo, hi; |
| 115 |
> |
* Task(Task parent, int lo, int hi) { |
| 116 |
> |
* super(parent); this.lo = lo; this.hi = hi; |
| 117 |
> |
* } |
| 118 |
> |
* |
| 119 |
> |
* public void compute() { |
| 120 |
> |
* if (hi - lo >= 2) { |
| 121 |
> |
* int mid = (lo + hi) >>> 1; |
| 122 |
> |
* // must set pending count before fork |
| 123 |
> |
* setPendingCount(2); |
| 124 |
> |
* new Task(this, mid, hi).fork(); // right child |
| 125 |
> |
* new Task(this, lo, mid).fork(); // left child |
| 126 |
> |
* } |
| 127 |
> |
* else if (hi > lo) |
| 128 |
> |
* action.accept(array[lo]); |
| 129 |
> |
* tryComplete(); |
| 130 |
> |
* } |
| 131 |
|
* } |
| 132 |
+ |
* new Task(null, 0, array.length).invoke(); |
| 133 |
|
* }}</pre> |
| 134 |
|
* |
| 135 |
|
* This design can be improved by noticing that in the recursive case, |
| 136 |
|
* the task has nothing to do after forking its right task, so can |
| 137 |
|
* directly invoke its left task before returning. (This is an analog |
| 138 |
< |
* of tail recursion removal.) Also, because the task returns upon |
| 139 |
< |
* executing its left task (rather than falling through to invoke |
| 140 |
< |
* {@code tryComplete}) the pending count is set to one: |
| 138 |
> |
* of tail recursion removal.) Also, when the last action in a task |
| 139 |
> |
* is to fork or invoke a subtask (a "tail call"), the call to {@code |
| 140 |
> |
* tryComplete()} can be optimized away, at the cost of making the |
| 141 |
> |
* pending count look "off by one". |
| 142 |
|
* |
| 143 |
|
* <pre> {@code |
| 144 |
< |
* class ForEach<E> ... { |
| 145 |
< |
* ... |
| 146 |
< |
* public void compute() { // version 2 |
| 147 |
< |
* if (hi - lo >= 2) { |
| 148 |
< |
* int mid = (lo + hi) >>> 1; |
| 149 |
< |
* setPendingCount(1); // only one pending |
| 150 |
< |
* new ForEach(this, array, op, mid, hi).fork(); // right child |
| 151 |
< |
* new ForEach(this, array, op, lo, mid).compute(); // direct invoke |
| 152 |
< |
* } |
| 153 |
< |
* else { |
| 154 |
< |
* if (hi > lo) |
| 156 |
< |
* op.apply(array[lo]); |
| 157 |
< |
* tryComplete(); |
| 144 |
> |
* public void compute() { |
| 145 |
> |
* if (hi - lo >= 2) { |
| 146 |
> |
* int mid = (lo + hi) >>> 1; |
| 147 |
> |
* setPendingCount(1); // not off by one ! |
| 148 |
> |
* new Task(this, mid, hi).fork(); // right child |
| 149 |
> |
* new Task(this, lo, mid).compute(); // direct invoke |
| 150 |
> |
* } else { |
| 151 |
> |
* if (hi > lo) |
| 152 |
> |
* action.accept(array[lo]); |
| 153 |
> |
* tryComplete(); |
| 154 |
> |
* } |
| 155 |
|
* } |
| 156 |
< |
* } |
| 160 |
< |
* }}</pre> |
| 156 |
> |
* }}</pre> |
| 157 |
|
* |
| 158 |
|
* As a further optimization, notice that the left task need not even exist. |
| 159 |
|
* Instead of creating a new one, we can iterate using the original task, |
| 160 |
|
* and add a pending count for each fork. Additionally, because no task |
| 161 |
|
* in this tree implements an {@link #onCompletion(CountedCompleter)} method, |
| 162 |
< |
* {@code tryComplete()} can be replaced with {@link #propagateCompletion}. |
| 162 |
> |
* {@code tryComplete} can be replaced with {@link #propagateCompletion}. |
| 163 |
|
* |
| 164 |
|
* <pre> {@code |
| 165 |
< |
* class ForEach<E> ... { |
| 166 |
< |
* ... |
| 167 |
< |
* public void compute() { // version 3 |
| 168 |
< |
* int l = lo, h = hi; |
| 169 |
< |
* while (h - l >= 2) { |
| 170 |
< |
* int mid = (l + h) >>> 1; |
| 171 |
< |
* addToPendingCount(1); |
| 172 |
< |
* new ForEach(this, array, op, mid, h).fork(); // right child |
| 173 |
< |
* h = mid; |
| 174 |
< |
* } |
| 175 |
< |
* if (h > l) |
| 176 |
< |
* op.apply(array[l]); |
| 177 |
< |
* propagateCompletion(); |
| 165 |
> |
* public void compute() { |
| 166 |
> |
* int n = hi - lo; |
| 167 |
> |
* for (; n >= 2; n /= 2) { |
| 168 |
> |
* addToPendingCount(1); |
| 169 |
> |
* new Task(this, lo + n/2, lo + n).fork(); |
| 170 |
> |
* } |
| 171 |
> |
* if (n > 0) |
| 172 |
> |
* action.accept(array[lo]); |
| 173 |
> |
* propagateCompletion(); |
| 174 |
> |
* } |
| 175 |
> |
* }}</pre> |
| 176 |
> |
* |
| 177 |
> |
* When pending counts can be precomputed, they can be established in |
| 178 |
> |
* the constructor: |
| 179 |
> |
* |
| 180 |
> |
* <pre> {@code |
| 181 |
> |
* public static <E> void forEach(E[] array, Consumer<E> action) { |
| 182 |
> |
* class Task extends CountedCompleter<Void> { |
| 183 |
> |
* final int lo, hi; |
| 184 |
> |
* Task(Task parent, int lo, int hi) { |
| 185 |
> |
* super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo)); |
| 186 |
> |
* this.lo = lo; this.hi = hi; |
| 187 |
> |
* } |
| 188 |
> |
* |
| 189 |
> |
* public void compute() { |
| 190 |
> |
* for (int n = hi - lo; n >= 2; n /= 2) |
| 191 |
> |
* new Task(this, lo + n/2, lo + n).fork(); |
| 192 |
> |
* action.accept(array[lo]); |
| 193 |
> |
* propagateCompletion(); |
| 194 |
> |
* } |
| 195 |
|
* } |
| 196 |
+ |
* if (array.length > 0) |
| 197 |
+ |
* new Task(null, 0, array.length).invoke(); |
| 198 |
|
* }}</pre> |
| 199 |
|
* |
| 200 |
< |
* Additional optimizations of such classes might entail precomputing |
| 201 |
< |
* pending counts so that they can be established in constructors, |
| 202 |
< |
* specializing classes for leaf steps, subdividing by say, four, |
| 203 |
< |
* instead of two per iteration, and using an adaptive threshold |
| 189 |
< |
* instead of always subdividing down to single elements. |
| 200 |
> |
* Additional optimizations of such classes might entail specializing |
| 201 |
> |
* classes for leaf steps, subdividing by say, four, instead of two |
| 202 |
> |
* per iteration, and using an adaptive threshold instead of always |
| 203 |
> |
* subdividing down to single elements. |
| 204 |
|
* |
| 205 |
|
* <p><b>Searching.</b> A tree of CountedCompleters can search for a |
| 206 |
|
* value or property in different parts of a data structure, and |
