4 |
|
* http://creativecommons.org/publicdomain/zero/1.0/ |
5 |
|
*/ |
6 |
|
|
7 |
– |
import java.util.concurrent.*; |
7 |
|
import java.util.*; |
8 |
+ |
import java.util.concurrent.*; |
9 |
|
|
10 |
|
class BoxedLongSort { |
11 |
|
static final long NPS = (1000L * 1000 * 1000); |
12 |
|
|
13 |
|
static int THRESHOLD; |
14 |
< |
static final boolean warmup = true; |
14 |
> |
// static final int THRESHOLD = 64; |
15 |
|
|
16 |
|
public static void main(String[] args) throws Exception { |
17 |
|
int procs = 0; |
30 |
|
System.out.println("Usage: java BoxedLongSort threads n reps"); |
31 |
|
return; |
32 |
|
} |
33 |
< |
ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() : |
34 |
< |
new ForkJoinPool(procs); |
33 |
> |
if (procs == 0) |
34 |
> |
procs = Runtime.getRuntime().availableProcessors(); |
35 |
|
|
36 |
+ |
THRESHOLD = ((n + 7) >>> 3) / procs; |
37 |
+ |
// THRESHOLD = ((n + 15) >>> 4) / procs; |
38 |
+ |
// THRESHOLD = ((n + 31) >>> 5) / procs; |
39 |
+ |
if (THRESHOLD < 64) |
40 |
+ |
THRESHOLD = 64; |
41 |
+ |
|
42 |
+ |
System.out.println("Threshold = " + THRESHOLD); |
43 |
+ |
|
44 |
+ |
Long[] numbers = new Long[n]; |
45 |
+ |
for (int i = 0; i < n; ++i) |
46 |
+ |
numbers[i] = Long.valueOf(i); |
47 |
|
Long[] a = new Long[n]; |
48 |
< |
seqRandomFill(a, 0, n); |
49 |
< |
|
50 |
< |
if (warmup) { |
51 |
< |
System.out.printf("Sorting %d longs, %d replications\n", n, 1); |
52 |
< |
Collections.shuffle(Arrays.asList(a)); |
53 |
< |
long last = System.nanoTime(); |
54 |
< |
java.util.Arrays.sort(a); |
55 |
< |
double elapsed = (double)(System.nanoTime() - last) / NPS; |
56 |
< |
System.out.printf("Arrays.sort time: %7.3f\n", elapsed); |
46 |
< |
checkSorted(a); |
47 |
< |
} |
48 |
< |
|
49 |
< |
// for now hardwire 8 * #CPUs leaf tasks |
50 |
< |
THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism(); |
51 |
< |
// THRESHOLD = 1 + ((n + 15) >>> 4) / pool.getParallelism(); |
52 |
< |
// THRESHOLD = 1 + ((n + 31) >>> 5) / pool.getParallelism(); |
48 |
> |
ForkJoinPool pool = new ForkJoinPool(procs); |
49 |
> |
seqTest(a, numbers, pool, 1); |
50 |
> |
System.out.println(pool); |
51 |
> |
parTest(a, numbers, pool, reps); |
52 |
> |
System.out.println(pool); |
53 |
> |
seqTest(a, numbers, pool, 2); |
54 |
> |
System.out.println(pool); |
55 |
> |
pool.shutdown(); |
56 |
> |
} |
57 |
|
|
58 |
+ |
static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) { |
59 |
+ |
int n = numbers.length; |
60 |
|
System.out.printf("Sorting %d longs, %d replications\n", n, reps); |
61 |
+ |
long start = System.nanoTime(); |
62 |
|
for (int i = 0; i < reps; ++i) { |
63 |
< |
Collections.shuffle(Arrays.asList(a)); |
64 |
< |
// pool.invoke(new RandomFiller(a, 0, n)); |
63 |
> |
pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); |
64 |
> |
// pool.invoke(new TaskChecker()); |
65 |
|
long last = System.nanoTime(); |
66 |
< |
pool.invoke(new Sorter(a, new Long[n], 0, n)); |
67 |
< |
double elapsed = (double)(System.nanoTime() - last) / NPS; |
68 |
< |
System.out.printf("Parallel sort time: %7.3f\n", elapsed); |
66 |
> |
// quickSort(a, 0, n-1); |
67 |
> |
java.util.Arrays.sort(a); |
68 |
> |
long now = System.nanoTime(); |
69 |
> |
double total = (double)(now - start) / NPS; |
70 |
> |
double elapsed = (double)(now - last) / NPS; |
71 |
> |
System.out.printf("Arrays.sort time: %7.3f total %9.3f\n", |
72 |
> |
elapsed, total); |
73 |
|
if (i == 0) |
74 |
|
checkSorted(a); |
75 |
|
} |
76 |
< |
System.out.println(pool); |
76 |
> |
} |
77 |
|
|
78 |
< |
System.out.printf("Sorting %d longs, %d replications\n", n, sreps); |
79 |
< |
for (int i = 0; i < sreps; ++i) { |
80 |
< |
Collections.shuffle(Arrays.asList(a)); |
81 |
< |
// pool.invoke(new RandomFiller(a, 0, n)); |
78 |
> |
static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) { |
79 |
> |
int n = numbers.length; |
80 |
> |
Long[] w = new Long[n]; |
81 |
> |
System.out.printf("Sorting %d longs, %d replications\n", n, reps); |
82 |
> |
long start = System.nanoTime(); |
83 |
> |
for (int i = 0; i < reps; ++i) { |
84 |
> |
// Arrays.fill(w, 0, n, null); |
85 |
> |
pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); |
86 |
> |
// pool.invoke(new TaskChecker()); |
87 |
|
long last = System.nanoTime(); |
88 |
< |
java.util.Arrays.sort(a); |
89 |
< |
double elapsed = (double)(System.nanoTime() - last) / NPS; |
90 |
< |
System.out.printf("Arrays.sort time: %7.3f\n", elapsed); |
88 |
> |
pool.invoke(new Sorter(a, w, 0, n)); |
89 |
> |
long now = System.nanoTime(); |
90 |
> |
// pool.invoke(new TaskChecker()); |
91 |
> |
double total = (double)(now - start) / NPS; |
92 |
> |
double elapsed = (double)(now - last) / NPS; |
93 |
> |
System.out.printf("Parallel sort time: %7.3f total %9.3f\n", |
94 |
> |
elapsed, total); |
95 |
|
if (i == 0) |
96 |
|
checkSorted(a); |
97 |
|
} |
78 |
– |
System.out.println(pool); |
79 |
– |
pool.shutdown(); |
98 |
|
} |
99 |
|
|
100 |
|
static final class Sorter extends RecursiveAction { |
108 |
|
|
109 |
|
public void compute() { |
110 |
|
int l = origin; |
111 |
< |
if (n <= THRESHOLD) |
112 |
< |
Arrays.sort(a, l, l+n); |
111 |
> |
if (n <= THRESHOLD) { |
112 |
> |
// Arrays.sort(a, l, l+n); |
113 |
> |
quickSort(a, l, l+n-1); |
114 |
> |
} |
115 |
|
else { // divide in quarters to ensure sorted array in a not w |
116 |
|
int h = n >>> 1; |
117 |
|
int q = n >>> 2; |
165 |
|
* and finding index of right closest to split point. |
166 |
|
* Uses left-spine decomposition to generate all |
167 |
|
* merge tasks before bottomming out at base case. |
148 |
– |
* |
168 |
|
*/ |
169 |
|
public final void compute() { |
170 |
|
Merger rights = null; |
171 |
< |
int nleft = ln; |
172 |
< |
int nright = rn; |
173 |
< |
while (nleft > THRESHOLD) { // && nright > (THRESHOLD >>> 3)) { |
174 |
< |
int lh = nleft >>> 1; |
175 |
< |
int splitIndex = lo + lh; |
176 |
< |
Long split = a[splitIndex]; |
171 |
> |
Long[] a = this.a; |
172 |
> |
Long[] w = this.w; |
173 |
> |
int ln = this.ln; |
174 |
> |
int rn = this.rn; |
175 |
> |
int l = this.lo; |
176 |
> |
int r = this.ro; |
177 |
> |
int k = this.wo; |
178 |
> |
while (ln > THRESHOLD && rn > 4) { |
179 |
> |
int lh = ln >>> 1; |
180 |
> |
int lm = l + lh; |
181 |
> |
Long split = a[lm]; |
182 |
> |
long ls = split.longValue(); |
183 |
|
int rl = 0; |
184 |
< |
int rh = nright; |
184 |
> |
int rh = rn; |
185 |
|
while (rl < rh) { |
186 |
< |
int mid = (rl + rh) >>> 1; |
187 |
< |
if (split <= a[ro + mid]) |
188 |
< |
rh = mid; |
186 |
> |
int rm = (rl + rh) >>> 1; |
187 |
> |
if (ls <= a[r + rm].longValue()) |
188 |
> |
rh = rm; |
189 |
|
else |
190 |
< |
rl = mid + 1; |
190 |
> |
rl = rm + 1; |
191 |
> |
} |
192 |
> |
(rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork(); |
193 |
> |
rn = rh; |
194 |
> |
ln = lh; |
195 |
> |
} |
196 |
> |
|
197 |
> |
int lFence = l + ln; |
198 |
> |
int rFence = r + rn; |
199 |
> |
for (Long t;;) { |
200 |
> |
if (l < lFence) { |
201 |
> |
Long al = a[l], ar; |
202 |
> |
if (r >= rFence || |
203 |
> |
al.longValue() <= (ar = a[r]).longValue()) { |
204 |
> |
++l; t = al; |
205 |
> |
} |
206 |
> |
else { |
207 |
> |
++r; t = ar; |
208 |
> |
} |
209 |
|
} |
210 |
< |
(rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, |
211 |
< |
nright-rh, wo+lh+rh, rights)).fork(); |
212 |
< |
nleft = lh; |
213 |
< |
nright = rh; |
210 |
> |
else if (r < rFence) |
211 |
> |
t = a[r++]; |
212 |
> |
else |
213 |
> |
break; |
214 |
> |
w[k++] = t; |
215 |
|
} |
216 |
|
|
217 |
< |
merge(nleft, nright); |
217 |
> |
// merge(nleft, nright); |
218 |
|
if (rights != null) |
219 |
|
collectRights(rights); |
176 |
– |
|
220 |
|
} |
221 |
|
|
222 |
|
final void merge(int nleft, int nright) { |
288 |
|
} |
289 |
|
} |
290 |
|
|
291 |
+ |
static final class RandomRepacker extends RecursiveAction { |
292 |
+ |
final Long[] src; |
293 |
+ |
final Long[] dst; |
294 |
+ |
final int lo, hi, size; |
295 |
+ |
RandomRepacker(Long[] src, Long[] dst, |
296 |
+ |
int lo, int hi, int size) { |
297 |
+ |
this.src = src; this.dst = dst; |
298 |
+ |
this.lo = lo; this.hi = hi; this.size = size; |
299 |
+ |
} |
300 |
+ |
|
301 |
+ |
public final void compute() { |
302 |
+ |
Long[] s = src; |
303 |
+ |
Long[] d = dst; |
304 |
+ |
int l = lo, h = hi, n = size; |
305 |
+ |
if (h - l > THRESHOLD) { |
306 |
+ |
int m = (l + h) >>> 1; |
307 |
+ |
invokeAll(new RandomRepacker(s, d, l, m, n), |
308 |
+ |
new RandomRepacker(s, d, m, h, n)); |
309 |
+ |
} |
310 |
+ |
else { |
311 |
+ |
ThreadLocalRandom rng = ThreadLocalRandom.current(); |
312 |
+ |
for (int i = l; i < h; ++i) |
313 |
+ |
d[i] = s[rng.nextInt(n)]; |
314 |
+ |
} |
315 |
+ |
} |
316 |
+ |
} |
317 |
+ |
|
318 |
+ |
static final int INSERTION_SORT_THRESHOLD = 8; |
319 |
+ |
|
320 |
+ |
static void quickSort(Long[] a, int lo, int hi) { |
321 |
+ |
for (;;) { |
322 |
+ |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
323 |
+ |
for (int i = lo + 1; i <= hi; i++) { |
324 |
+ |
Long t = a[i]; |
325 |
+ |
long tv = t.longValue(); |
326 |
+ |
int j = i - 1; |
327 |
+ |
while (j >= lo && tv < a[j].longValue()) { |
328 |
+ |
a[j+1] = a[j]; |
329 |
+ |
--j; |
330 |
+ |
} |
331 |
+ |
a[j+1] = t; |
332 |
+ |
} |
333 |
+ |
return; |
334 |
+ |
} |
335 |
+ |
|
336 |
+ |
int mid = (lo + hi) >>> 1; |
337 |
+ |
if (a[lo].longValue() > a[mid].longValue()) { |
338 |
+ |
Long t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
339 |
+ |
} |
340 |
+ |
if (a[mid].longValue() > a[hi].longValue()) { |
341 |
+ |
Long t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
342 |
+ |
if (a[lo].longValue() > a[mid].longValue()) { |
343 |
+ |
Long u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
344 |
+ |
} |
345 |
+ |
} |
346 |
+ |
|
347 |
+ |
long pivot = a[mid].longValue(); |
348 |
+ |
int left = lo+1; |
349 |
+ |
int right = hi-1; |
350 |
+ |
for (;;) { |
351 |
+ |
while (pivot < a[right].longValue()) |
352 |
+ |
--right; |
353 |
+ |
while (left < right && pivot >= a[left].longValue()) |
354 |
+ |
++left; |
355 |
+ |
if (left < right) { |
356 |
+ |
Long t = a[left]; a[left] = a[right]; a[right] = t; |
357 |
+ |
--right; |
358 |
+ |
} |
359 |
+ |
else break; |
360 |
+ |
} |
361 |
+ |
|
362 |
+ |
if (left - lo <= hi - right) { |
363 |
+ |
quickSort(a, lo, left); |
364 |
+ |
lo = left + 1; |
365 |
+ |
} |
366 |
+ |
else { |
367 |
+ |
quickSort(a, right, hi); |
368 |
+ |
hi = left; |
369 |
+ |
} |
370 |
+ |
} |
371 |
+ |
} |
372 |
|
|
373 |
|
} |