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.*;
import java.util.concurrent.*;

// Based very loosely on cilksort

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

    static int THRESHOLD;
    static final boolean warmup = true;

    public static void main (String[] args) throws Exception {
        int n = 1 << 22;
        int sreps = 2;
        int reps = 20;
        long[] a = new long[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);
        }

        ForkJoinPool pool = new ForkJoinPool();
        // 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
                SubSorter rs;
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                (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))).fork();
                (new SubSorter
                 (new Sorter(a, w, l,   q),
                  new Sorter(a, w, l+q, h-q),
                  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;
        final 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 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;
            }

            // Base case -- merge left and right
            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++];

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