1 /*
2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util;
26
27 import java.util.concurrent.RecursiveAction;
28 import java.util.concurrent.CountedCompleter;
29
30 /**
31 * Helper utilities for the parallel sort methods in Arrays.parallelSort.
32 *
33 * For each primitive type, plus Object, we define a static class to
34 * contain the Sorter and Merger implementations for that type:
35 *
36 * Sorter classes based mainly on CilkSort
37 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
38 * Basic algorithm:
39 * if array size is small, just use a sequential quicksort (via Arrays.sort)
40 * Otherwise:
41 * 1. Break array in half.
42 * 2. For each half,
43 * a. break the half in half (i.e., quarters),
44 * b. sort the quarters
45 * c. merge them together
46 * 3. merge together the two halves.
47 *
48 * One reason for splitting in quarters is that this guarantees that
49 * the final sort is in the main array, not the workspace array.
50 * (workspace and main swap roles on each subsort step.) Leaf-level
51 * sorts use the associated sequential sort.
52 *
53 * Merger classes perform merging for Sorter. They are structured
54 * such that if the underlying sort is stable (as is true for
55 * TimSort), then so is the full sort. If big enough, they split the
56 * largest of the two partitions in half, find the greatest point in
57 * smaller partition less than the beginning of the second half of
58 * larger via binary search; and then merge in parallel the two
59 * partitions. In part to ensure tasks are triggered in
60 * stability-preserving order, the current CountedCompleter design
61 * requires some little tasks to serve as place holders for triggering
62 * completion tasks. These classes (EmptyCompleter and Relay) don't
63 * need to keep track of the arrays, and are never themselves forked,
64 * so don't hold any task state.
65 *
66 * The primitive class versions (FJByte... FJDouble) are
67 * identical to each other except for type declarations.
68 *
69 * The base sequential sorts rely on non-public versions of TimSort,
70 * ComparableTimSort, and DualPivotQuicksort sort methods that accept
71 * temp workspace array slices that we will have already allocated, so
72 * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
73 * sort, that does not ever use a workspace array.)
74 */
75 /*package*/ class ArraysParallelSortHelpers {
76
77 /*
78 * Style note: The task classes have a lot of parameters, that are
79 * stored as task fields and copied to local variables and used in
80 * compute() methods, We pack these into as few lines as possible,
81 * and hoist consistency checks among them before main loops, to
82 * reduce distraction.
83 */
84
85 /**
86 * A placeholder task for Sorters, used for the lowest
87 * quartile task, that does not need to maintain array state.
88 */
89 static final class EmptyCompleter extends CountedCompleter<Void> {
90 static final long serialVersionUID = 2446542900576103244L;
91 EmptyCompleter(CountedCompleter<?> p) { super(p); }
92 public final void compute() { }
93 }
118 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
119 int wbase, int gran,
120 Comparator<? super T> comparator) {
121 super(par);
122 this.a = a; this.w = w; this.base = base; this.size = size;
123 this.wbase = wbase; this.gran = gran;
124 this.comparator = comparator;
125 }
126 public final void compute() {
127 CountedCompleter<?> s = this;
128 Comparator<? super T> c = this.comparator;
129 T[] a = this.a, w = this.w; // localize all params
130 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
131 while (n > g) {
132 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
133 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
134 wb+h, n-h, b, g, c));
135 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
136 b+u, n-u, wb+h, g, c));
137 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
138 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
139 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
140 b+q, h-q, wb, g, c));
141 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
142 s = new EmptyCompleter(bc);
143 n = q;
144 }
145 TimSort.sort(a, b, b + n, c, w, wb, n);
146 s.tryComplete();
147 }
148 }
149
150 static final class Merger<T> extends CountedCompleter<Void> {
151 static final long serialVersionUID = 2446542900576103244L;
152 final T[] a, w; // main and workspace arrays
153 final int lbase, lsize, rbase, rsize, wbase, gran;
154 Comparator<? super T> comparator;
155 Merger(CountedCompleter<?> par, T[] a, T[] w,
156 int lbase, int lsize, int rbase,
157 int rsize, int wbase, int gran,
158 Comparator<? super T> comparator) {
209 }
210
211 int lf = lb + ln, rf = rb + rn; // index bounds
212 while (lb < lf && rb < rf) {
213 T t, al, ar;
214 if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
215 lb++; t = al;
216 }
217 else {
218 rb++; t = ar;
219 }
220 w[k++] = t;
221 }
222 if (rb < rf)
223 System.arraycopy(a, rb, w, k, rf - rb);
224 else if (lb < lf)
225 System.arraycopy(a, lb, w, k, lf - lb);
226
227 tryComplete();
228 }
229
230 }
231 } // FJObject
232
233 /** byte support class */
234 static final class FJByte {
235 static final class Sorter extends CountedCompleter<Void> {
236 static final long serialVersionUID = 2446542900576103244L;
237 final byte[] a, w;
238 final int base, size, wbase, gran;
239 Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
240 int size, int wbase, int gran) {
241 super(par);
242 this.a = a; this.w = w; this.base = base; this.size = size;
243 this.wbase = wbase; this.gran = gran;
244 }
245 public final void compute() {
246 CountedCompleter<?> s = this;
247 byte[] a = this.a, w = this.w; // localize all params
248 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
249 while (n > g) {
250 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
251 Relay fc = new Relay(new Merger(s, w, a, wb, h,
252 wb+h, n-h, b, g));
253 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
254 b+u, n-u, wb+h, g));
255 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
256 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
257 Relay bc = new Relay(new Merger(fc, a, w, b, q,
258 b+q, h-q, wb, g));
259 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
260 s = new EmptyCompleter(bc);
261 n = q;
262 }
263 DualPivotQuicksort.sort(a, b, b + n - 1);
264 s.tryComplete();
265 }
266 }
267
268 static final class Merger extends CountedCompleter<Void> {
269 static final long serialVersionUID = 2446542900576103244L;
270 final byte[] a, w; // main and workspace arrays
271 final int lbase, lsize, rbase, rsize, wbase, gran;
272 Merger(CountedCompleter<?> par, byte[] a, byte[] w,
273 int lbase, int lsize, int rbase,
274 int rsize, int wbase, int gran) {
275 super(par);
276 this.a = a; this.w = w;
277 this.lbase = lbase; this.lsize = lsize;
278 this.rbase = rbase; this.rsize = rsize;
279 this.wbase = wbase; this.gran = gran;
280 }
281
282 public final void compute() {
283 byte[] a = this.a, w = this.w; // localize all params
284 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
285 rn = this.rsize, k = this.wbase, g = this.gran;
286 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
287 throw new IllegalStateException(); // hoist checks
288 for (int lh, rh;;) { // split larger, find point in smaller
289 if (ln >= rn) {
290 if (ln <= g)
291 break;
292 rh = rn;
293 byte split = a[(lh = ln >>> 1) + lb];
294 for (int lo = 0; lo < rh; ) {
295 int rm = (lo + rh) >>> 1;
296 if (split <= a[rm + rb])
297 rh = rm;
298 else
299 lo = rm + 1;
300 }
301 }
302 else {
303 if (rn <= g)
304 break;
305 lh = ln;
306 byte split = a[(rh = rn >>> 1) + rb];
307 for (int lo = 0; lo < lh; ) {
308 int lm = (lo + lh) >>> 1;
309 if (split <= a[lm + lb])
310 lh = lm;
311 else
312 lo = lm + 1;
313 }
314 }
315 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
316 rb + rh, rn - rh,
317 k + lh + rh, g);
318 rn = rh;
319 ln = lh;
320 addToPendingCount(1);
321 m.fork();
322 }
323
324 int lf = lb + ln, rf = rb + rn; // index bounds
325 while (lb < lf && rb < rf) {
326 byte t, al, ar;
327 if ((al = a[lb]) <= (ar = a[rb])) {
328 lb++; t = al;
329 }
330 else {
331 rb++; t = ar;
332 }
333 w[k++] = t;
334 }
335 if (rb < rf)
336 System.arraycopy(a, rb, w, k, rf - rb);
337 else if (lb < lf)
338 System.arraycopy(a, lb, w, k, lf - lb);
339 tryComplete();
340 }
341 }
342 } // FJByte
343
344 /** char support class */
345 static final class FJChar {
346 static final class Sorter extends CountedCompleter<Void> {
347 static final long serialVersionUID = 2446542900576103244L;
348 final char[] a, w;
349 final int base, size, wbase, gran;
350 Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
351 int size, int wbase, int gran) {
352 super(par);
353 this.a = a; this.w = w; this.base = base; this.size = size;
354 this.wbase = wbase; this.gran = gran;
355 }
356 public final void compute() {
357 CountedCompleter<?> s = this;
358 char[] a = this.a, w = this.w; // localize all params
359 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
360 while (n > g) {
361 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
362 Relay fc = new Relay(new Merger(s, w, a, wb, h,
363 wb+h, n-h, b, g));
364 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
365 b+u, n-u, wb+h, g));
366 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
367 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
368 Relay bc = new Relay(new Merger(fc, a, w, b, q,
369 b+q, h-q, wb, g));
370 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
371 s = new EmptyCompleter(bc);
372 n = q;
373 }
374 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
375 s.tryComplete();
376 }
377 }
378
379 static final class Merger extends CountedCompleter<Void> {
380 static final long serialVersionUID = 2446542900576103244L;
381 final char[] a, w; // main and workspace arrays
382 final int lbase, lsize, rbase, rsize, wbase, gran;
383 Merger(CountedCompleter<?> par, char[] a, char[] w,
384 int lbase, int lsize, int rbase,
385 int rsize, int wbase, int gran) {
386 super(par);
387 this.a = a; this.w = w;
388 this.lbase = lbase; this.lsize = lsize;
389 this.rbase = rbase; this.rsize = rsize;
390 this.wbase = wbase; this.gran = gran;
391 }
392
393 public final void compute() {
394 char[] a = this.a, w = this.w; // localize all params
395 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
396 rn = this.rsize, k = this.wbase, g = this.gran;
397 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
398 throw new IllegalStateException(); // hoist checks
399 for (int lh, rh;;) { // split larger, find point in smaller
400 if (ln >= rn) {
401 if (ln <= g)
402 break;
403 rh = rn;
404 char split = a[(lh = ln >>> 1) + lb];
405 for (int lo = 0; lo < rh; ) {
406 int rm = (lo + rh) >>> 1;
407 if (split <= a[rm + rb])
408 rh = rm;
409 else
410 lo = rm + 1;
411 }
412 }
413 else {
414 if (rn <= g)
415 break;
416 lh = ln;
417 char split = a[(rh = rn >>> 1) + rb];
418 for (int lo = 0; lo < lh; ) {
419 int lm = (lo + lh) >>> 1;
420 if (split <= a[lm + lb])
421 lh = lm;
422 else
423 lo = lm + 1;
424 }
425 }
426 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
427 rb + rh, rn - rh,
428 k + lh + rh, g);
429 rn = rh;
430 ln = lh;
431 addToPendingCount(1);
432 m.fork();
433 }
434
435 int lf = lb + ln, rf = rb + rn; // index bounds
436 while (lb < lf && rb < rf) {
437 char t, al, ar;
438 if ((al = a[lb]) <= (ar = a[rb])) {
439 lb++; t = al;
440 }
441 else {
442 rb++; t = ar;
443 }
444 w[k++] = t;
445 }
446 if (rb < rf)
447 System.arraycopy(a, rb, w, k, rf - rb);
448 else if (lb < lf)
449 System.arraycopy(a, lb, w, k, lf - lb);
450 tryComplete();
451 }
452 }
453 } // FJChar
454
455 /** short support class */
456 static final class FJShort {
457 static final class Sorter extends CountedCompleter<Void> {
458 static final long serialVersionUID = 2446542900576103244L;
459 final short[] a, w;
460 final int base, size, wbase, gran;
461 Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
462 int size, int wbase, int gran) {
463 super(par);
464 this.a = a; this.w = w; this.base = base; this.size = size;
465 this.wbase = wbase; this.gran = gran;
466 }
467 public final void compute() {
468 CountedCompleter<?> s = this;
469 short[] a = this.a, w = this.w; // localize all params
470 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
471 while (n > g) {
472 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
473 Relay fc = new Relay(new Merger(s, w, a, wb, h,
474 wb+h, n-h, b, g));
475 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
476 b+u, n-u, wb+h, g));
477 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
478 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
479 Relay bc = new Relay(new Merger(fc, a, w, b, q,
480 b+q, h-q, wb, g));
481 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
482 s = new EmptyCompleter(bc);
483 n = q;
484 }
485 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
486 s.tryComplete();
487 }
488 }
489
490 static final class Merger extends CountedCompleter<Void> {
491 static final long serialVersionUID = 2446542900576103244L;
492 final short[] a, w; // main and workspace arrays
493 final int lbase, lsize, rbase, rsize, wbase, gran;
494 Merger(CountedCompleter<?> par, short[] a, short[] w,
495 int lbase, int lsize, int rbase,
496 int rsize, int wbase, int gran) {
497 super(par);
498 this.a = a; this.w = w;
499 this.lbase = lbase; this.lsize = lsize;
500 this.rbase = rbase; this.rsize = rsize;
501 this.wbase = wbase; this.gran = gran;
502 }
503
504 public final void compute() {
505 short[] a = this.a, w = this.w; // localize all params
506 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
507 rn = this.rsize, k = this.wbase, g = this.gran;
508 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
509 throw new IllegalStateException(); // hoist checks
510 for (int lh, rh;;) { // split larger, find point in smaller
511 if (ln >= rn) {
512 if (ln <= g)
513 break;
514 rh = rn;
515 short split = a[(lh = ln >>> 1) + lb];
516 for (int lo = 0; lo < rh; ) {
517 int rm = (lo + rh) >>> 1;
518 if (split <= a[rm + rb])
519 rh = rm;
520 else
521 lo = rm + 1;
522 }
523 }
524 else {
525 if (rn <= g)
526 break;
527 lh = ln;
528 short split = a[(rh = rn >>> 1) + rb];
529 for (int lo = 0; lo < lh; ) {
530 int lm = (lo + lh) >>> 1;
531 if (split <= a[lm + lb])
532 lh = lm;
533 else
534 lo = lm + 1;
535 }
536 }
537 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
538 rb + rh, rn - rh,
539 k + lh + rh, g);
540 rn = rh;
541 ln = lh;
542 addToPendingCount(1);
543 m.fork();
544 }
545
546 int lf = lb + ln, rf = rb + rn; // index bounds
547 while (lb < lf && rb < rf) {
548 short t, al, ar;
549 if ((al = a[lb]) <= (ar = a[rb])) {
550 lb++; t = al;
551 }
552 else {
553 rb++; t = ar;
554 }
555 w[k++] = t;
556 }
557 if (rb < rf)
558 System.arraycopy(a, rb, w, k, rf - rb);
559 else if (lb < lf)
560 System.arraycopy(a, lb, w, k, lf - lb);
561 tryComplete();
562 }
563 }
564 } // FJShort
565
566 /** int support class */
567 static final class FJInt {
568 static final class Sorter extends CountedCompleter<Void> {
569 static final long serialVersionUID = 2446542900576103244L;
570 final int[] a, w;
571 final int base, size, wbase, gran;
572 Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
573 int size, int wbase, int gran) {
574 super(par);
575 this.a = a; this.w = w; this.base = base; this.size = size;
576 this.wbase = wbase; this.gran = gran;
577 }
578 public final void compute() {
579 CountedCompleter<?> s = this;
580 int[] a = this.a, w = this.w; // localize all params
581 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
582 while (n > g) {
583 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
584 Relay fc = new Relay(new Merger(s, w, a, wb, h,
585 wb+h, n-h, b, g));
586 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
587 b+u, n-u, wb+h, g));
588 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
589 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
590 Relay bc = new Relay(new Merger(fc, a, w, b, q,
591 b+q, h-q, wb, g));
592 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
593 s = new EmptyCompleter(bc);
594 n = q;
595 }
596 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
597 s.tryComplete();
598 }
599 }
600
601 static final class Merger extends CountedCompleter<Void> {
602 static final long serialVersionUID = 2446542900576103244L;
603 final int[] a, w; // main and workspace arrays
604 final int lbase, lsize, rbase, rsize, wbase, gran;
605 Merger(CountedCompleter<?> par, int[] a, int[] w,
606 int lbase, int lsize, int rbase,
607 int rsize, int wbase, int gran) {
608 super(par);
609 this.a = a; this.w = w;
610 this.lbase = lbase; this.lsize = lsize;
611 this.rbase = rbase; this.rsize = rsize;
612 this.wbase = wbase; this.gran = gran;
613 }
614
615 public final void compute() {
616 int[] a = this.a, w = this.w; // localize all params
617 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
618 rn = this.rsize, k = this.wbase, g = this.gran;
619 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
620 throw new IllegalStateException(); // hoist checks
621 for (int lh, rh;;) { // split larger, find point in smaller
622 if (ln >= rn) {
623 if (ln <= g)
624 break;
625 rh = rn;
626 int split = a[(lh = ln >>> 1) + lb];
627 for (int lo = 0; lo < rh; ) {
628 int rm = (lo + rh) >>> 1;
629 if (split <= a[rm + rb])
630 rh = rm;
631 else
632 lo = rm + 1;
633 }
634 }
635 else {
636 if (rn <= g)
637 break;
638 lh = ln;
639 int split = a[(rh = rn >>> 1) + rb];
640 for (int lo = 0; lo < lh; ) {
641 int lm = (lo + lh) >>> 1;
642 if (split <= a[lm + lb])
643 lh = lm;
644 else
645 lo = lm + 1;
646 }
647 }
648 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
649 rb + rh, rn - rh,
650 k + lh + rh, g);
651 rn = rh;
652 ln = lh;
653 addToPendingCount(1);
654 m.fork();
655 }
656
657 int lf = lb + ln, rf = rb + rn; // index bounds
658 while (lb < lf && rb < rf) {
659 int t, al, ar;
660 if ((al = a[lb]) <= (ar = a[rb])) {
661 lb++; t = al;
662 }
663 else {
664 rb++; t = ar;
665 }
666 w[k++] = t;
667 }
668 if (rb < rf)
669 System.arraycopy(a, rb, w, k, rf - rb);
670 else if (lb < lf)
671 System.arraycopy(a, lb, w, k, lf - lb);
672 tryComplete();
673 }
674 }
675 } // FJInt
676
677 /** long support class */
678 static final class FJLong {
679 static final class Sorter extends CountedCompleter<Void> {
680 static final long serialVersionUID = 2446542900576103244L;
681 final long[] a, w;
682 final int base, size, wbase, gran;
683 Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
684 int size, int wbase, int gran) {
685 super(par);
686 this.a = a; this.w = w; this.base = base; this.size = size;
687 this.wbase = wbase; this.gran = gran;
688 }
689 public final void compute() {
690 CountedCompleter<?> s = this;
691 long[] a = this.a, w = this.w; // localize all params
692 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
693 while (n > g) {
694 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
695 Relay fc = new Relay(new Merger(s, w, a, wb, h,
696 wb+h, n-h, b, g));
697 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
698 b+u, n-u, wb+h, g));
699 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
700 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
701 Relay bc = new Relay(new Merger(fc, a, w, b, q,
702 b+q, h-q, wb, g));
703 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
704 s = new EmptyCompleter(bc);
705 n = q;
706 }
707 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
708 s.tryComplete();
709 }
710 }
711
712 static final class Merger extends CountedCompleter<Void> {
713 static final long serialVersionUID = 2446542900576103244L;
714 final long[] a, w; // main and workspace arrays
715 final int lbase, lsize, rbase, rsize, wbase, gran;
716 Merger(CountedCompleter<?> par, long[] a, long[] w,
717 int lbase, int lsize, int rbase,
718 int rsize, int wbase, int gran) {
719 super(par);
720 this.a = a; this.w = w;
721 this.lbase = lbase; this.lsize = lsize;
722 this.rbase = rbase; this.rsize = rsize;
723 this.wbase = wbase; this.gran = gran;
724 }
725
726 public final void compute() {
727 long[] a = this.a, w = this.w; // localize all params
728 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
729 rn = this.rsize, k = this.wbase, g = this.gran;
730 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
731 throw new IllegalStateException(); // hoist checks
732 for (int lh, rh;;) { // split larger, find point in smaller
733 if (ln >= rn) {
734 if (ln <= g)
735 break;
736 rh = rn;
737 long split = a[(lh = ln >>> 1) + lb];
738 for (int lo = 0; lo < rh; ) {
739 int rm = (lo + rh) >>> 1;
740 if (split <= a[rm + rb])
741 rh = rm;
742 else
743 lo = rm + 1;
744 }
745 }
746 else {
747 if (rn <= g)
748 break;
749 lh = ln;
750 long split = a[(rh = rn >>> 1) + rb];
751 for (int lo = 0; lo < lh; ) {
752 int lm = (lo + lh) >>> 1;
753 if (split <= a[lm + lb])
754 lh = lm;
755 else
756 lo = lm + 1;
757 }
758 }
759 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
760 rb + rh, rn - rh,
761 k + lh + rh, g);
762 rn = rh;
763 ln = lh;
764 addToPendingCount(1);
765 m.fork();
766 }
767
768 int lf = lb + ln, rf = rb + rn; // index bounds
769 while (lb < lf && rb < rf) {
770 long t, al, ar;
771 if ((al = a[lb]) <= (ar = a[rb])) {
772 lb++; t = al;
773 }
774 else {
775 rb++; t = ar;
776 }
777 w[k++] = t;
778 }
779 if (rb < rf)
780 System.arraycopy(a, rb, w, k, rf - rb);
781 else if (lb < lf)
782 System.arraycopy(a, lb, w, k, lf - lb);
783 tryComplete();
784 }
785 }
786 } // FJLong
787
788 /** float support class */
789 static final class FJFloat {
790 static final class Sorter extends CountedCompleter<Void> {
791 static final long serialVersionUID = 2446542900576103244L;
792 final float[] a, w;
793 final int base, size, wbase, gran;
794 Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
795 int size, int wbase, int gran) {
796 super(par);
797 this.a = a; this.w = w; this.base = base; this.size = size;
798 this.wbase = wbase; this.gran = gran;
799 }
800 public final void compute() {
801 CountedCompleter<?> s = this;
802 float[] a = this.a, w = this.w; // localize all params
803 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
804 while (n > g) {
805 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
806 Relay fc = new Relay(new Merger(s, w, a, wb, h,
807 wb+h, n-h, b, g));
808 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
809 b+u, n-u, wb+h, g));
810 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
811 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
812 Relay bc = new Relay(new Merger(fc, a, w, b, q,
813 b+q, h-q, wb, g));
814 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
815 s = new EmptyCompleter(bc);
816 n = q;
817 }
818 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
819 s.tryComplete();
820 }
821 }
822
823 static final class Merger extends CountedCompleter<Void> {
824 static final long serialVersionUID = 2446542900576103244L;
825 final float[] a, w; // main and workspace arrays
826 final int lbase, lsize, rbase, rsize, wbase, gran;
827 Merger(CountedCompleter<?> par, float[] a, float[] w,
828 int lbase, int lsize, int rbase,
829 int rsize, int wbase, int gran) {
830 super(par);
831 this.a = a; this.w = w;
832 this.lbase = lbase; this.lsize = lsize;
833 this.rbase = rbase; this.rsize = rsize;
834 this.wbase = wbase; this.gran = gran;
835 }
836
837 public final void compute() {
838 float[] a = this.a, w = this.w; // localize all params
839 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
840 rn = this.rsize, k = this.wbase, g = this.gran;
841 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
842 throw new IllegalStateException(); // hoist checks
843 for (int lh, rh;;) { // split larger, find point in smaller
844 if (ln >= rn) {
845 if (ln <= g)
846 break;
847 rh = rn;
848 float split = a[(lh = ln >>> 1) + lb];
849 for (int lo = 0; lo < rh; ) {
850 int rm = (lo + rh) >>> 1;
851 if (split <= a[rm + rb])
852 rh = rm;
853 else
854 lo = rm + 1;
855 }
856 }
857 else {
858 if (rn <= g)
859 break;
860 lh = ln;
861 float split = a[(rh = rn >>> 1) + rb];
862 for (int lo = 0; lo < lh; ) {
863 int lm = (lo + lh) >>> 1;
864 if (split <= a[lm + lb])
865 lh = lm;
866 else
867 lo = lm + 1;
868 }
869 }
870 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
871 rb + rh, rn - rh,
872 k + lh + rh, g);
873 rn = rh;
874 ln = lh;
875 addToPendingCount(1);
876 m.fork();
877 }
878
879 int lf = lb + ln, rf = rb + rn; // index bounds
880 while (lb < lf && rb < rf) {
881 float t, al, ar;
882 if ((al = a[lb]) <= (ar = a[rb])) {
883 lb++; t = al;
884 }
885 else {
886 rb++; t = ar;
887 }
888 w[k++] = t;
889 }
890 if (rb < rf)
891 System.arraycopy(a, rb, w, k, rf - rb);
892 else if (lb < lf)
893 System.arraycopy(a, lb, w, k, lf - lb);
894 tryComplete();
895 }
896 }
897 } // FJFloat
898
899 /** double support class */
900 static final class FJDouble {
901 static final class Sorter extends CountedCompleter<Void> {
902 static final long serialVersionUID = 2446542900576103244L;
903 final double[] a, w;
904 final int base, size, wbase, gran;
905 Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
906 int size, int wbase, int gran) {
907 super(par);
908 this.a = a; this.w = w; this.base = base; this.size = size;
909 this.wbase = wbase; this.gran = gran;
910 }
911 public final void compute() {
912 CountedCompleter<?> s = this;
913 double[] a = this.a, w = this.w; // localize all params
914 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
915 while (n > g) {
916 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
917 Relay fc = new Relay(new Merger(s, w, a, wb, h,
918 wb+h, n-h, b, g));
919 Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
920 b+u, n-u, wb+h, g));
921 new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
922 new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
923 Relay bc = new Relay(new Merger(fc, a, w, b, q,
924 b+q, h-q, wb, g));
925 new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
926 s = new EmptyCompleter(bc);
927 n = q;
928 }
929 DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
930 s.tryComplete();
931 }
932 }
933
934 static final class Merger extends CountedCompleter<Void> {
935 static final long serialVersionUID = 2446542900576103244L;
936 final double[] a, w; // main and workspace arrays
937 final int lbase, lsize, rbase, rsize, wbase, gran;
938 Merger(CountedCompleter<?> par, double[] a, double[] w,
939 int lbase, int lsize, int rbase,
940 int rsize, int wbase, int gran) {
941 super(par);
942 this.a = a; this.w = w;
943 this.lbase = lbase; this.lsize = lsize;
944 this.rbase = rbase; this.rsize = rsize;
945 this.wbase = wbase; this.gran = gran;
946 }
947
948 public final void compute() {
949 double[] a = this.a, w = this.w; // localize all params
950 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
951 rn = this.rsize, k = this.wbase, g = this.gran;
952 if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
953 throw new IllegalStateException(); // hoist checks
954 for (int lh, rh;;) { // split larger, find point in smaller
955 if (ln >= rn) {
956 if (ln <= g)
957 break;
958 rh = rn;
959 double split = a[(lh = ln >>> 1) + lb];
960 for (int lo = 0; lo < rh; ) {
961 int rm = (lo + rh) >>> 1;
962 if (split <= a[rm + rb])
963 rh = rm;
964 else
965 lo = rm + 1;
966 }
967 }
968 else {
969 if (rn <= g)
970 break;
971 lh = ln;
972 double split = a[(rh = rn >>> 1) + rb];
973 for (int lo = 0; lo < lh; ) {
974 int lm = (lo + lh) >>> 1;
975 if (split <= a[lm + lb])
976 lh = lm;
977 else
978 lo = lm + 1;
979 }
980 }
981 Merger m = new Merger(this, a, w, lb + lh, ln - lh,
982 rb + rh, rn - rh,
983 k + lh + rh, g);
984 rn = rh;
985 ln = lh;
986 addToPendingCount(1);
987 m.fork();
988 }
989
990 int lf = lb + ln, rf = rb + rn; // index bounds
991 while (lb < lf && rb < rf) {
992 double t, al, ar;
993 if ((al = a[lb]) <= (ar = a[rb])) {
994 lb++; t = al;
995 }
996 else {
997 rb++; t = ar;
998 }
999 w[k++] = t;
1000 }
1001 if (rb < rf)
1002 System.arraycopy(a, rb, w, k, rf - rb);
1003 else if (lb < lf)
1004 System.arraycopy(a, lb, w, k, lf - lb);
1005 tryComplete();
1006 }
1007 }
1008 } // FJDouble
1009
1010 }
|
1 /*
2 * Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util;
26
27 import java.util.concurrent.CountedCompleter;
28
29 /**
30 * Helper utilities for the parallel sort methods in Arrays.parallelSort.
31 *
32 * For each primitive type, plus Object, we define a static class to
33 * contain the Sorter and Merger implementations for that type:
34 *
35 * Sorter classes based mainly on CilkSort
36 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
37 * Basic algorithm:
38 * if array size is small, just use a sequential sort (via Arrays.sort)
39 * Otherwise:
40 * 1. Break array in half.
41 * 2. For each half,
42 * a. break the half in half (i.e., quarters),
43 * b. sort the quarters
44 * c. merge them together
45 * 3. merge together the two halves.
46 *
47 * One reason for splitting in quarters is that this guarantees that
48 * the final sort is in the main array, not the workspace array.
49 * (workspace and main swap roles on each subsort step.) Leaf-level
50 * sorts use the associated sequential sort.
51 *
52 * Merger classes perform merging for Sorter. They are structured
53 * such that if the underlying sort is stable (as is true for
54 * TimSort), then so is the full sort. If big enough, they split the
55 * largest of the two partitions in half, find the greatest point in
56 * smaller partition less than the beginning of the second half of
57 * larger via binary search; and then merge in parallel the two
58 * partitions. In part to ensure tasks are triggered in
59 * stability-preserving order, the current CountedCompleter design
60 * requires some little tasks to serve as place holders for triggering
61 * completion tasks. These classes (EmptyCompleter and Relay) don't
62 * need to keep track of the arrays, and are never themselves forked,
63 * so don't hold any task state.
64 *
65 * The base sequential sorts rely on non-public versions of TimSort,
66 * ComparableTimSort sort methods that accept temp workspace array
67 * slices that we will have already allocated, so avoids redundant
68 * allocation.
69 */
70 /*package*/ class ArraysParallelSortHelpers {
71
72 /*
73 * Style note: The task classes have a lot of parameters, that are
74 * stored as task fields and copied to local variables and used in
75 * compute() methods, We pack these into as few lines as possible,
76 * and hoist consistency checks among them before main loops, to
77 * reduce distraction.
78 */
79
80 /**
81 * A placeholder task for Sorters, used for the lowest
82 * quartile task, that does not need to maintain array state.
83 */
84 static final class EmptyCompleter extends CountedCompleter<Void> {
85 static final long serialVersionUID = 2446542900576103244L;
86 EmptyCompleter(CountedCompleter<?> p) { super(p); }
87 public final void compute() { }
88 }
113 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
114 int wbase, int gran,
115 Comparator<? super T> comparator) {
116 super(par);
117 this.a = a; this.w = w; this.base = base; this.size = size;
118 this.wbase = wbase; this.gran = gran;
119 this.comparator = comparator;
120 }
121 public final void compute() {
122 CountedCompleter<?> s = this;
123 Comparator<? super T> c = this.comparator;
124 T[] a = this.a, w = this.w; // localize all params
125 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
126 while (n > g) {
127 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
128 Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
129 wb+h, n-h, b, g, c));
130 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
131 b+u, n-u, wb+h, g, c));
132 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
133 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();
134 Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
135 b+q, h-q, wb, g, c));
136 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
137 s = new EmptyCompleter(bc);
138 n = q;
139 }
140 TimSort.sort(a, b, b + n, c, w, wb, n);
141 s.tryComplete();
142 }
143 }
144
145 static final class Merger<T> extends CountedCompleter<Void> {
146 static final long serialVersionUID = 2446542900576103244L;
147 final T[] a, w; // main and workspace arrays
148 final int lbase, lsize, rbase, rsize, wbase, gran;
149 Comparator<? super T> comparator;
150 Merger(CountedCompleter<?> par, T[] a, T[] w,
151 int lbase, int lsize, int rbase,
152 int rsize, int wbase, int gran,
153 Comparator<? super T> comparator) {
204 }
205
206 int lf = lb + ln, rf = rb + rn; // index bounds
207 while (lb < lf && rb < rf) {
208 T t, al, ar;
209 if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
210 lb++; t = al;
211 }
212 else {
213 rb++; t = ar;
214 }
215 w[k++] = t;
216 }
217 if (rb < rf)
218 System.arraycopy(a, rb, w, k, rf - rb);
219 else if (lb < lf)
220 System.arraycopy(a, lb, w, k, lf - lb);
221
222 tryComplete();
223 }
224 }
225 }
226 }
|