ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/BoxedLongSort.java

Comparing jsr166/src/test/loops/BoxedLongSort.java (file contents):
Revision 1.6 by jsr166, Mon Oct 10 16:59:04 2011 UTC vs.
Revision 1.7 by dl, Mon Apr 9 13:18:06 2012 UTC

#	Line 11 | Line 11 | 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;
#	Line 30 | Line 30 | class BoxedLongSort {
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 {
#	Line 90 | Line 108 | class BoxedLongSort {
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;
#	Line 149 | Line 169 | class BoxedLongSort {
169		*/
170		public final void compute() {
171		Merger rights = null;
172	<	int nleft = ln;
173	<	int nright = rn;
174	<	while (nleft > THRESHOLD) { //  && nright > (THRESHOLD >>> 3)) {
175	<	int lh = nleft >>> 1;
176	<	int splitIndex = lo + lh;
177	<	Long split = a[splitIndex];
172	>	Long[] a = this.a;
173	>	Long[] w = this.w;
174	>	int ln = this.ln;
175	>	int rn = this.rn;
176	>	int l = this.lo;
177	>	int r = this.ro;
178	>	int k = this.wo;
179	>	while (ln > THRESHOLD && rn > 4) {
180	>	int lh = ln >>> 1;
181	>	int lm = l + lh;
182	>	Long split = a[lm];
183	>	long ls = split.longValue();
184		int rl = 0;
185	<	int rh = nright;
185	>	int rh = rn;
186		while (rl < rh) {
187	<	int mid = (rl + rh) >>> 1;
188	<	if (split <= a[ro + mid])
189	<	rh = mid;
187	>	int rm = (rl + rh) >>> 1;
188	>	if (ls <= a[r + rm].longValue())
189	>	rh = rm;
190		else
191	<	rl = mid + 1;
191	>	rl = rm + 1;
192		}
193	<	(rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
194	<	nright-rh, wo+lh+rh, rights)).fork();
195	<	nleft = lh;
170	<	nright = rh;
193	>	(rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork();
194	>	rn = rh;
195	>	ln = lh;
196		}
197
198	<	merge(nleft, nright);
198	>	int lFence = l + ln;
199	>	int rFence = r + rn;
200	>	for (Long t;;) {
201	>	if (l < lFence) {
202	>	Long al = a[l], ar;
203	>	if (r >= rFence ||
204	>	al.longValue() <= (ar = a[r]).longValue()) {
205	>	++l; t = al;
206	>	}
207	>	else {
208	>	++r; t = ar;
209	>	}
210	>	}
211	>	else if (r < rFence)
212	>	t = a[r++];
213	>	else
214	>	break;
215	>	w[k++] = t;
216	>	}
217	>
218	>	//            merge(nleft, nright);
219		if (rights != null)
220		collectRights(rights);
221
#	Line 246 | Line 291 | class BoxedLongSort {
291		}
292
293
294	+	static final class RandomRepacker extends RecursiveAction {
295	+	final Long[] src;
296	+	final Long[] dst;
297	+	final int lo, hi, size;
298	+	RandomRepacker(Long[] src, Long[] dst,
299	+	int lo, int hi, int size) {
300	+	this.src = src; this.dst = dst;
301	+	this.lo = lo; this.hi = hi; this.size = size;
302	+	}
303	+
304	+	public final void compute() {
305	+	Long[] s = src;
306	+	Long[] d = dst;
307	+	int l = lo, h = hi, n = size;
308	+	if (h - l > THRESHOLD) {
309	+	int m = (l + h) >>> 1;
310	+	invokeAll(new RandomRepacker(s, d, l, m, n),
311	+	new RandomRepacker(s, d, m, h, n));
312	+	}
313	+	else {
314	+	ThreadLocalRandom rng = ThreadLocalRandom.current();
315	+	for (int i = l; i < h; ++i)
316	+	d[i] = s[rng.nextInt(n)];
317	+	}
318	+	}
319	+	}
320	+
321	+	static final int INSERTION_SORT_THRESHOLD = 8;
322	+
323	+	static void quickSort(Long[] a, int lo, int hi) {
324	+	for (;;) {
325	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
326	+	for (int i = lo + 1; i <= hi; i++) {
327	+	Long t = a[i];
328	+	long tv = t.longValue();
329	+	int j = i - 1;
330	+	while (j >= lo && tv < a[j].longValue()) {
331	+	a[j+1] = a[j];
332	+	--j;
333	+	}
334	+	a[j+1] = t;
335	+	}
336	+	return;
337	+	}
338	+
339	+	int mid = (lo + hi) >>> 1;
340	+	if (a[lo].longValue() > a[mid].longValue()) {
341	+	Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
342	+	}
343	+	if (a[mid].longValue() > a[hi].longValue()) {
344	+	Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
345	+	if (a[lo].longValue() > a[mid].longValue()) {
346	+	Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
347	+	}
348	+	}
349	+
350	+	long pivot = a[mid].longValue();
351	+	int left = lo+1;
352	+	int right = hi-1;
353	+	for (;;) {
354	+	while (pivot < a[right].longValue())
355	+	--right;
356	+	while (left < right && pivot >= a[left].longValue())
357	+	++left;
358	+	if (left < right) {
359	+	Long t = a[left]; a[left] = a[right]; a[right] = t;
360	+	--right;
361	+	}
362	+	else break;
363	+	}
364	+
365	+	if (left - lo <= hi - right) {
366	+	quickSort(a, lo, left);
367	+	lo = left + 1;
368	+	}
369	+	else {
370	+	quickSort(a, right, hi);
371	+	hi = left;
372	+	}
373	+	}
374	+	}
375	+
376		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines