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); |
16 |
|
public static void main(String[] args) throws Exception { |
17 |
|
int procs = 0; |
18 |
|
int n = 1 << 22; |
19 |
< |
int reps = 20; |
19 |
> |
int reps = 30; |
20 |
|
int sreps = 2; |
21 |
|
try { |
22 |
|
if (args.length > 0) |
45 |
|
for (int i = 0; i < n; ++i) |
46 |
|
numbers[i] = Long.valueOf(i); |
47 |
|
Long[] a = new Long[n]; |
48 |
< |
ForkJoinPool pool = new ForkJoinPool(procs); |
48 |
> |
// ForkJoinPool pool = new ForkJoinPool(procs); |
49 |
> |
ForkJoinPool pool = ForkJoinPool.commonPool(); |
50 |
|
seqTest(a, numbers, pool, 1); |
51 |
|
System.out.println(pool); |
52 |
|
parTest(a, numbers, pool, reps); |
61 |
|
System.out.printf("Sorting %d longs, %d replications\n", n, reps); |
62 |
|
long start = System.nanoTime(); |
63 |
|
for (int i = 0; i < reps; ++i) { |
64 |
< |
pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); |
64 |
> |
new RandomRepacker(numbers, a, 0, n, n).invoke(); |
65 |
|
// pool.invoke(new TaskChecker()); |
66 |
|
long last = System.nanoTime(); |
67 |
|
// quickSort(a, 0, n-1); |
69 |
|
long now = System.nanoTime(); |
70 |
|
double total = (double)(now - start) / NPS; |
71 |
|
double elapsed = (double)(now - last) / NPS; |
72 |
< |
System.out.printf("Arrays.sort time: %7.3f total %9.3f\n", |
72 |
> |
System.out.printf("Arrays.sort time: %7.3f total %9.3f\n", |
73 |
|
elapsed, total); |
74 |
|
if (i == 0) |
75 |
|
checkSorted(a); |
76 |
|
} |
77 |
|
} |
78 |
|
|
79 |
< |
static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) { |
79 |
> |
static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) throws Exception { |
80 |
|
int n = numbers.length; |
81 |
|
Long[] w = new Long[n]; |
82 |
|
System.out.printf("Sorting %d longs, %d replications\n", n, reps); |
83 |
|
long start = System.nanoTime(); |
84 |
|
for (int i = 0; i < reps; ++i) { |
85 |
|
// Arrays.fill(w, 0, n, null); |
86 |
< |
pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); |
86 |
> |
new RandomRepacker(numbers, a, 0, n, n).invoke(); |
87 |
> |
// Thread.sleep(500); |
88 |
|
// pool.invoke(new TaskChecker()); |
89 |
|
long last = System.nanoTime(); |
90 |
< |
pool.invoke(new Sorter(a, w, 0, n)); |
90 |
> |
new Sorter(a, w, 0, n).invoke(); |
91 |
|
long now = System.nanoTime(); |
92 |
|
// pool.invoke(new TaskChecker()); |
93 |
|
double total = (double)(now - start) / NPS; |
94 |
|
double elapsed = (double)(now - last) / NPS; |
95 |
< |
System.out.printf("Parallel sort time: %7.3f total %9.3f\n", |
95 |
> |
System.out.printf("Parallel sort time: %7.3f total %9.3f\n", |
96 |
|
elapsed, total); |
97 |
|
if (i == 0) |
98 |
|
checkSorted(a); |
167 |
|
* and finding index of right closest to split point. |
168 |
|
* Uses left-spine decomposition to generate all |
169 |
|
* merge tasks before bottomming out at base case. |
168 |
– |
* |
170 |
|
*/ |
171 |
|
public final void compute() { |
172 |
|
Merger rights = null; |
203 |
|
Long al = a[l], ar; |
204 |
|
if (r >= rFence || |
205 |
|
al.longValue() <= (ar = a[r]).longValue()) { |
206 |
< |
++l; t = al; |
207 |
< |
} |
208 |
< |
else { |
209 |
< |
++r; t = ar; |
206 |
> |
++l; t = al; |
207 |
> |
} |
208 |
> |
else { |
209 |
> |
++r; t = ar; |
210 |
|
} |
211 |
|
} |
212 |
|
else if (r < rFence) |
213 |
|
t = a[r++]; |
214 |
< |
else |
214 |
> |
else |
215 |
|
break; |
216 |
|
w[k++] = t; |
217 |
|
} |
219 |
|
// merge(nleft, nright); |
220 |
|
if (rights != null) |
221 |
|
collectRights(rights); |
221 |
– |
|
222 |
|
} |
223 |
|
|
224 |
|
final void merge(int nleft, int nright) { |
290 |
|
} |
291 |
|
} |
292 |
|
|
293 |
– |
|
293 |
|
static final class RandomRepacker extends RecursiveAction { |
294 |
|
final Long[] src; |
295 |
|
final Long[] dst; |
296 |
|
final int lo, hi, size; |
297 |
< |
RandomRepacker(Long[] src, Long[] dst, |
297 |
> |
RandomRepacker(Long[] src, Long[] dst, |
298 |
|
int lo, int hi, int size) { |
299 |
|
this.src = src; this.dst = dst; |
300 |
|
this.lo = lo; this.hi = hi; this.size = size; |
301 |
|
} |
302 |
< |
|
302 |
> |
|
303 |
|
public final void compute() { |
304 |
|
Long[] s = src; |
305 |
|
Long[] d = dst; |