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 }
89
90 /**
91 * A trigger for secondary merge of two merges
92 */
93 static final class Relay extends CountedCompleter<Void> {
94 static final long serialVersionUID = 2446542900576103244L;
95 final CountedCompleter<?> task;
96 Relay(CountedCompleter<?> task) {
97 super(null, 1);
98 this.task = task;
99 }
100 public final void compute() { }
101 public final void onCompletion(CountedCompleter<?> t) {
102 task.compute();
103 }
104 }
105
106 /** Object + Comparator support class */
107 static final class FJObject {
108 static final class Sorter<T> extends CountedCompleter<Void> {
109 static final long serialVersionUID = 2446542900576103244L;
110 final T[] a, w;
111 final int base, size, wbase, gran;
112 Comparator<? super T> comparator;
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) {
154 super(par);
155 this.a = a; this.w = w;
156 this.lbase = lbase; this.lsize = lsize;
157 this.rbase = rbase; this.rsize = rsize;
158 this.wbase = wbase; this.gran = gran;
159 this.comparator = comparator;
160 }
161
162 public final void compute() {
163 Comparator<? super T> c = this.comparator;
164 T[] a = this.a, w = this.w; // localize all params
165 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
166 rn = this.rsize, k = this.wbase, g = this.gran;
167 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
168 c == null)
169 throw new IllegalStateException(); // hoist checks
170 for (int lh, rh;;) { // split larger, find point in smaller
171 if (ln >= rn) {
172 if (ln <= g)
173 break;
174 rh = rn;
175 T split = a[(lh = ln >>> 1) + lb];
176 for (int lo = 0; lo < rh; ) {
177 int rm = (lo + rh) >>> 1;
178 if (c.compare(split, a[rm + rb]) <= 0)
179 rh = rm;
180 else
181 lo = rm + 1;
182 }
183 }
184 else {
185 if (rn <= g)
186 break;
187 lh = ln;
188 T split = a[(rh = rn >>> 1) + rb];
189 for (int lo = 0; lo < lh; ) {
190 int lm = (lo + lh) >>> 1;
191 if (c.compare(split, a[lm + lb]) <= 0)
192 lh = lm;
193 else
194 lo = lm + 1;
195 }
196 }
197 Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh,
198 rb + rh, rn - rh,
199 k + lh + rh, g, c);
200 rn = rh;
201 ln = lh;
202 addToPendingCount(1);
203 m.fork();
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 }