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 |
5 |
*/ |
6 |
|
7 |
package jsr166y.forkjoin; |
8 |
import static jsr166y.forkjoin.TaskTypes.*; |
9 |
import java.util.*; |
10 |
import java.util.concurrent.atomic.*; |
11 |
|
12 |
/** |
13 |
* Parallel int operations on collections and arrays. |
14 |
*/ |
15 |
public class IntTasks { |
16 |
/** |
17 |
* default granularity for divide-by-two tasks. Provides about |
18 |
* four times as many finest-grained tasks as there are CPUs. |
19 |
*/ |
20 |
static int defaultGranularity(ForkJoinExecutor ex, int n) { |
21 |
int threads = ex.getParallelismLevel(); |
22 |
return 1 + n / ((threads << 2) - 3); |
23 |
} |
24 |
|
25 |
/** |
26 |
* Applies the given procedure to each element of the array. |
27 |
* @param ex the executor |
28 |
* @param array the array |
29 |
* @param proc the procedure |
30 |
*/ |
31 |
public static <T> void apply(ForkJoinExecutor ex, |
32 |
int[] array, |
33 |
IntProcedure proc) { |
34 |
int n = array.length; |
35 |
ex.invoke(new FJApplyer(array, proc, 0, n, defaultGranularity(ex, n))); |
36 |
} |
37 |
|
38 |
/** |
39 |
* Returns reduction of given array |
40 |
* @param ex the executor |
41 |
* @param array the array |
42 |
* @param reducer the reducer |
43 |
* @param base the result for an empty array |
44 |
*/ |
45 |
public static int reduce(ForkJoinExecutor ex, |
46 |
int[] array, |
47 |
IntReducer reducer, |
48 |
int base) { |
49 |
int n = array.length; |
50 |
FJReducer r = new FJReducer(array,reducer, base, |
51 |
0, n, defaultGranularity(ex, n)); |
52 |
ex.invoke(r); |
53 |
return r.result; |
54 |
} |
55 |
|
56 |
/** |
57 |
* Applies mapper to each element of list and reduces result |
58 |
* @param ex the executor |
59 |
* @param list the list |
60 |
* @param mapper the mapper |
61 |
* @param reducer the reducer |
62 |
* @param base the result for an empty list |
63 |
*/ |
64 |
public static <T> int reduce(ForkJoinExecutor ex, |
65 |
List<T> list, |
66 |
MapperToInt<T> mapper, |
67 |
IntReducer reducer, |
68 |
int base) { |
69 |
int n = list.size(); |
70 |
FJMapReducer<T> r = |
71 |
new FJMapReducer<T>(list, mapper, reducer, base, |
72 |
0, n, defaultGranularity(ex, n)); |
73 |
ex.invoke(r); |
74 |
return r.result; |
75 |
} |
76 |
|
77 |
/** |
78 |
* Applies mapper to each element of list and reduces result |
79 |
* @param ex the executor |
80 |
* @param array the array |
81 |
* @param mapper the mapper |
82 |
* @param reducer the reducer |
83 |
* @param base the result for an empty list |
84 |
*/ |
85 |
public static <T> int reduce(ForkJoinExecutor ex, |
86 |
T[] array, |
87 |
MapperToInt<T> mapper, |
88 |
IntReducer reducer, |
89 |
int base) { |
90 |
int n = array.length; |
91 |
FJArrayMapReducer<T> r = |
92 |
new FJArrayMapReducer<T>(array, mapper, reducer, base, |
93 |
0, n, defaultGranularity(ex, n)); |
94 |
ex.invoke(r); |
95 |
return r.result; |
96 |
} |
97 |
|
98 |
/** |
99 |
* Applies mapper to each element of array and reduces result |
100 |
* @param ex the executor |
101 |
* @param array the array |
102 |
* @param mapper the mapper |
103 |
* @param reducer the reducer |
104 |
* @param base the result for an empty array |
105 |
*/ |
106 |
public static <T> int reduce(ForkJoinExecutor ex, |
107 |
int[] array, |
108 |
IntTransformer mapper, |
109 |
IntReducer reducer, |
110 |
int base) { |
111 |
int n = array.length; |
112 |
FJTransformReducer r = |
113 |
new FJTransformReducer(array, mapper, reducer, base, |
114 |
0, n, defaultGranularity(ex, n)); |
115 |
ex.invoke(r); |
116 |
return r.result; |
117 |
} |
118 |
|
119 |
/** |
120 |
* Returns a array mapping each element of given array using mapper |
121 |
* @param ex the executor |
122 |
* @param array the array |
123 |
* @param mapper the mapper |
124 |
*/ |
125 |
public static int[] map(ForkJoinExecutor ex, |
126 |
int[] array, |
127 |
IntTransformer mapper) { |
128 |
int n = array.length; |
129 |
int[] dest = new int[n]; |
130 |
ex.invoke(new FJMapper(array, dest, mapper, |
131 |
0, n, defaultGranularity(ex, n))); |
132 |
return dest; |
133 |
} |
134 |
|
135 |
/** |
136 |
* Returns an element of the array matching the given predicate, or |
137 |
* missing if none |
138 |
* @param ex the executor |
139 |
* @param array the array |
140 |
* @param pred the predicate |
141 |
* @param missing the value to return if no such element exists |
142 |
*/ |
143 |
public static int findAny(ForkJoinExecutor ex, |
144 |
int[] array, |
145 |
IntPredicate pred, |
146 |
int missing) { |
147 |
int n = array.length; |
148 |
VolatileInt result = new VolatileInt(missing); |
149 |
ex.invoke(new FJFindAny(array, pred, result, missing, |
150 |
0, n, defaultGranularity(ex, n))); |
151 |
return result.value; |
152 |
} |
153 |
|
154 |
static final class VolatileInt { |
155 |
volatile int value; |
156 |
VolatileInt(int v) { value = v; } |
157 |
} |
158 |
|
159 |
/** |
160 |
* Returns a list of all elements of the array matching pred |
161 |
* @param ex the executor |
162 |
* @param array the array |
163 |
* @param pred the predicate |
164 |
*/ |
165 |
public static List<Integer> findAll(ForkJoinExecutor ex, |
166 |
int[] array, |
167 |
IntPredicate pred) { |
168 |
int n = array.length; |
169 |
Vector<Integer> dest = new Vector<Integer>(); // todo: use smarter list |
170 |
ex.invoke(new FJFindAll(array, pred, dest, |
171 |
0, n, defaultGranularity(ex, n))); |
172 |
return dest; |
173 |
} |
174 |
|
175 |
|
176 |
/** |
177 |
* Sorts the given array |
178 |
* @param ex the executor |
179 |
* @param array the array |
180 |
*/ |
181 |
public static void sort(ForkJoinExecutor ex, int[] array) { |
182 |
int n = array.length; |
183 |
int[] workSpace = new int[n]; |
184 |
ex.invoke(new FJSorter(array, 0, workSpace, 0, n)); |
185 |
} |
186 |
|
187 |
/** |
188 |
* Returns the sum of all elements |
189 |
* @param ex the executor |
190 |
* @param array the array |
191 |
*/ |
192 |
public static int sum(ForkJoinExecutor ex, |
193 |
int[] array) { |
194 |
int n = array.length; |
195 |
FJSum r = new FJSum(array, 0, n, defaultGranularity(ex, n)); |
196 |
ex.invoke(r); |
197 |
return r.result; |
198 |
} |
199 |
|
200 |
/** |
201 |
* Returns the sum of all mapped elements |
202 |
* @param ex the executor |
203 |
* @param array the array |
204 |
* @param mapper the mapper |
205 |
*/ |
206 |
public static int sum(ForkJoinExecutor ex, |
207 |
int[] array, |
208 |
IntTransformer mapper) { |
209 |
int n = array.length; |
210 |
FJTransformSum r = |
211 |
new FJTransformSum(array, mapper, 0, n, defaultGranularity(ex, n)); |
212 |
ex.invoke(r); |
213 |
return r.result; |
214 |
} |
215 |
|
216 |
/** |
217 |
* Replaces each element with running cumulative sum. |
218 |
* @param ex the executor |
219 |
* @param array the array |
220 |
* @return the sum of all elements |
221 |
*/ |
222 |
public static int cumulate(ForkJoinExecutor ex, int[] array) { |
223 |
int n = array.length; |
224 |
if (n == 0) |
225 |
return 0; |
226 |
if (n == 1) |
227 |
return array[0]; |
228 |
int gran; |
229 |
int threads = ex.getParallelismLevel(); |
230 |
if (threads == 1) |
231 |
gran = n; |
232 |
else |
233 |
gran = n / (threads << 3); |
234 |
if (gran < 1024) |
235 |
gran = 1024; |
236 |
// int gran = (threads == 1)? n : 4096; |
237 |
// int gran = (threads == 1)? n : 8192; |
238 |
FJCumulator.Ctl ctl = new FJCumulator.Ctl(array, gran); |
239 |
FJCumulator r = new FJCumulator(null, ctl, 0, n); |
240 |
ex.invoke(r); |
241 |
return array[n-1]; |
242 |
} |
243 |
|
244 |
/** |
245 |
* Returns the minimum of all elements, or MAX_VALUE if empty |
246 |
* @param ex the executor |
247 |
* @param array the array |
248 |
*/ |
249 |
public static int min(ForkJoinExecutor ex, |
250 |
int[] array) { |
251 |
int n = array.length; |
252 |
FJMin r = new FJMin(array, 0, n, defaultGranularity(ex, n)); |
253 |
ex.invoke(r); |
254 |
return r.result; |
255 |
} |
256 |
|
257 |
/** |
258 |
* Returns the maximum of all elements, or MIN_VALUE if empty |
259 |
* @param ex the executor |
260 |
* @param array the array |
261 |
*/ |
262 |
public static int max(ForkJoinExecutor ex, |
263 |
int[] array) { |
264 |
int n = array.length; |
265 |
FJMax r = new FJMax(array, 0, n, defaultGranularity(ex, n)); |
266 |
ex.invoke(r); |
267 |
return r.result; |
268 |
} |
269 |
|
270 |
|
271 |
/** |
272 |
* Fork/Join version of apply |
273 |
*/ |
274 |
static final class FJApplyer extends RecursiveAction { |
275 |
final int[] array; |
276 |
final IntProcedure f; |
277 |
final int lo; |
278 |
final int hi; |
279 |
final int gran; |
280 |
FJApplyer next; |
281 |
|
282 |
FJApplyer(int[] array, IntProcedure f, int lo, int hi, int gran){ |
283 |
this.array = array; |
284 |
this.f = f; |
285 |
this.lo = lo; |
286 |
this.hi = hi; |
287 |
this.gran = gran; |
288 |
} |
289 |
|
290 |
protected void compute() { |
291 |
FJApplyer right = null; |
292 |
int l = lo; |
293 |
int h = hi; |
294 |
int g = gran; |
295 |
while (h - l > g) { |
296 |
int mid = (l + h) >>> 1; |
297 |
FJApplyer r = new FJApplyer(array, f, mid, h, g); |
298 |
r.fork(); |
299 |
r.next = right; |
300 |
right = r; |
301 |
h = mid; |
302 |
} |
303 |
for (int i = l; i < h; ++i) |
304 |
f.apply(array[i]); |
305 |
while (right != null) { |
306 |
right.join(); |
307 |
right = right.next; |
308 |
} |
309 |
} |
310 |
} |
311 |
|
312 |
/** |
313 |
* Fork/Join version of MapReduce |
314 |
*/ |
315 |
static final class FJMapReducer<T> extends RecursiveAction { |
316 |
final List<T> list; |
317 |
final MapperToInt<T> mapper; |
318 |
final IntReducer reducer; |
319 |
final int base; |
320 |
final int lo; |
321 |
final int hi; |
322 |
final int gran; |
323 |
int result; |
324 |
FJMapReducer<T> next; |
325 |
|
326 |
FJMapReducer(List<T> list, |
327 |
MapperToInt<T> mapper, |
328 |
IntReducer reducer, |
329 |
int base, |
330 |
int lo, |
331 |
int hi, |
332 |
int gran) { |
333 |
this.list = list; |
334 |
this.mapper = mapper; |
335 |
this.reducer = reducer; |
336 |
this.base = base; |
337 |
this.lo = lo; |
338 |
this.hi = hi; |
339 |
this.gran = gran; |
340 |
} |
341 |
|
342 |
|
343 |
protected void compute() { |
344 |
FJMapReducer<T> right = null; |
345 |
int l = lo; |
346 |
int h = hi; |
347 |
int g = gran; |
348 |
while (h - l > g) { |
349 |
int mid = (l + h) >>> 1; |
350 |
FJMapReducer<T> r =new FJMapReducer<T>(list, mapper, reducer, |
351 |
base, mid, h, g); |
352 |
r.next = right; |
353 |
right = r; |
354 |
h = mid; |
355 |
r.fork(); |
356 |
} |
357 |
int x = base; |
358 |
for (int i = l; i < h; ++i) |
359 |
x = reducer.combine(x, mapper.map(list.get(i))); |
360 |
while (right != null) { |
361 |
if (ForkJoinWorkerThread.removeIfNextLocalTask(right)) |
362 |
right.compute(); |
363 |
else |
364 |
right.join(); |
365 |
x = reducer.combine(x, right.result); |
366 |
right = right.next; |
367 |
} |
368 |
result = x; |
369 |
} |
370 |
} |
371 |
|
372 |
/** |
373 |
* Fork/Join version of MapReduce |
374 |
*/ |
375 |
static final class FJArrayMapReducer<T> extends RecursiveAction { |
376 |
final T[] array; |
377 |
final MapperToInt<T> mapper; |
378 |
final IntReducer reducer; |
379 |
final int base; |
380 |
final int lo; |
381 |
final int hi; |
382 |
final int gran; |
383 |
int result; |
384 |
FJArrayMapReducer<T> next; |
385 |
|
386 |
FJArrayMapReducer(T[] array, |
387 |
MapperToInt<T> mapper, |
388 |
IntReducer reducer, |
389 |
int base, |
390 |
int lo, |
391 |
int hi, |
392 |
int gran) { |
393 |
this.array = array; |
394 |
this.mapper = mapper; |
395 |
this.reducer = reducer; |
396 |
this.base = base; |
397 |
this.lo = lo; |
398 |
this.hi = hi; |
399 |
this.gran = gran; |
400 |
} |
401 |
|
402 |
|
403 |
protected void compute() { |
404 |
FJArrayMapReducer<T> right = null; |
405 |
int l = lo; |
406 |
int h = hi; |
407 |
int g = gran; |
408 |
while (h - l > g) { |
409 |
int mid = (l + h) >>> 1; |
410 |
FJArrayMapReducer<T> r = |
411 |
new FJArrayMapReducer<T>(array, mapper, reducer, |
412 |
base, mid, h, g); |
413 |
r.next = right; |
414 |
right = r; |
415 |
h = mid; |
416 |
r.fork(); |
417 |
} |
418 |
int x = base; |
419 |
for (int i = l; i < h; ++i) |
420 |
x = reducer.combine(x, mapper.map(array[i])); |
421 |
while (right != null) { |
422 |
right.join(); |
423 |
x = reducer.combine(x, right.result); |
424 |
FJArrayMapReducer<T> next = right.next; |
425 |
right.next = null; |
426 |
right = next; |
427 |
} |
428 |
result = x; |
429 |
} |
430 |
} |
431 |
|
432 |
/** |
433 |
* Fork/Join version of TransformReduce |
434 |
*/ |
435 |
static final class FJTransformReducer extends RecursiveAction { |
436 |
final int[] array; |
437 |
final IntTransformer mapper; |
438 |
final IntReducer reducer; |
439 |
final int base; |
440 |
final int lo; |
441 |
final int hi; |
442 |
final int gran; |
443 |
int result; |
444 |
FJTransformReducer next; |
445 |
|
446 |
FJTransformReducer(int[] array, |
447 |
IntTransformer mapper, |
448 |
IntReducer reducer, |
449 |
int base, |
450 |
int lo, |
451 |
int hi, |
452 |
int gran) { |
453 |
this.array = array; |
454 |
this.mapper = mapper; |
455 |
this.reducer = reducer; |
456 |
this.base = base; |
457 |
this.lo = lo; |
458 |
this.hi = hi; |
459 |
this.gran = gran; |
460 |
} |
461 |
|
462 |
protected void compute() { |
463 |
FJTransformReducer right = null; |
464 |
int l = lo; |
465 |
int h = hi; |
466 |
int g = gran; |
467 |
while (h - l > g) { |
468 |
int mid = (l + h) >>> 1; |
469 |
FJTransformReducer r = |
470 |
new FJTransformReducer(array, mapper, reducer, |
471 |
base, mid, h, g); |
472 |
r.fork(); |
473 |
r.next = right; |
474 |
|
475 |
right = r; |
476 |
h = mid; |
477 |
} |
478 |
int x = base; |
479 |
for (int i = l; i < h; ++i) |
480 |
x = reducer.combine(x, mapper.map(array[i])); |
481 |
while (right != null) { |
482 |
right.join(); |
483 |
x = reducer.combine(x, right.result); |
484 |
right = right.next; |
485 |
} |
486 |
result = x; |
487 |
} |
488 |
|
489 |
} |
490 |
|
491 |
/** |
492 |
* Fork/Join version of Map |
493 |
*/ |
494 |
static final class FJMapper extends RecursiveAction { |
495 |
final int[] array; |
496 |
final int[] dest; |
497 |
final IntTransformer mapper; |
498 |
final int lo; |
499 |
final int hi; |
500 |
final int gran; |
501 |
FJMapper next; |
502 |
|
503 |
FJMapper(int[] array, |
504 |
int[] dest, |
505 |
IntTransformer mapper, |
506 |
int lo, |
507 |
int hi, |
508 |
int gran) { |
509 |
this.array = array; |
510 |
this.dest = dest; |
511 |
this.mapper = mapper; |
512 |
this.lo = lo; |
513 |
this.hi = hi; |
514 |
this.gran = gran; |
515 |
} |
516 |
|
517 |
|
518 |
protected void compute() { |
519 |
FJMapper right = null; |
520 |
int l = lo; |
521 |
int h = hi; |
522 |
int g = gran; |
523 |
while (h - l > g) { |
524 |
int mid = (l + h) >>> 1; |
525 |
FJMapper r = |
526 |
new FJMapper(array, dest, mapper, mid, h, g); |
527 |
r.fork(); |
528 |
r.next = right; |
529 |
|
530 |
right = r; |
531 |
h = mid; |
532 |
} |
533 |
for (int i = l; i < h; ++i) |
534 |
dest[i] = mapper.map(array[i]); |
535 |
while (right != null) { |
536 |
right.join(); |
537 |
right = right.next; |
538 |
} |
539 |
} |
540 |
} |
541 |
|
542 |
/** |
543 |
* Fork/Join version of Reduce |
544 |
*/ |
545 |
static final class FJReducer extends RecursiveAction { |
546 |
final int[] array; |
547 |
final IntReducer reducer; |
548 |
final int base; |
549 |
final int lo; |
550 |
final int hi; |
551 |
final int gran; |
552 |
int result; |
553 |
FJReducer next; |
554 |
|
555 |
FJReducer(int[] array, |
556 |
IntReducer reducer, |
557 |
int base, |
558 |
int lo, |
559 |
int hi, |
560 |
int gran) { |
561 |
this.array = array; |
562 |
this.reducer = reducer; |
563 |
this.base = base; |
564 |
this.lo = lo; |
565 |
this.hi = hi; |
566 |
this.gran = gran; |
567 |
} |
568 |
|
569 |
protected void compute() { |
570 |
FJReducer right = null; |
571 |
int l = lo; |
572 |
int h = hi; |
573 |
int g = gran; |
574 |
while (h - l > g) { |
575 |
int mid = (l + h) >>> 1; |
576 |
FJReducer r = |
577 |
new FJReducer(array, reducer, base, mid, h, g); |
578 |
r.fork(); |
579 |
r.next = right; |
580 |
|
581 |
right = r; |
582 |
h = mid; |
583 |
} |
584 |
int x = base; |
585 |
for (int i = l; i < h; ++i) |
586 |
x = reducer.combine(x, array[i]); |
587 |
while (right != null) { |
588 |
right.join(); |
589 |
x = reducer.combine(x, right.result); |
590 |
right = right.next; |
591 |
} |
592 |
result = x; |
593 |
} |
594 |
} |
595 |
|
596 |
/** |
597 |
* Fork/Join version of sum |
598 |
*/ |
599 |
static final class FJSum extends RecursiveAction { |
600 |
final int[] array; |
601 |
final int lo; |
602 |
final int hi; |
603 |
final int gran; |
604 |
int result; |
605 |
FJSum next; |
606 |
|
607 |
FJSum(int[] array, |
608 |
int lo, |
609 |
int hi, |
610 |
int gran) { |
611 |
this.array = array; |
612 |
this.lo = lo; |
613 |
this.hi = hi; |
614 |
this.gran = gran; |
615 |
} |
616 |
|
617 |
protected void compute() { |
618 |
FJSum right = null; |
619 |
int l = lo; |
620 |
int h = hi; |
621 |
int g = gran; |
622 |
while (h - l > g) { |
623 |
int mid = (l + h) >>> 1; |
624 |
FJSum r = |
625 |
new FJSum(array, mid, h, g); |
626 |
r.fork(); |
627 |
r.next = right; |
628 |
|
629 |
right = r; |
630 |
h = mid; |
631 |
} |
632 |
int x = 0; |
633 |
for (int i = l; i < h; ++i) |
634 |
x += array[i]; |
635 |
while (right != null) { |
636 |
right.join(); |
637 |
x += right.result; |
638 |
right = right.next; |
639 |
} |
640 |
result = x; |
641 |
} |
642 |
} |
643 |
|
644 |
/** |
645 |
* Fork/Join version of min |
646 |
*/ |
647 |
static final class FJMin extends RecursiveAction { |
648 |
final int[] array; |
649 |
final int lo; |
650 |
final int hi; |
651 |
final int gran; |
652 |
int result; |
653 |
FJMin next; |
654 |
|
655 |
FJMin(int[] array, |
656 |
int lo, |
657 |
int hi, |
658 |
int gran) { |
659 |
this.array = array; |
660 |
this.lo = lo; |
661 |
this.hi = hi; |
662 |
this.gran = gran; |
663 |
} |
664 |
|
665 |
protected void compute() { |
666 |
FJMin right = null; |
667 |
int l = lo; |
668 |
int h = hi; |
669 |
int g = gran; |
670 |
while (h - l > g) { |
671 |
int mid = (l + h) >>> 1; |
672 |
FJMin r = |
673 |
new FJMin(array, mid, h, g); |
674 |
r.fork(); |
675 |
r.next = right; |
676 |
|
677 |
right = r; |
678 |
h = mid; |
679 |
} |
680 |
int x = Integer.MAX_VALUE; |
681 |
for (int i = l; i < h; ++i) { |
682 |
int y = array[i]; |
683 |
if (y < x) |
684 |
x = y; |
685 |
} |
686 |
while (right != null) { |
687 |
right.join(); |
688 |
int y = right.result; |
689 |
if (y < x) |
690 |
x = y; |
691 |
right = right.next; |
692 |
} |
693 |
result = x; |
694 |
} |
695 |
} |
696 |
|
697 |
/** |
698 |
* Fork/Join version of max |
699 |
*/ |
700 |
static final class FJMax extends RecursiveAction { |
701 |
final int[] array; |
702 |
final int lo; |
703 |
final int hi; |
704 |
final int gran; |
705 |
int result; |
706 |
FJMax next; |
707 |
|
708 |
FJMax(int[] array, |
709 |
int lo, |
710 |
int hi, |
711 |
int gran) { |
712 |
this.array = array; |
713 |
this.lo = lo; |
714 |
this.hi = hi; |
715 |
this.gran = gran; |
716 |
} |
717 |
|
718 |
protected void compute() { |
719 |
FJMax right = null; |
720 |
int l = lo; |
721 |
int h = hi; |
722 |
int g = gran; |
723 |
while (h - l > g) { |
724 |
int mid = (l + h) >>> 1; |
725 |
FJMax r = |
726 |
new FJMax(array, mid, h, g); |
727 |
r.fork(); |
728 |
r.next = right; |
729 |
|
730 |
right = r; |
731 |
h = mid; |
732 |
} |
733 |
int x = Integer.MAX_VALUE; |
734 |
for (int i = l; i < h; ++i) { |
735 |
int y = array[i]; |
736 |
if (y > x) |
737 |
x = y; |
738 |
} |
739 |
while (right != null) { |
740 |
right.join(); |
741 |
int y = right.result; |
742 |
if (y > x) |
743 |
x = y; |
744 |
right = right.next; |
745 |
} |
746 |
result = x; |
747 |
} |
748 |
} |
749 |
|
750 |
/** |
751 |
* Fork/Join version of TransformSum |
752 |
*/ |
753 |
static final class FJTransformSum extends RecursiveAction { |
754 |
final int[] array; |
755 |
final IntTransformer mapper; |
756 |
final int lo; |
757 |
final int hi; |
758 |
final int gran; |
759 |
int result; |
760 |
FJTransformSum next; |
761 |
|
762 |
FJTransformSum(int[] array, |
763 |
IntTransformer mapper, |
764 |
int lo, |
765 |
int hi, |
766 |
int gran) { |
767 |
this.array = array; |
768 |
this.mapper = mapper; |
769 |
this.lo = lo; |
770 |
this.hi = hi; |
771 |
this.gran = gran; |
772 |
} |
773 |
|
774 |
protected void compute() { |
775 |
FJTransformSum right = null; |
776 |
int l = lo; |
777 |
int h = hi; |
778 |
int g = gran; |
779 |
while (h - l > g) { |
780 |
int mid = (l + h) >>> 1; |
781 |
FJTransformSum r = |
782 |
new FJTransformSum(array, mapper, mid, h, g); |
783 |
r.fork(); |
784 |
r.next = right; |
785 |
|
786 |
right = r; |
787 |
h = mid; |
788 |
} |
789 |
int x = 0; |
790 |
for (int i = l; i < h; ++i) |
791 |
x += mapper.map(array[i]); |
792 |
while (right != null) { |
793 |
right.join(); |
794 |
x += right.result; |
795 |
right = right.next; |
796 |
} |
797 |
result = x; |
798 |
} |
799 |
|
800 |
} |
801 |
|
802 |
/** |
803 |
* Fork/Join version of scan |
804 |
* |
805 |
* A basic version of scan is straightforward. |
806 |
* Keep dividing by two to threshold segment size, and then: |
807 |
* Pass 1: Create tree of partial sums for each segment |
808 |
* Pass 2: For each segment, cumulate with offset of left sibling |
809 |
* See G. Blelloch's http://www.cs.cmu.edu/~scandal/alg/scan.html |
810 |
* |
811 |
* This version improves performance within FJ framework: |
812 |
* a) It allows second pass of ready left-hand sides to proceed even |
813 |
* if some right-hand side first passes are still executing. |
814 |
* b) It collapses the first and second passes of segments for which |
815 |
* incoming cumulations are ready before summing. |
816 |
* c) It skips first pass for rightmost segment (whose |
817 |
* result is not needed for second pass). |
818 |
* |
819 |
*/ |
820 |
static final class FJCumulator extends AsyncAction { |
821 |
|
822 |
/** |
823 |
* Shared control across nodes |
824 |
*/ |
825 |
static final class Ctl { |
826 |
final int[] array; |
827 |
final int granularity; |
828 |
/** |
829 |
* The index of the max current consecutive |
830 |
* cumulation starting from leftmost. Initially zero. |
831 |
*/ |
832 |
volatile int consecutiveIndex; |
833 |
/** |
834 |
* The current consecutive cumulation |
835 |
*/ |
836 |
int consecutiveSum; |
837 |
|
838 |
Ctl(int[] array, int granularity) { |
839 |
this.array = array; |
840 |
this.granularity = granularity; |
841 |
} |
842 |
} |
843 |
|
844 |
final FJCumulator parent; |
845 |
final FJCumulator.Ctl ctl; |
846 |
FJCumulator left, right; |
847 |
final int lo; |
848 |
final int hi; |
849 |
|
850 |
/** Incoming cumulative sum */ |
851 |
int in; |
852 |
|
853 |
/** Sum of this subtree */ |
854 |
int out; |
855 |
|
856 |
/** |
857 |
* Phase/state control, updated only via transitionTo, for |
858 |
* CUMULATE, SUMMED, and FINISHED bits. |
859 |
*/ |
860 |
volatile int phase; |
861 |
|
862 |
/** |
863 |
* Phase bit. When false, segments compute only their sum. |
864 |
* When true, they cumulate array elements. CUMULATE is set at |
865 |
* root at beginning of second pass and then propagated |
866 |
* down. But it may also be set earlier in two cases when |
867 |
* cumulations are known to be ready: (1) For subtrees with |
868 |
* lo==0 (the left spine of tree) (2) Leaf nodes with |
869 |
* completed predecessors. |
870 |
*/ |
871 |
static final int CUMULATE = 1; |
872 |
|
873 |
/** |
874 |
* One bit join count. For leafs, set when summed. For |
875 |
* internal nodes, becomes true when one child is summed. |
876 |
* When second child finishes summing, it then moves up tree |
877 |
* to trigger cumulate phase. |
878 |
*/ |
879 |
static final int SUMMED = 2; |
880 |
|
881 |
/** |
882 |
* One bit join count. For leafs, set when cumulated. For |
883 |
* internal nodes, becomes true when one child is cumulated. |
884 |
* When second child finishes cumulating, it then moves up |
885 |
* tree, excecuting finish() at the root. |
886 |
*/ |
887 |
static final int FINISHED = 4; |
888 |
|
889 |
static final AtomicIntegerFieldUpdater<FJCumulator> phaseUpdater = |
890 |
AtomicIntegerFieldUpdater.newUpdater(FJCumulator.class, "phase"); |
891 |
|
892 |
FJCumulator(FJCumulator parent, |
893 |
FJCumulator.Ctl ctl, |
894 |
int lo, |
895 |
int hi) { |
896 |
this.parent = parent; |
897 |
this.ctl = ctl; |
898 |
this.lo = lo; |
899 |
this.hi = hi; |
900 |
} |
901 |
|
902 |
public void compute() { |
903 |
if (hi - lo <= ctl.granularity) { |
904 |
int cb = establishLeafPhase(); |
905 |
leafSum(cb); |
906 |
propagateLeafPhase(cb); |
907 |
} |
908 |
else |
909 |
spawnTasks(); |
910 |
} |
911 |
|
912 |
/** |
913 |
* decide which leaf action to take - sum, cumulate, or both |
914 |
* @return associated bit s |
915 |
*/ |
916 |
int establishLeafPhase() { |
917 |
for (;;) { |
918 |
int b = phase; |
919 |
if ((b & FINISHED) != 0) // already done |
920 |
return 0; |
921 |
int cb; |
922 |
if ((b & CUMULATE) != 0) |
923 |
cb = FINISHED; |
924 |
else if (lo == ctl.consecutiveIndex) |
925 |
cb = (SUMMED|FINISHED); |
926 |
else |
927 |
cb = SUMMED; |
928 |
if (phaseUpdater.compareAndSet(this, b, b|cb)) |
929 |
return cb; |
930 |
} |
931 |
} |
932 |
|
933 |
void propagateLeafPhase(int cb) { |
934 |
FJCumulator c = this; |
935 |
FJCumulator p = parent; |
936 |
for (;;) { |
937 |
if (p == null) { |
938 |
if ((cb & FINISHED) != 0) |
939 |
c.finish(); |
940 |
break; |
941 |
} |
942 |
int pb = p.phase; |
943 |
if ((pb & cb & FINISHED) != 0) { // both finished |
944 |
c = p; |
945 |
p = p.parent; |
946 |
} |
947 |
else if ((pb & cb & SUMMED) != 0) { // both summed |
948 |
int refork = 0; |
949 |
if ((pb & CUMULATE) == 0 && p.lo == 0) |
950 |
refork = CUMULATE; |
951 |
int next = pb|cb|refork; |
952 |
if (pb == next || |
953 |
phaseUpdater.compareAndSet(p, pb, next)) { |
954 |
if (refork != 0) |
955 |
p.fork(); |
956 |
cb = SUMMED; // drop finished bit |
957 |
c = p; |
958 |
p = p.parent; |
959 |
} |
960 |
} |
961 |
else if (phaseUpdater.compareAndSet(p, pb, pb|cb)) |
962 |
break; |
963 |
} |
964 |
} |
965 |
|
966 |
void leafSum(int cb) { |
967 |
int[] array = ctl.array; |
968 |
if (cb == SUMMED) { |
969 |
if (hi < array.length) { // skip rightmost |
970 |
int sum = 0; |
971 |
for (int i = lo; i < hi; ++i) |
972 |
sum += array[i]; |
973 |
out = sum; |
974 |
} |
975 |
} |
976 |
else if (cb == FINISHED) { |
977 |
int sum = in; |
978 |
for (int i = lo; i < hi; ++i) |
979 |
sum = array[i] += sum; |
980 |
} |
981 |
else if (cb == (SUMMED|FINISHED)) { |
982 |
int cin = ctl.consecutiveSum; |
983 |
int sum = cin; |
984 |
for (int i = lo; i < hi; ++i) |
985 |
sum = array[i] += sum; |
986 |
out = sum - cin; |
987 |
ctl.consecutiveSum = sum; |
988 |
ctl.consecutiveIndex = hi; |
989 |
} |
990 |
} |
991 |
|
992 |
/** |
993 |
* Returns true if can CAS CUMULATE bit true |
994 |
*/ |
995 |
boolean transitionToCumulate() { |
996 |
int c; |
997 |
while (((c = phase) & CUMULATE) == 0) |
998 |
if (phaseUpdater.compareAndSet(this, c, c | CUMULATE)) |
999 |
return true; |
1000 |
return false; |
1001 |
} |
1002 |
|
1003 |
void spawnTasks() { |
1004 |
if (left == null) { |
1005 |
int mid = (lo + hi) >>> 1; |
1006 |
left = new FJCumulator(this, ctl, lo, mid); |
1007 |
right = new FJCumulator(this, ctl, mid, hi); |
1008 |
} |
1009 |
|
1010 |
boolean cumulate = (phase & CUMULATE) != 0; |
1011 |
if (cumulate) { // push down sums |
1012 |
int cin = in; |
1013 |
left.in = cin; |
1014 |
right.in = cin + left.out; |
1015 |
} |
1016 |
|
1017 |
if (!cumulate || right.transitionToCumulate()) |
1018 |
right.fork(); |
1019 |
if (!cumulate || left.transitionToCumulate()) |
1020 |
left.compute(); |
1021 |
} |
1022 |
|
1023 |
} |
1024 |
|
1025 |
|
1026 |
/** |
1027 |
* Fork/Join version of FindAny |
1028 |
*/ |
1029 |
static final class FJFindAny extends RecursiveAction { |
1030 |
final int[] array; |
1031 |
final IntPredicate pred; |
1032 |
final VolatileInt result; |
1033 |
final int missing; |
1034 |
final int lo; |
1035 |
final int hi; |
1036 |
final int gran; |
1037 |
|
1038 |
FJFindAny(int[] array, |
1039 |
IntPredicate pred, |
1040 |
VolatileInt result, |
1041 |
int missing, |
1042 |
int lo, |
1043 |
int hi, |
1044 |
int gran) { |
1045 |
this.array = array; |
1046 |
this.pred = pred; |
1047 |
this.result = result; |
1048 |
this.missing = missing; |
1049 |
this.lo = lo; |
1050 |
this.hi = hi; |
1051 |
this.gran = gran; |
1052 |
} |
1053 |
|
1054 |
void seqCompute() { |
1055 |
for (int i = lo; i < hi; ++i) { |
1056 |
int x = array[i]; |
1057 |
if (pred.evaluate(x) && result.value == missing) { |
1058 |
result.value = x; |
1059 |
break; |
1060 |
} |
1061 |
} |
1062 |
} |
1063 |
|
1064 |
protected void compute() { |
1065 |
if (result.value != missing) |
1066 |
return; |
1067 |
if (hi - lo <= gran) { |
1068 |
seqCompute(); |
1069 |
return; |
1070 |
} |
1071 |
int mid = (lo + hi) >>> 1; |
1072 |
FJFindAny left = |
1073 |
new FJFindAny(array, pred, result, missing, lo, mid, gran); |
1074 |
left.fork(); |
1075 |
FJFindAny right = |
1076 |
new FJFindAny(array, pred, result, missing, mid, hi, gran); |
1077 |
right.invoke(); |
1078 |
if (result.value != missing) |
1079 |
left.cancel(); |
1080 |
else |
1081 |
left.join(); |
1082 |
} |
1083 |
} |
1084 |
|
1085 |
/** |
1086 |
* Fork/Join version of FindAll |
1087 |
*/ |
1088 |
static final class FJFindAll extends RecursiveAction { |
1089 |
final int[] array; |
1090 |
final IntPredicate pred; |
1091 |
final List<Integer> result; |
1092 |
final int lo; |
1093 |
final int hi; |
1094 |
final int gran; |
1095 |
|
1096 |
FJFindAll(int[] array, |
1097 |
IntPredicate pred, |
1098 |
List<Integer> result, |
1099 |
int lo, |
1100 |
int hi, |
1101 |
int gran) { |
1102 |
this.array = array; |
1103 |
this.pred = pred; |
1104 |
this.result = result; |
1105 |
this.lo = lo; |
1106 |
this.hi = hi; |
1107 |
this.gran = gran; |
1108 |
} |
1109 |
|
1110 |
|
1111 |
void seqCompute() { |
1112 |
for (int i = lo; i < hi; ++i) { |
1113 |
int x = array[i]; |
1114 |
if (pred.evaluate(x)) |
1115 |
result.add(x); |
1116 |
} |
1117 |
} |
1118 |
|
1119 |
protected void compute() { |
1120 |
if (hi - lo <= gran) { |
1121 |
seqCompute(); |
1122 |
return; |
1123 |
} |
1124 |
int mid = (lo + hi) >>> 1; |
1125 |
FJFindAll left = |
1126 |
new FJFindAll(array, pred, result, lo, mid, gran); |
1127 |
FJFindAll right = |
1128 |
new FJFindAll(array, pred, result, mid, hi, gran); |
1129 |
coInvoke(left, right); |
1130 |
} |
1131 |
} |
1132 |
|
1133 |
/* |
1134 |
* Sort algorithm based mainly on CilkSort |
1135 |
* <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>: |
1136 |
* if array size is small, just use a sequential quicksort |
1137 |
* Otherwise: |
1138 |
* 1. Break array in half. |
1139 |
* 2. For each half, |
1140 |
* a. break the half in half (i.e., quarters), |
1141 |
* b. sort the quarters |
1142 |
* c. merge them together |
1143 |
* 3. merge together the two halves. |
1144 |
* |
1145 |
* One reason for splitting in quarters is that this guarantees |
1146 |
* that the final sort is in the main array, not the workspace array. |
1147 |
* (workspace and main swap roles on each subsort step.) |
1148 |
* |
1149 |
*/ |
1150 |
|
1151 |
// Cutoff for when to do sequential versus parallel sorts and merges |
1152 |
static final int SEQUENTIAL_THRESHOLD = 256; // == 16 * 16 |
1153 |
// Todo: check for #cpu sensitivity |
1154 |
|
1155 |
|
1156 |
static class FJSorter extends RecursiveAction { |
1157 |
final int[] a; // Array to be sorted. |
1158 |
final int ao; // origin of the part of array we deal with |
1159 |
final int[] w; // workspace array for merge |
1160 |
final int wo; // its origin |
1161 |
final int n; // Number of elements in (sub)arrays. |
1162 |
|
1163 |
FJSorter (int[] a, int ao, int[] w, int wo, int n) { |
1164 |
this.a = a; this.ao = ao; this.w = w; this.wo = wo; this.n = n; |
1165 |
} |
1166 |
|
1167 |
protected void compute() { |
1168 |
if (n <= SEQUENTIAL_THRESHOLD) |
1169 |
quickSort(a, ao, ao+n-1); |
1170 |
else { |
1171 |
int q = n >>> 2; // lower quarter index |
1172 |
int h = n >>> 1; // half |
1173 |
int u = h + q; // upper quarter |
1174 |
|
1175 |
coInvoke(new SubSorter(new FJSorter(a, ao, w, wo, q), |
1176 |
new FJSorter(a, ao+q, w, wo+q, q), |
1177 |
new FJMerger(a, ao, q, ao+q, q, |
1178 |
w, wo)), |
1179 |
new SubSorter(new FJSorter(a, ao+h, w, wo+h, q), |
1180 |
new FJSorter(a, ao+u, w, wo+u, n-u), |
1181 |
new FJMerger(a, ao+h, q, ao+u, n-u, |
1182 |
w, wo+h))); |
1183 |
new FJMerger(w, wo, h, wo+h, n-h, a, ao).compute(); |
1184 |
} |
1185 |
} |
1186 |
|
1187 |
} |
1188 |
|
1189 |
/** |
1190 |
* A boring class to run two given sorts in parallel, then merge them. |
1191 |
*/ |
1192 |
static class SubSorter extends RecursiveAction { |
1193 |
final FJSorter left; |
1194 |
final FJSorter right; |
1195 |
final FJMerger merger; |
1196 |
SubSorter(FJSorter left, FJSorter right, FJMerger merger) { |
1197 |
this.left = left; this.right = right; this.merger = merger; |
1198 |
} |
1199 |
protected void compute() { |
1200 |
coInvoke(left, right); |
1201 |
merger.invoke(); |
1202 |
} |
1203 |
} |
1204 |
|
1205 |
static class FJMerger extends RecursiveAction { |
1206 |
final int[] a; // partitioned array. |
1207 |
final int lo; // relative origin of left side |
1208 |
final int ln; // number of elements on left |
1209 |
final int ro; // relative origin of right side |
1210 |
final int rn; // number of elements on right |
1211 |
|
1212 |
final int[] w; // Output array. |
1213 |
final int wo; |
1214 |
|
1215 |
FJMerger (int[] a, int lo, int ln, int ro, int rn, int[] w, int wo) { |
1216 |
this.a = a; |
1217 |
this.w = w; |
1218 |
this.wo = wo; |
1219 |
// Left side should be largest of the two for fiding split. |
1220 |
// Swap now, since left/right doesn't otherwise matter |
1221 |
if (ln >= rn) { |
1222 |
this.lo = lo; this.ln = ln; |
1223 |
this.ro = ro; this.rn = rn; |
1224 |
} |
1225 |
else { |
1226 |
this.lo = ro; this.ln = rn; |
1227 |
this.ro = lo; this.rn = ln; |
1228 |
} |
1229 |
} |
1230 |
|
1231 |
protected void compute() { |
1232 |
/* |
1233 |
If partiions are small, then just sequentially merge. |
1234 |
Otherwise: |
1235 |
1. Split Left partition in half. |
1236 |
2. Find the greatest point in Right partition |
1237 |
less than the beginning of the second half of left, |
1238 |
via binary search. |
1239 |
3. In parallel: |
1240 |
merge left half of L with elements of R up to split point |
1241 |
merge right half of L with elements of R past split point |
1242 |
*/ |
1243 |
|
1244 |
if (ln <= SEQUENTIAL_THRESHOLD) |
1245 |
merge(); |
1246 |
else { |
1247 |
int lh = ln >>> 1; |
1248 |
int ls = lo + lh; // index of split |
1249 |
int split = a[ls]; |
1250 |
int rl = 0; |
1251 |
int rh = rn; |
1252 |
while (rl < rh) { |
1253 |
int mid = (rl + rh) >>> 1; |
1254 |
if (split <= a[ro + mid]) |
1255 |
rh = mid; |
1256 |
else |
1257 |
rl = mid + 1; |
1258 |
} |
1259 |
coInvoke(new FJMerger(a, lo, lh, ro, rh, w, wo), |
1260 |
new FJMerger(a, ls, ln-lh, ro+rh, rn-rh, w, wo+lh+rh)); |
1261 |
} |
1262 |
} |
1263 |
|
1264 |
/** a standard sequential merge */ |
1265 |
void merge() { |
1266 |
int l = lo; |
1267 |
int lFence = lo+ln; |
1268 |
int r = ro; |
1269 |
int rFence = ro+rn; |
1270 |
int k = wo; |
1271 |
while (l < lFence && r < rFence) |
1272 |
w[k++] = (a[l] <= a[r])? a[l++] : a[r++]; |
1273 |
while (l < lFence) |
1274 |
w[k++] = a[l++]; |
1275 |
while (r < rFence) |
1276 |
w[k++] = a[r++]; |
1277 |
} |
1278 |
} |
1279 |
|
1280 |
// Cutoff for when to use insertion-sort instead of quicksort |
1281 |
static final int INSERTION_SORT_THRESHOLD = 16; |
1282 |
|
1283 |
/** A standard sequential quicksort */ |
1284 |
static void quickSort(int[] a, int lo, int hi) { |
1285 |
// If under threshold, use insertion sort |
1286 |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
1287 |
for (int i = lo + 1; i <= hi; i++) { |
1288 |
int t = a[i]; |
1289 |
int j = i - 1; |
1290 |
while (j >= lo && t < a[j]) { |
1291 |
a[j+1] = a[j]; |
1292 |
--j; |
1293 |
} |
1294 |
a[j+1] = t; |
1295 |
} |
1296 |
return; |
1297 |
} |
1298 |
|
1299 |
// Use median-of-three(lo, mid, hi) to pick a partition. |
1300 |
// Also swap them into relative order while we are at it. |
1301 |
int mid = (lo + hi) >>> 1; |
1302 |
if (a[lo] > a[mid]) { |
1303 |
int t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
1304 |
} |
1305 |
if (a[mid] > a[hi]) { |
1306 |
int t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
1307 |
if (a[lo] > a[mid]) { |
1308 |
t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
1309 |
} |
1310 |
} |
1311 |
|
1312 |
int pivot = a[mid]; |
1313 |
int left = lo+1; |
1314 |
int right = hi-1; |
1315 |
for (;;) { |
1316 |
while (pivot < a[right]) |
1317 |
--right; |
1318 |
while (left < right && pivot >= a[left]) |
1319 |
++left; |
1320 |
if (left < right) { |
1321 |
int t = a[left]; a[left] = a[right]; a[right] = t; |
1322 |
--right; |
1323 |
} |
1324 |
else break; |
1325 |
} |
1326 |
quickSort(a, lo, left); |
1327 |
quickSort(a, left+1, hi); |
1328 |
} |
1329 |
|
1330 |
|
1331 |
|
1332 |
} |