ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/loops/BoxedLongSort.java
Revision: 1.13
Committed: Sat Sep 12 18:12:20 2015 UTC (8 years, 6 months ago) by dl
Branch: MAIN
CVS Tags: HEAD
Changes since 1.12: +8 -6 lines
Log Message:
Use commonPool

File Contents

# Content
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/publicdomain/zero/1.0/
5 */
6
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 int THRESHOLD = 64;
15
16 public static void main(String[] args) throws Exception {
17 int procs = 0;
18 int n = 1 << 22;
19 int reps = 30;
20 int sreps = 2;
21 try {
22 if (args.length > 0)
23 procs = Integer.parseInt(args[0]);
24 if (args.length > 1)
25 n = Integer.parseInt(args[1]);
26 if (args.length > 2)
27 reps = Integer.parseInt(args[1]);
28 }
29 catch (Exception e) {
30 System.out.println("Usage: java BoxedLongSort threads n reps");
31 return;
32 }
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 // 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);
53 System.out.println(pool);
54 seqTest(a, numbers, pool, 2);
55 System.out.println(pool);
56 pool.shutdown();
57 }
58
59 static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
60 int n = numbers.length;
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 new RandomRepacker(numbers, a, 0, n, n).invoke();
65 // pool.invoke(new TaskChecker());
66 long last = System.nanoTime();
67 // quickSort(a, 0, n-1);
68 java.util.Arrays.sort(a);
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",
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) 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 new RandomRepacker(numbers, a, 0, n, n).invoke();
87 // Thread.sleep(500);
88 // pool.invoke(new TaskChecker());
89 long last = System.nanoTime();
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",
96 elapsed, total);
97 if (i == 0)
98 checkSorted(a);
99 }
100 }
101
102 static final class Sorter extends RecursiveAction {
103 final Long[] a;
104 final Long[] w;
105 final int origin;
106 final int n;
107 Sorter(Long[] a, Long[] w, int origin, int n) {
108 this.a = a; this.w = w; this.origin = origin; this.n = n;
109 }
110
111 public void compute() {
112 int l = origin;
113 if (n <= THRESHOLD) {
114 // Arrays.sort(a, l, l+n);
115 quickSort(a, l, l+n-1);
116 }
117 else { // divide in quarters to ensure sorted array in a not w
118 int h = n >>> 1;
119 int q = n >>> 2;
120 int u = h + q;
121 SubSorter rs = new SubSorter
122 (new Sorter(a, w, l+h, q),
123 new Sorter(a, w, l+u, n-u),
124 new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
125 rs.fork();
126 Sorter rl = new Sorter(a, w, l+q, h-q);
127 rl.fork();
128 (new Sorter(a, w, l, q)).compute();
129 rl.join();
130 (new Merger(a, w, l, q, l+q, h-q, l, null)).compute();
131 rs.join();
132 new Merger(w, a, l, h, l+h, n-h, l, null).compute();
133 }
134 }
135 }
136
137 static final class SubSorter extends RecursiveAction {
138 final Sorter left;
139 final Sorter right;
140 final Merger merger;
141 SubSorter(Sorter left, Sorter right, Merger merger) {
142 this.left = left; this.right = right; this.merger = merger;
143 }
144 public void compute() {
145 right.fork();
146 left.compute();
147 right.join();
148 merger.compute();
149 }
150 }
151
152 static final class Merger extends RecursiveAction {
153 final Long[] a; final Long[] w;
154 final int lo; final int ln; final int ro; final int rn; final int wo;
155 Merger next;
156 Merger(Long[] a, Long[] w, int lo, int ln, int ro, int rn, int wo,
157 Merger next) {
158 this.a = a; this.w = w;
159 this.lo = lo; this.ln = ln;
160 this.ro = ro; this.rn = rn;
161 this.wo = wo;
162 this.next = next;
163 }
164
165 /**
166 * Merge left and right by splitting left in half,
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.
170 */
171 public final void compute() {
172 Merger rights = null;
173 Long[] a = this.a;
174 Long[] w = this.w;
175 int ln = this.ln;
176 int rn = this.rn;
177 int l = this.lo;
178 int r = this.ro;
179 int k = this.wo;
180 while (ln > THRESHOLD && rn > 4) {
181 int lh = ln >>> 1;
182 int lm = l + lh;
183 Long split = a[lm];
184 long ls = split.longValue();
185 int rl = 0;
186 int rh = rn;
187 while (rl < rh) {
188 int rm = (rl + rh) >>> 1;
189 if (ls <= a[r + rm].longValue())
190 rh = rm;
191 else
192 rl = rm + 1;
193 }
194 (rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork();
195 rn = rh;
196 ln = lh;
197 }
198
199 int lFence = l + ln;
200 int rFence = r + rn;
201 for (Long t;;) {
202 if (l < lFence) {
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;
210 }
211 }
212 else if (r < rFence)
213 t = a[r++];
214 else
215 break;
216 w[k++] = t;
217 }
218
219 // merge(nleft, nright);
220 if (rights != null)
221 collectRights(rights);
222 }
223
224 final void merge(int nleft, int nright) {
225 int l = lo;
226 int lFence = lo + nleft;
227 int r = ro;
228 int rFence = ro + nright;
229 int k = wo;
230 while (l < lFence && r < rFence) {
231 Long al = a[l];
232 Long ar = a[r];
233 Long t;
234 if (al <= ar) { ++l; t = al; } else { ++r; t = ar; }
235 w[k++] = t;
236 }
237 while (l < lFence)
238 w[k++] = a[l++];
239 while (r < rFence)
240 w[k++] = a[r++];
241 }
242
243 static void collectRights(Merger rt) {
244 while (rt != null) {
245 Merger next = rt.next;
246 rt.next = null;
247 if (rt.tryUnfork()) rt.compute(); else rt.join();
248 rt = next;
249 }
250 }
251
252 }
253
254 static void checkSorted(Long[] a) {
255 int n = a.length;
256 for (int i = 0; i < n - 1; i++) {
257 if (a[i] > a[i+1]) {
258 throw new Error("Unsorted at " + i + ": " +
259 a[i] + " / " + a[i+1]);
260 }
261 }
262 }
263
264 static void seqRandomFill(Long[] array, int lo, int hi) {
265 ThreadLocalRandom rng = ThreadLocalRandom.current();
266 for (int i = lo; i < hi; ++i)
267 array[i] = rng.nextLong();
268 }
269
270 static final class RandomFiller extends RecursiveAction {
271 final Long[] array;
272 final int lo, hi;
273 RandomFiller(Long[] array, int lo, int hi) {
274 this.array = array; this.lo = lo; this.hi = hi;
275 }
276 public void compute() {
277 if (hi - lo <= THRESHOLD) {
278 Long[] a = array;
279 ThreadLocalRandom rng = ThreadLocalRandom.current();
280 for (int i = lo; i < hi; ++i)
281 a[i] = rng.nextLong();
282 }
283 else {
284 int mid = (lo + hi) >>> 1;
285 RandomFiller r = new RandomFiller(array, mid, hi);
286 r.fork();
287 (new RandomFiller(array, lo, mid)).compute();
288 r.join();
289 }
290 }
291 }
292
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,
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
303 public final void compute() {
304 Long[] s = src;
305 Long[] d = dst;
306 int l = lo, h = hi, n = size;
307 if (h - l > THRESHOLD) {
308 int m = (l + h) >>> 1;
309 invokeAll(new RandomRepacker(s, d, l, m, n),
310 new RandomRepacker(s, d, m, h, n));
311 }
312 else {
313 ThreadLocalRandom rng = ThreadLocalRandom.current();
314 for (int i = l; i < h; ++i)
315 d[i] = s[rng.nextInt(n)];
316 }
317 }
318 }
319
320 static final int INSERTION_SORT_THRESHOLD = 8;
321
322 static void quickSort(Long[] a, int lo, int hi) {
323 for (;;) {
324 if (hi - lo <= INSERTION_SORT_THRESHOLD) {
325 for (int i = lo + 1; i <= hi; i++) {
326 Long t = a[i];
327 long tv = t.longValue();
328 int j = i - 1;
329 while (j >= lo && tv < a[j].longValue()) {
330 a[j+1] = a[j];
331 --j;
332 }
333 a[j+1] = t;
334 }
335 return;
336 }
337
338 int mid = (lo + hi) >>> 1;
339 if (a[lo].longValue() > a[mid].longValue()) {
340 Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
341 }
342 if (a[mid].longValue() > a[hi].longValue()) {
343 Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
344 if (a[lo].longValue() > a[mid].longValue()) {
345 Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
346 }
347 }
348
349 long pivot = a[mid].longValue();
350 int left = lo+1;
351 int right = hi-1;
352 for (;;) {
353 while (pivot < a[right].longValue())
354 --right;
355 while (left < right && pivot >= a[left].longValue())
356 ++left;
357 if (left < right) {
358 Long t = a[left]; a[left] = a[right]; a[right] = t;
359 --right;
360 }
361 else break;
362 }
363
364 if (left - lo <= hi - right) {
365 quickSort(a, lo, left);
366 lo = left + 1;
367 }
368 else {
369 quickSort(a, right, hi);
370 hi = left;
371 }
372 }
373 }
374
375 }