test/loops/CCBoxedLongSort.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.*;
import java.util.concurrent.*;

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

    static final int INSERTION_SORT_THRESHOLD = 8;
    //    static final int THRESHOLD = 64;
    static int THRESHOLD;

    public static void main(String[] args) throws Exception {
        int procs = 0;
        int n = 1 << 22;
        int reps = 30;
        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 BoxedLongSort threads n reps");
            return;
        }
        if (procs == 0)
            procs = Runtime.getRuntime().availableProcessors();

        THRESHOLD = ((n + 7) >>> 3) / procs;
        //        THRESHOLD = ((n + 15) >>> 4) / procs;
        //        THRESHOLD = ((n + 31) >>> 5) / procs;
        if (THRESHOLD < 64)
            THRESHOLD = 64;

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

        Long[] numbers = new Long[n];
        for (int i = 0; i < n; ++i)
            numbers[i] = Long.valueOf(i);
        Long[] a = new Long[n];
        ForkJoinPool pool = new ForkJoinPool(procs);
        seqTest(a, numbers, pool, 1);
        System.out.println(pool);
        parTest(a, numbers, pool, reps);
        System.out.println(pool);
        seqTest(a, numbers, pool, 2);
        System.out.println(pool);
        pool.shutdown();
    }

    static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
        int n = numbers.length;
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            pool.invoke(new RandomRepacker(null, numbers, a, 0, n, n));
            long last = System.nanoTime();
            quickSort(a, 0, n-1);
            //            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);
            pool.invoke(new OrderChecker(null, a, 0, n, n));
        }
    }

    static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
        int n = numbers.length;
        Long[] w = new Long[n];
        System.out.printf("Sorting %d longs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            pool.invoke(new RandomRepacker(null, numbers, a, 0, n, n));
            long last = System.nanoTime();
            pool.invoke(new Sorter(null, a, w, 0, n));
            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);
            pool.invoke(new OrderChecker(null, a, 0, n, n));
        }
    }

    /*
     * Merge sort alternates placing elements in the given array vs
     * the workspace array. To make sure the final elements are in the
     * given array, we descend in double steps.  So we need some
     * little tasks to serve as the place holders for triggering the
     * merges and re-merges. These don't need to keep track of the
     * arrays, and are never themselves forked, so are mostly empty.
     */
    static final class Subsorter extends CountedCompleter<Void> {
        Subsorter(CountedCompleter<?> p) { super(p); }
        public final void compute() { }
    }

    static final class Comerger extends CountedCompleter<Void> {
        final Merger merger;
        Comerger(Merger merger) {
            super(null, 1);
            this.merger = merger;
        }
        public final void compute() { }
        public final void onCompletion(CountedCompleter<?> t) {
            merger.compute();
        }
    }

    static final class Sorter extends CountedCompleter<Void> {
        final Long[] a;
        final Long[] w;
        final int origin;
        final int size;
        Sorter(CountedCompleter<?> par, Long[] a, Long[] w, int origin, int n) {
            super(par);
            this.a = a; this.w = w; this.origin = origin; this.size = n;
        }

        public final void compute() {
            Long[] a = this.a;
            Long[] w = this.w;
            int l = this.origin;
            int n = this.size;
            CountedCompleter<?> s = this;
            int thr = THRESHOLD;
            while (n > thr) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                int lq = l + q, lh = l + h, lu = l + u;
                int nh = n - h, nu = n - u, hq = h - q;
                Comerger fc =
                    new Comerger(new Merger(s, w, a, l, h, lh, nh, l));
                Comerger rc =
                    new Comerger(new Merger(fc, a, w, lh, q, lu, nu, lh));
                Comerger lc =
                    new Comerger(new Merger(fc, a, w, l, q, lq, hq, l));
                Sorter su = new Sorter(rc, a, w, lu, nu);
                Sorter sh = new Sorter(rc, a, w, lh, q);
                Sorter sq = new Sorter(lc, a, w, lq, hq);
                su.fork();
                sh.fork();
                sq.fork();
                s = new Subsorter(lc);
                n = q;
            }
            //            Arrays.sort(a, l, l+n);
            quickSort(a, l, l+n-1);
            s.tryComplete();
        }
    }

    static final class Merger extends CountedCompleter<Void> {
        final Long[] a; final Long[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        Merger(CountedCompleter<?> par,
               Long[] a, Long[] w, int lo, int ln, int ro, int rn, int wo) {
            super(par);
            this.a = a;    this.w = w;
            this.lo = lo;  this.ln = ln;
            this.ro = ro;  this.rn = rn;
            this.wo = wo;
        }

        /**
         * Merge left and right by splitting left in half,
         * and finding index of right closest to split point.
         */
        public final void compute() {
            int ln = this.ln;
            int rn = this.rn;
            int l = this.lo;
            int r = this.ro;
            int k = this.wo;
            Long[] a = this.a;
            Long[] w = this.w;
            int thr = THRESHOLD;
            while (ln > thr && rn > 4) {
                int lh = ln >>> 1;
                int lm = l + lh;
                Long split = a[lm];
                long ls = split.longValue();
                int rl = 0;
                int rh = rn;
                while (rl < rh) {
                    int rm = (rl + rh) >>> 1;
                    if (ls <= a[r + rm].longValue())
                        rh = rm;
                    else
                        rl = rm + 1;
                }
                addToPendingCount(1);
                new Merger(this, a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh).fork();
                rn = rh;
                ln = lh;
            }

            int lFence = l + ln;
            int rFence = r + rn;
            for (Long t;;) {
                if (l < lFence) {
                    Long al = a[l], ar;
                    if (r >= rFence ||
                        al.longValue() <= (ar = a[r]).longValue()) {
                        ++l; t = al;
                    }
                    else {
                        ++r; t = ar;
                    }
                }
                else if (r < rFence)
                    t = a[r++];
                else
                    break;
                w[k++] = t;
            }
            tryComplete();
        }
    }

    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) {
                int m = (l + h) >>> 1;
                addToPendingCount(1);
                new RandomRepacker(this, s, d, m, h, n).fork();
                h = m;
            }
            ThreadLocalRandom rng = ThreadLocalRandom.current();
            for (int i = l; i < h; ++i)
                d[i] = s[rng.nextInt(n)];
            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();
        }
    }

    static void quickSort(Long[] a, int lo, int hi) {
        for (;;) {
            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
                for (int i = lo + 1; i <= hi; i++) {
                    Long t = a[i];
                    long tv = t.longValue();
                    int j = i - 1;
                    while (j >= lo && tv < a[j].longValue()) {
                        a[j+1] = a[j];
                        --j;
                    }
                    a[j+1] = t;
                }
                return;
            }

            int mid = (lo + hi) >>> 1;
            if (a[lo].longValue() > a[mid].longValue()) {
                Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
            }
            if (a[mid].longValue() > a[hi].longValue()) {
                Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
                if (a[lo].longValue() > a[mid].longValue()) {
                    Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
                }
            }

            long pivot = a[mid].longValue();
            int left = lo+1;
            int right = hi-1;
            for (;;) {
                while (pivot < a[right].longValue())
                    --right;
                while (left < right && pivot >= a[left].longValue())
                    ++left;
                if (left < right) {
                    Long t = a[left]; a[left] = a[right]; a[right] = t;
                    --right;
                }
                else break;
            }

            if (left - lo <= hi - right) {
                quickSort(a, lo, left);
                lo = left + 1;
            }
            else {
                quickSort(a, right, hi);
                hi = left;
            }
        }
    }

}
Revision:	1.4
Committed:	Wed Dec 31 17:00:58 2014 UTC (9 years, 4 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.3:	+1 -1 lines
Log Message:	lexicographic import order
#	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/publicdomain/zero/1.0/
5			*/
6
7	jsr166	1.4	import java.util.*;
8	dl	1.1	import java.util.concurrent.*;
9
10			class CCBoxedLongSort {
11			static final long NPS = (1000L * 1000 * 1000);
12
13			static final int INSERTION_SORT_THRESHOLD = 8;
14			// static final int THRESHOLD = 64;
15			static int THRESHOLD;
16
17			public static void main(String[] args) throws Exception {
18			int procs = 0;
19			int n = 1 << 22;
20			int reps = 30;
21			int sreps = 2;
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[1]);
29			}
30			catch (Exception e) {
31			System.out.println("Usage: java BoxedLongSort threads n reps");
32			return;
33			}
34			if (procs == 0)
35			procs = Runtime.getRuntime().availableProcessors();
36
37			THRESHOLD = ((n + 7) >>> 3) / procs;
38			// THRESHOLD = ((n + 15) >>> 4) / procs;
39			// THRESHOLD = ((n + 31) >>> 5) / procs;
40			if (THRESHOLD < 64)
41			THRESHOLD = 64;
42
43			System.out.println("Threshold = " + THRESHOLD);
44
45			Long[] numbers = new Long[n];
46			for (int i = 0; i < n; ++i)
47			numbers[i] = Long.valueOf(i);
48			Long[] a = new Long[n];
49			ForkJoinPool pool = new ForkJoinPool(procs);
50			seqTest(a, numbers, pool, 1);
51			System.out.println(pool);
52			parTest(a, numbers, pool, reps);
53			System.out.println(pool);
54			seqTest(a, numbers, pool, 2);
55			System.out.println(pool);
56			pool.shutdown();
57			}
58
59			static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
60			int n = numbers.length;
61			System.out.printf("Sorting %d longs, %d replications\n", n, reps);
62			long start = System.nanoTime();
63			for (int i = 0; i < reps; ++i) {
64			pool.invoke(new RandomRepacker(null, numbers, a, 0, n, n));
65			long last = System.nanoTime();
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	jsr166	1.2	System.out.printf("Arrays.sort time: %7.3f total %9.3f\n",
72	dl	1.1	elapsed, total);
73			pool.invoke(new OrderChecker(null, a, 0, n, n));
74			}
75			}
76
77			static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) {
78			int n = numbers.length;
79			Long[] w = new Long[n];
80			System.out.printf("Sorting %d longs, %d replications\n", n, reps);
81			long start = System.nanoTime();
82			for (int i = 0; i < reps; ++i) {
83			pool.invoke(new RandomRepacker(null, numbers, a, 0, n, n));
84			long last = System.nanoTime();
85			pool.invoke(new Sorter(null, a, w, 0, n));
86			long now = System.nanoTime();
87			double total = (double)(now - start) / NPS;
88			double elapsed = (double)(now - last) / NPS;
89	jsr166	1.2	System.out.printf("Parallel sort time: %7.3f total %9.3f\n",
90	dl	1.1	elapsed, total);
91			pool.invoke(new OrderChecker(null, a, 0, n, n));
92			}
93			}
94
95			/*
96			* Merge sort alternates placing elements in the given array vs
97			* the workspace array. To make sure the final elements are in the
98			* given array, we descend in double steps. So we need some
99			* little tasks to serve as the place holders for triggering the
100			* merges and re-merges. These don't need to keep track of the
101			* arrays, and are never themselves forked, so are mostly empty.
102			*/
103	dl	1.3	static final class Subsorter extends CountedCompleter<Void> {
104			Subsorter(CountedCompleter<?> p) { super(p); }
105	dl	1.1	public final void compute() { }
106			}
107
108	dl	1.3	static final class Comerger extends CountedCompleter<Void> {
109	dl	1.1	final Merger merger;
110			Comerger(Merger merger) {
111			super(null, 1);
112			this.merger = merger;
113			}
114			public final void compute() { }
115	dl	1.3	public final void onCompletion(CountedCompleter<?> t) {
116	dl	1.1	merger.compute();
117			}
118			}
119
120	dl	1.3	static final class Sorter extends CountedCompleter<Void> {
121	dl	1.1	final Long[] a;
122			final Long[] w;
123			final int origin;
124			final int size;
125	dl	1.3	Sorter(CountedCompleter<?> par, Long[] a, Long[] w, int origin, int n) {
126	dl	1.1	super(par);
127			this.a = a; this.w = w; this.origin = origin; this.size = n;
128			}
129
130			public final void compute() {
131			Long[] a = this.a;
132			Long[] w = this.w;
133			int l = this.origin;
134			int n = this.size;
135	dl	1.3	CountedCompleter<?> s = this;
136	dl	1.1	int thr = THRESHOLD;
137			while (n > thr) {
138			int h = n >>> 1;
139			int q = n >>> 2;
140			int u = h + q;
141			int lq = l + q, lh = l + h, lu = l + u;
142			int nh = n - h, nu = n - u, hq = h - q;
143	jsr166	1.2	Comerger fc =
144	dl	1.1	new Comerger(new Merger(s, w, a, l, h, lh, nh, l));
145	jsr166	1.2	Comerger rc =
146	dl	1.1	new Comerger(new Merger(fc, a, w, lh, q, lu, nu, lh));
147	jsr166	1.2	Comerger lc =
148	dl	1.1	new Comerger(new Merger(fc, a, w, l, q, lq, hq, l));
149			Sorter su = new Sorter(rc, a, w, lu, nu);
150			Sorter sh = new Sorter(rc, a, w, lh, q);
151			Sorter sq = new Sorter(lc, a, w, lq, hq);
152			su.fork();
153			sh.fork();
154			sq.fork();
155			s = new Subsorter(lc);
156			n = q;
157			}
158			// Arrays.sort(a, l, l+n);
159			quickSort(a, l, l+n-1);
160	jsr166	1.2	s.tryComplete();
161	dl	1.1	}
162			}
163
164	dl	1.3	static final class Merger extends CountedCompleter<Void> {
165	dl	1.1	final Long[] a; final Long[] w;
166			final int lo; final int ln; final int ro; final int rn; final int wo;
167	dl	1.3	Merger(CountedCompleter<?> par,
168	dl	1.1	Long[] a, Long[] w, int lo, int ln, int ro, int rn, int wo) {
169			super(par);
170			this.a = a; this.w = w;
171			this.lo = lo; this.ln = ln;
172			this.ro = ro; this.rn = rn;
173			this.wo = wo;
174			}
175
176			/**
177			* Merge left and right by splitting left in half,
178			* and finding index of right closest to split point.
179			*/
180			public final void compute() {
181			int ln = this.ln;
182			int rn = this.rn;
183			int l = this.lo;
184			int r = this.ro;
185			int k = this.wo;
186			Long[] a = this.a;
187			Long[] w = this.w;
188			int thr = THRESHOLD;
189			while (ln > thr && rn > 4) {
190			int lh = ln >>> 1;
191			int lm = l + lh;
192			Long split = a[lm];
193			long ls = split.longValue();
194			int rl = 0;
195			int rh = rn;
196			while (rl < rh) {
197			int rm = (rl + rh) >>> 1;
198			if (ls <= a[r + rm].longValue())
199			rh = rm;
200			else
201			rl = rm + 1;
202			}
203			addToPendingCount(1);
204			new Merger(this, a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh).fork();
205			rn = rh;
206			ln = lh;
207			}
208	jsr166	1.2
209	dl	1.1	int lFence = l + ln;
210			int rFence = r + rn;
211			for (Long t;;) {
212			if (l < lFence) {
213			Long al = a[l], ar;
214			if (r >= rFence \|\|
215			al.longValue() <= (ar = a[r]).longValue()) {
216	jsr166	1.2	++l; t = al;
217			}
218			else {
219			++r; t = ar;
220	dl	1.1	}
221			}
222			else if (r < rFence)
223			t = a[r++];
224	jsr166	1.2	else
225	dl	1.1	break;
226			w[k++] = t;
227			}
228			tryComplete();
229			}
230			}
231
232			static void checkSorted(Long[] a) {
233			int n = a.length;
234			long x = a[0].longValue(), y;
235			for (int i = 0; i < n - 1; i++) {
236			if (x > (y = a[i+1].longValue()))
237			throw new Error("Unsorted at " + i + ": " + x + " / " + y);
238			x = y;
239			}
240			}
241
242	dl	1.3	static final class RandomRepacker extends CountedCompleter<Void> {
243	dl	1.1	final Long[] src;
244			final Long[] dst;
245			final int lo, hi, size;
246	dl	1.3	RandomRepacker(CountedCompleter<?> par, Long[] src, Long[] dst,
247	dl	1.1	int lo, int hi, int size) {
248			super(par);
249			this.src = src; this.dst = dst;
250			this.lo = lo; this.hi = hi; this.size = size;
251			}
252	jsr166	1.2
253	dl	1.1	public final void compute() {
254			Long[] s = src;
255			Long[] d = dst;
256			int l = lo, h = hi, n = size;
257			while (h - l > THRESHOLD) {
258			int m = (l + h) >>> 1;
259			addToPendingCount(1);
260			new RandomRepacker(this, s, d, m, h, n).fork();
261			h = m;
262			}
263			ThreadLocalRandom rng = ThreadLocalRandom.current();
264			for (int i = l; i < h; ++i)
265			d[i] = s[rng.nextInt(n)];
266			tryComplete();
267			}
268			}
269
270	dl	1.3	static final class OrderChecker extends CountedCompleter<Void> {
271	dl	1.1	final Long[] array;
272			final int lo, hi, size;
273	dl	1.3	OrderChecker(CountedCompleter<?> par, Long[] a, int lo, int hi, int size) {
274	dl	1.1	super(par);
275	jsr166	1.2	this.array = a;
276	dl	1.1	this.lo = lo; this.hi = hi; this.size = size;
277			}
278
279			public final void compute() {
280			Long[] a = this.array;
281			int l = lo, h = hi, n = size;
282			while (h - l > THRESHOLD) {
283			int m = (l + h) >>> 1;
284			addToPendingCount(1);
285			new OrderChecker(this, a, m, h, n).fork();
286			h = m;
287			}
288			int bound = h < n ? h : n - 1;
289			int i = l;
290			long x = a[i].longValue(), y;
291			while (i < bound) {
292			if (x > (y = a[++i].longValue()))
293			throw new Error("Unsorted " + x + " / " + y);
294			x = y;
295			}
296			tryComplete();
297			}
298			}
299
300			static void quickSort(Long[] a, int lo, int hi) {
301			for (;;) {
302			if (hi - lo <= INSERTION_SORT_THRESHOLD) {
303			for (int i = lo + 1; i <= hi; i++) {
304			Long t = a[i];
305			long tv = t.longValue();
306			int j = i - 1;
307			while (j >= lo && tv < a[j].longValue()) {
308			a[j+1] = a[j];
309			--j;
310			}
311			a[j+1] = t;
312			}
313			return;
314			}
315
316			int mid = (lo + hi) >>> 1;
317			if (a[lo].longValue() > a[mid].longValue()) {
318			Long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
319			}
320			if (a[mid].longValue() > a[hi].longValue()) {
321			Long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
322			if (a[lo].longValue() > a[mid].longValue()) {
323			Long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
324			}
325			}
326
327			long pivot = a[mid].longValue();
328			int left = lo+1;
329			int right = hi-1;
330			for (;;) {
331			while (pivot < a[right].longValue())
332			--right;
333			while (left < right && pivot >= a[left].longValue())
334			++left;
335			if (left < right) {
336			Long t = a[left]; a[left] = a[right]; a[right] = t;
337			--right;
338			}
339			else break;
340			}
341
342			if (left - lo <= hi - right) {
343			quickSort(a, lo, left);
344			lo = left + 1;
345			}
346			else {
347			quickSort(a, right, hi);
348			hi = left;
349			}
350			}
351			}
352
353			}