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/licenses/publicdomain
 */

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

class ScalarLongSort {
    static final long NPS = (1000L * 1000 * 1000);

    static int THRESHOLD;
    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;
        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[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java ScalarLongSort threads n reps");
            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);
        }

        // for now hardwire 8 * #CPUs leaf tasks
        THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism();
        //        THRESHOLD = 1 + ((n + 15) >>> 4) / pool.getParallelism();
        //        THRESHOLD = 1 + ((n + 31) >>> 5) / pool.getParallelism();

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