test/loops/ScalarLongSort.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 ScalarLongSort {
    static final long NPS = (1000L * 1000 * 1000);

    static int THRESHOLD = -1;
    static final boolean warmup = true;

    public static void main (String[] args) throws Exception {
        int procs = 0;
        int n = 1 << 22;
        int reps = 20;
        int sreps = 2;
        int st = -1;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
            if (args.length > 1)
                n = Integer.parseInt(args[1]);
            if (args.length > 2)
                reps = Integer.parseInt(args[2]);
            if (args.length > 3)
                st = Integer.parseInt(args[3]);
        }
        catch (Exception e) {
            System.out.println("Usage: java ScalarLongSort threads n reps sequential-threshold");
            return;
        }
        ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
            new ForkJoinPool(procs);

        long[] a = new long[n];
        seqRandomFill(a, 0, n);

        if (warmup) {
            System.out.printf("Sorting %d longs, %d replications\n", n, 1);
            seqRandomFill(a, 0, n);
            long last = System.nanoTime();
            java.util.Arrays.sort(a);
            double elapsed = (double)(System.nanoTime() - last) / NPS;
            System.out.printf("Arrays.sort   time:  %7.3f\n", elapsed);
            checkSorted(a);
        }

        if (st <= 0) // for now hardwire 8 * #CPUs leaf tasks
            THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
        else
            THRESHOLD = st;

        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        for (int i = 0; i < reps; ++i) {
            pool.invoke(new RandomFiller(a, 0, n));
            long last = System.nanoTime();
            pool.invoke(new Sorter(a, new long[n], 0, n));
            double elapsed = (double)(System.nanoTime() - last) / NPS;
            System.out.printf("Parallel sort time: %7.3f\n", elapsed);
            if (i == 0)
                checkSorted(a);
        }
        System.out.println(pool);

        System.out.printf("Sorting %d longs, %d replications\n", n, sreps);
        for (int i = 0; i < sreps; ++i) {
            pool.invoke(new RandomFiller(a, 0, n));
            long last = System.nanoTime();
            java.util.Arrays.sort(a);
            double elapsed = (double)(System.nanoTime() - last) / NPS;
            System.out.printf("Arrays.sort   time:  %7.3f\n", elapsed);
            if (i == 0)
                checkSorted(a);
        }
        System.out.println(pool);


        pool.shutdown();
    }

    static final class Sorter extends RecursiveAction {
        final long[] a;
        final long[] w;
        final int origin;
        final int n;
        Sorter(long[] a, long[] w, int origin, int n) {
            this.a = a; this.w = w; this.origin = origin; this.n = n;
        }

        public void compute() {
            int l = origin;
            if (n <= THRESHOLD)
                Arrays.sort(a, l, l+n);
            else { // divide in quarters to ensure sorted array in a not w
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                SubSorter rs = new SubSorter
                    (new Sorter(a, w, l+h, q),
                     new Sorter(a, w, l+u, n-u),
                     new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
                rs.fork();
                Sorter rl = new Sorter(a, w, l+q, h-q);
                rl.fork();
                (new Sorter(a, w, l,   q)).compute();
                rl.join();
                (new Merger(a, w, l,   q, l+q, h-q, l, null)).compute();
                rs.join();
                new Merger(w, a, l, h, l+h, n-h, l, null).compute();
            }
        }
    }

    static final class SubSorter extends RecursiveAction {
        final Sorter left;
        final Sorter right;
        final Merger merger;
        SubSorter(Sorter left, Sorter right, Merger merger) {
            this.left = left; this.right = right; this.merger = merger;
        }
        public void compute() {
            right.fork();
            left.compute();
            right.join();
            merger.compute();
        }
    }

    static final class Merger extends RecursiveAction {
        final long[] a; final long[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        Merger next;
        Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
               Merger next) {
            this.a = a;    this.w = w;
            this.lo = lo;  this.ln = ln;
            this.ro = ro;  this.rn = rn;
            this.wo = wo;
            this.next = next;
        }

        /**
         * Merge left and right by splitting left in half,
         * and finding index of right closest to split point.
         * Uses left-spine decomposition to generate all
         * merge tasks before bottomming out at base case.
         *
         */
        public final void compute() {
            Merger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > THRESHOLD) { //  && nright > (THRESHOLD >>> 3)) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                long split = a[splitIndex];
                int rl = 0;
                int rh = nright;
                while (rl < rh) {
                    int mid = (rl + rh) >>> 1;
                    if (split <= a[ro + mid])
                        rh = mid;
                    else
                        rl = mid + 1;
                }
                (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
                                     nright-rh, wo+lh+rh, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            merge(nleft, nright);
            if (rights != null)
                collectRights(rights);

        }

        final void merge(int nleft, int nright) {
            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                long al = a[l];
                long ar = a[r];
                long t;
                if (al <= ar) { ++l; t = al; } else { ++r; t = ar; }
                w[k++] = t;
            }
            while (l < lFence)
                w[k++] = a[l++];
            while (r < rFence)
                w[k++] = a[r++];
        }

        static void collectRights(Merger rt) {
            while (rt != null) {
                Merger next = rt.next;
                rt.next = null;
                if (rt.tryUnfork()) rt.compute(); else rt.join();
                rt = next;
            }
        }

    }

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

    static void seqRandomFill(long[] array, int lo, int hi) {
        ThreadLocalRandom rng = ThreadLocalRandom.current();
        for (int i = lo; i < hi; ++i)
            array[i] = rng.nextLong();
    }

    static final class RandomFiller extends RecursiveAction {
        final long[] array;
        final int lo, hi;
        RandomFiller(long[] array, int lo, int hi) {
            this.array = array; this.lo = lo; this.hi = hi;
        }
        public void compute() {
            if (hi - lo <= THRESHOLD) {
                long[] a = array;
                ThreadLocalRandom rng = ThreadLocalRandom.current();
                for (int i = lo; i < hi; ++i)
                    a[i] = rng.nextLong();
            }
            else {
                int mid = (lo + hi) >>> 1;
                RandomFiller r = new RandomFiller(array, mid, hi);
                r.fork();
                (new RandomFiller(array, lo, mid)).compute();
                r.join();
            }
        }
    }


}
Revision:	1.9
Committed:	Fri Aug 19 11:25:04 2011 UTC (12 years, 9 months ago) by dl
Branch:	MAIN
Changes since 1.8:	+10 -7 lines
Log Message:	Add sequential threshold command argument
#	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 ScalarLongSort {
11	static final long NPS = (1000L * 1000 * 1000);
12
13	static int THRESHOLD = -1;
14	static final boolean warmup = true;
15
16	public static void main (String[] args) throws Exception {
17	int procs = 0;
18	int n = 1 << 22;
19	int reps = 20;
20	int sreps = 2;
21	int st = -1;
22	try {
23	if (args.length > 0)
24	procs = Integer.parseInt(args[0]);
25	if (args.length > 1)
26	n = Integer.parseInt(args[1]);
27	if (args.length > 2)
28	reps = Integer.parseInt(args[2]);
29	if (args.length > 3)
30	st = Integer.parseInt(args[3]);
31	}
32	catch (Exception e) {
33	System.out.println("Usage: java ScalarLongSort threads n reps sequential-threshold");
34	return;
35	}
36	ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
37	new ForkJoinPool(procs);
38
39	long[] a = new long[n];
40	seqRandomFill(a, 0, n);
41
42	if (warmup) {
43	System.out.printf("Sorting %d longs, %d replications\n", n, 1);
44	seqRandomFill(a, 0, n);
45	long last = System.nanoTime();
46	java.util.Arrays.sort(a);
47	double elapsed = (double)(System.nanoTime() - last) / NPS;
48	System.out.printf("Arrays.sort time: %7.3f\n", elapsed);
49	checkSorted(a);
50	}
51
52	if (st <= 0) // for now hardwire 8 * #CPUs leaf tasks
53	THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
54	else
55	THRESHOLD = st;
56
57	System.out.printf("Sorting %d longs, %d replications\n", n, reps);
58	for (int i = 0; i < reps; ++i) {
59	pool.invoke(new RandomFiller(a, 0, n));
60	long last = System.nanoTime();
61	pool.invoke(new Sorter(a, new long[n], 0, n));
62	double elapsed = (double)(System.nanoTime() - last) / NPS;
63	System.out.printf("Parallel sort time: %7.3f\n", elapsed);
64	if (i == 0)
65	checkSorted(a);
66	}
67	System.out.println(pool);
68
69	System.out.printf("Sorting %d longs, %d replications\n", n, sreps);
70	for (int i = 0; i < sreps; ++i) {
71	pool.invoke(new RandomFiller(a, 0, n));
72	long last = System.nanoTime();
73	java.util.Arrays.sort(a);
74	double elapsed = (double)(System.nanoTime() - last) / NPS;
75	System.out.printf("Arrays.sort time: %7.3f\n", elapsed);
76	if (i == 0)
77	checkSorted(a);
78	}
79	System.out.println(pool);
80
81
82	pool.shutdown();
83	}
84
85	static final class Sorter extends RecursiveAction {
86	final long[] a;
87	final long[] w;
88	final int origin;
89	final int n;
90	Sorter(long[] a, long[] w, int origin, int n) {
91	this.a = a; this.w = w; this.origin = origin; this.n = n;
92	}
93
94	public void compute() {
95	int l = origin;
96	if (n <= THRESHOLD)
97	Arrays.sort(a, l, l+n);
98	else { // divide in quarters to ensure sorted array in a not w
99	int h = n >>> 1;
100	int q = n >>> 2;
101	int u = h + q;
102	SubSorter rs = new SubSorter
103	(new Sorter(a, w, l+h, q),
104	new Sorter(a, w, l+u, n-u),
105	new Merger(a, w, l+h, q, l+u, n-u, l+h, null));
106	rs.fork();
107	Sorter rl = new Sorter(a, w, l+q, h-q);
108	rl.fork();
109	(new Sorter(a, w, l, q)).compute();
110	rl.join();
111	(new Merger(a, w, l, q, l+q, h-q, l, null)).compute();
112	rs.join();
113	new Merger(w, a, l, h, l+h, n-h, l, null).compute();
114	}
115	}
116	}
117
118	static final class SubSorter extends RecursiveAction {
119	final Sorter left;
120	final Sorter right;
121	final Merger merger;
122	SubSorter(Sorter left, Sorter right, Merger merger) {
123	this.left = left; this.right = right; this.merger = merger;
124	}
125	public void compute() {
126	right.fork();
127	left.compute();
128	right.join();
129	merger.compute();
130	}
131	}
132
133	static final class Merger extends RecursiveAction {
134	final long[] a; final long[] w;
135	final int lo; final int ln; final int ro; final int rn; final int wo;
136	Merger next;
137	Merger(long[] a, long[] w, int lo, int ln, int ro, int rn, int wo,
138	Merger next) {
139	this.a = a; this.w = w;
140	this.lo = lo; this.ln = ln;
141	this.ro = ro; this.rn = rn;
142	this.wo = wo;
143	this.next = next;
144	}
145
146	/**
147	* Merge left and right by splitting left in half,
148	* and finding index of right closest to split point.
149	* Uses left-spine decomposition to generate all
150	* merge tasks before bottomming out at base case.
151	*
152	*/
153	public final void compute() {
154	Merger rights = null;
155	int nleft = ln;
156	int nright = rn;
157	while (nleft > THRESHOLD) { // && nright > (THRESHOLD >>> 3)) {
158	int lh = nleft >>> 1;
159	int splitIndex = lo + lh;
160	long split = a[splitIndex];
161	int rl = 0;
162	int rh = nright;
163	while (rl < rh) {
164	int mid = (rl + rh) >>> 1;
165	if (split <= a[ro + mid])
166	rh = mid;
167	else
168	rl = mid + 1;
169	}
170	(rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,
171	nright-rh, wo+lh+rh, rights)).fork();
172	nleft = lh;
173	nright = rh;
174	}
175
176	merge(nleft, nright);
177	if (rights != null)
178	collectRights(rights);
179
180	}
181
182	final void merge(int nleft, int nright) {
183	int l = lo;
184	int lFence = lo + nleft;
185	int r = ro;
186	int rFence = ro + nright;
187	int k = wo;
188	while (l < lFence && r < rFence) {
189	long al = a[l];
190	long ar = a[r];
191	long t;
192	if (al <= ar) { ++l; t = al; } else { ++r; t = ar; }
193	w[k++] = t;
194	}
195	while (l < lFence)
196	w[k++] = a[l++];
197	while (r < rFence)
198	w[k++] = a[r++];
199	}
200
201	static void collectRights(Merger rt) {
202	while (rt != null) {
203	Merger next = rt.next;
204	rt.next = null;
205	if (rt.tryUnfork()) rt.compute(); else rt.join();
206	rt = next;
207	}
208	}
209
210	}
211
212	static void checkSorted (long[] a) {
213	int n = a.length;
214	for (int i = 0; i < n - 1; i++) {
215	if (a[i] > a[i+1]) {
216	throw new Error("Unsorted at " + i + ": " +
217	a[i] + " / " + a[i+1]);
218	}
219	}
220	}
221
222	static void seqRandomFill(long[] array, int lo, int hi) {
223	ThreadLocalRandom rng = ThreadLocalRandom.current();
224	for (int i = lo; i < hi; ++i)
225	array[i] = rng.nextLong();
226	}
227
228	static final class RandomFiller extends RecursiveAction {
229	final long[] array;
230	final int lo, hi;
231	RandomFiller(long[] array, int lo, int hi) {
232	this.array = array; this.lo = lo; this.hi = hi;
233	}
234	public void compute() {
235	if (hi - lo <= THRESHOLD) {
236	long[] a = array;
237	ThreadLocalRandom rng = ThreadLocalRandom.current();
238	for (int i = lo; i < hi; ++i)
239	a[i] = rng.nextLong();
240	}
241	else {
242	int mid = (lo + hi) >>> 1;
243	RandomFiller r = new RandomFiller(array, mid, hi);
244	r.fork();
245	(new RandomFiller(array, lo, mid)).compute();
246	r.join();
247	}
248	}
249	}
250
251
252	}