test/loops/ArraysSort.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.concurrent.*;
import java.util.*;

class ArraysSort {
    static final long NPS = (1000L * 1000 * 1000);
    static int THRESHOLD;
    static Long[] numbers;

    static final Comparator<Object> cmp = (Object x, Object y) ->
        ((Long)x).compareTo((Long)y);

    public static void main(String[] args) throws Exception {
        int n = 1 << 22;
        int reps = 30;
        int sreps = 2;
        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                reps = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java ArraysSort n reps");
            return;
        }

        numbers = new Long[n];
        for (int i = 0; i < n; ++i)
            numbers[i] = Long.valueOf(i);

        int thr = ((n + 7) >>> 3) / ForkJoinPool.getCommonPoolParallelism();
        THRESHOLD = (thr <= 1 << 13) ? 1 << 13 : thr;

        System.out.println("Threshold = " + THRESHOLD);

        Long[] a = new Long[n];
        ForkJoinPool pool = ForkJoinPool.commonPool();
        seqTest(a, n, 1);
        System.out.println(pool);
        parTest(a, n, reps);
        System.out.println(pool);
        seqTest(a, n, 2);
        System.out.println(pool);
        cseqTest(a, n, 1);
        System.out.println(pool);
        cparTest(a, n, reps);
        System.out.println(pool);
        cseqTest(a, n, 2);
        System.out.println(pool);
    }

    static void seqTest(Long[] a, int n, int reps) {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            java.util.Arrays.sort(a);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Arrays.sort   time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }

    static void cseqTest(Long[] a, int n, int reps) {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            java.util.Arrays.sort(a, cmp);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Arrays.cmp sort time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }

    static void parTest(Long[] a, int n, int reps) throws Exception {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            java.util.Arrays.parallelSort(a);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Parallel sort time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }

    static void cparTest(Long[] a, int n, int reps) throws Exception {
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            new RandomRepacker(null, numbers, a, 0, n, n).invoke();
            long last = System.nanoTime();
            java.util.Arrays.parallelSort(a, cmp);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("Par cmp  sort time:  %7.3f total %9.3f\n",
                              elapsed, total);
            new OrderChecker(null, a, 0, n, n).invoke();
        }
    }

    static void checkSorted(Long[] a) {
        int n = a.length;
        long x = a[0].longValue(), y;
        for (int i = 0; i < n - 1; i++) {
            if (x > (y = a[i+1].longValue()))
                throw new Error("Unsorted at " + i + ": " + x + " / " + y);
            x = y;
        }
    }

    static final class RandomRepacker extends CountedCompleter<Void> {
        final Long[] src;
        final Long[] dst;
        final int lo, hi, size;
        RandomRepacker(CountedCompleter<?> par, Long[] src, Long[] dst,
                       int lo, int hi, int size) {
            super(par);
            this.src = src; this.dst = dst;
            this.lo = lo; this.hi = hi; this.size = size;
        }

        public final void compute() {
            Long[] s = src;
            Long[] d = dst;
            int l = lo, h = hi, n = size;
            while (h - l > THRESHOLD << 1) {
                int m = (l + h) >>> 1;
                addToPendingCount(1);
                new RandomRepacker(this, s, d, m, h, n).fork();
                h = m;
            }
            ThreadLocalRandom rng = ThreadLocalRandom.current();
            Long dl = d[l];
            int m = (dl == null) ? h : rng.nextInt(l, h);
            for (int i = l; i < m; ++i)
                d[i] = s[rng.nextInt(n)];
            if (dl != null) {
                dl = d[l];
                for (int i = m; i < h; ++i)
                    d[i] = dl;
            }
            tryComplete();
        }
    }

    static final class OrderChecker extends CountedCompleter<Void> {
        final Long[] array;
        final int lo, hi, size;
        OrderChecker(CountedCompleter<?> par, Long[] a, int lo, int hi, int size) {
            super(par);
            this.array = a;
            this.lo = lo; this.hi = hi; this.size = size;
        }

        public final void compute() {
            Long[] a = this.array;
            int l = lo, h = hi, n = size;
            while (h - l > THRESHOLD) {
                int m = (l + h) >>> 1;
                addToPendingCount(1);
                new OrderChecker(this, a, m, h, n).fork();
                h = m;
            }
            int bound = h < n ? h : n - 1;
            int i = l;
            long x = a[i].longValue(), y;
            while (i < bound) {
                if (x > (y = a[++i].longValue()))
                    throw new Error("Unsorted " + x + " / " + y);
                x = y;
            }
            tryComplete();
        }
    }

}
Revision:	1.4
Committed:	Sat Sep 12 19:09:00 2015 UTC (8 years, 7 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.3:	+0 -1 lines
Log Message:	style nits
#	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.concurrent.*;
8	import java.util.*;
9
10	class ArraysSort {
11	static final long NPS = (1000L * 1000 * 1000);
12	static int THRESHOLD;
13	static Long[] numbers;
14
15	static final Comparator<Object> cmp = (Object x, Object y) ->
16	((Long)x).compareTo((Long)y);
17
18	public static void main(String[] args) throws Exception {
19	int n = 1 << 22;
20	int reps = 30;
21	int sreps = 2;
22	try {
23	if (args.length > 0)
24	n = Integer.parseInt(args[0]);
25	if (args.length > 1)
26	reps = Integer.parseInt(args[1]);
27	}
28	catch (Exception e) {
29	System.out.println("Usage: java ArraysSort n reps");
30	return;
31	}
32
33	numbers = new Long[n];
34	for (int i = 0; i < n; ++i)
35	numbers[i] = Long.valueOf(i);
36
37	int thr = ((n + 7) >>> 3) / ForkJoinPool.getCommonPoolParallelism();
38	THRESHOLD = (thr <= 1 << 13) ? 1 << 13 : thr;
39
40	System.out.println("Threshold = " + THRESHOLD);
41
42	Long[] a = new Long[n];
43	ForkJoinPool pool = ForkJoinPool.commonPool();
44	seqTest(a, n, 1);
45	System.out.println(pool);
46	parTest(a, n, reps);
47	System.out.println(pool);
48	seqTest(a, n, 2);
49	System.out.println(pool);
50	cseqTest(a, n, 1);
51	System.out.println(pool);
52	cparTest(a, n, reps);
53	System.out.println(pool);
54	cseqTest(a, n, 2);
55	System.out.println(pool);
56	}
57
58	static void seqTest(Long[] a, int n, int reps) {
59	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
60	long start = System.nanoTime();
61	for (int i = 0; i < reps; ++i) {
62	new RandomRepacker(null, numbers, a, 0, n, n).invoke();
63	long last = System.nanoTime();
64	java.util.Arrays.sort(a);
65	long now = System.nanoTime();
66	double total = (double)(now - start) / NPS;
67	double elapsed = (double)(now - last) / NPS;
68	System.out.printf("Arrays.sort time: %7.3f total %9.3f\n",
69	elapsed, total);
70	new OrderChecker(null, a, 0, n, n).invoke();
71	}
72	}
73
74	static void cseqTest(Long[] a, int n, int reps) {
75	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
76	long start = System.nanoTime();
77	for (int i = 0; i < reps; ++i) {
78	new RandomRepacker(null, numbers, a, 0, n, n).invoke();
79	long last = System.nanoTime();
80	java.util.Arrays.sort(a, cmp);
81	long now = System.nanoTime();
82	double total = (double)(now - start) / NPS;
83	double elapsed = (double)(now - last) / NPS;
84	System.out.printf("Arrays.cmp sort time: %7.3f total %9.3f\n",
85	elapsed, total);
86	new OrderChecker(null, a, 0, n, n).invoke();
87	}
88	}
89
90	static void parTest(Long[] a, int n, int reps) throws Exception {
91	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
92	long start = System.nanoTime();
93	for (int i = 0; i < reps; ++i) {
94	new RandomRepacker(null, numbers, a, 0, n, n).invoke();
95	long last = System.nanoTime();
96	java.util.Arrays.parallelSort(a);
97	long now = System.nanoTime();
98	double total = (double)(now - start) / NPS;
99	double elapsed = (double)(now - last) / NPS;
100	System.out.printf("Parallel sort time: %7.3f total %9.3f\n",
101	elapsed, total);
102	new OrderChecker(null, a, 0, n, n).invoke();
103	}
104	}
105
106	static void cparTest(Long[] a, int n, int reps) throws Exception {
107	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
108	long start = System.nanoTime();
109	for (int i = 0; i < reps; ++i) {
110	new RandomRepacker(null, numbers, a, 0, n, n).invoke();
111	long last = System.nanoTime();
112	java.util.Arrays.parallelSort(a, cmp);
113	long now = System.nanoTime();
114	double total = (double)(now - start) / NPS;
115	double elapsed = (double)(now - last) / NPS;
116	System.out.printf("Par cmp sort time: %7.3f total %9.3f\n",
117	elapsed, total);
118	new OrderChecker(null, a, 0, n, n).invoke();
119	}
120	}
121
122	static void checkSorted(Long[] a) {
123	int n = a.length;
124	long x = a[0].longValue(), y;
125	for (int i = 0; i < n - 1; i++) {
126	if (x > (y = a[i+1].longValue()))
127	throw new Error("Unsorted at " + i + ": " + x + " / " + y);
128	x = y;
129	}
130	}
131
132	static final class RandomRepacker extends CountedCompleter<Void> {
133	final Long[] src;
134	final Long[] dst;
135	final int lo, hi, size;
136	RandomRepacker(CountedCompleter<?> par, Long[] src, Long[] dst,
137	int lo, int hi, int size) {
138	super(par);
139	this.src = src; this.dst = dst;
140	this.lo = lo; this.hi = hi; this.size = size;
141	}
142
143	public final void compute() {
144	Long[] s = src;
145	Long[] d = dst;
146	int l = lo, h = hi, n = size;
147	while (h - l > THRESHOLD << 1) {
148	int m = (l + h) >>> 1;
149	addToPendingCount(1);
150	new RandomRepacker(this, s, d, m, h, n).fork();
151	h = m;
152	}
153	ThreadLocalRandom rng = ThreadLocalRandom.current();
154	Long dl = d[l];
155	int m = (dl == null) ? h : rng.nextInt(l, h);
156	for (int i = l; i < m; ++i)
157	d[i] = s[rng.nextInt(n)];
158	if (dl != null) {
159	dl = d[l];
160	for (int i = m; i < h; ++i)
161	d[i] = dl;
162	}
163	tryComplete();
164	}
165	}
166
167	static final class OrderChecker extends CountedCompleter<Void> {
168	final Long[] array;
169	final int lo, hi, size;
170	OrderChecker(CountedCompleter<?> par, Long[] a, int lo, int hi, int size) {
171	super(par);
172	this.array = a;
173	this.lo = lo; this.hi = hi; this.size = size;
174	}
175
176	public final void compute() {
177	Long[] a = this.array;
178	int l = lo, h = hi, n = size;
179	while (h - l > THRESHOLD) {
180	int m = (l + h) >>> 1;
181	addToPendingCount(1);
182	new OrderChecker(this, a, m, h, n).fork();
183	h = m;
184	}
185	int bound = h < n ? h : n - 1;
186	int i = l;
187	long x = a[i].longValue(), y;
188	while (i < bound) {
189	if (x > (y = a[++i].longValue()))
190	throw new Error("Unsorted " + x + " / " + y);
191	x = y;
192	}
193	tryComplete();
194	}
195	}
196
197	}