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 = ((Long)a[0]).longValue(), y;
        for (int i = 0; i < n - 1; i++) {
            if (x > (y = ((Long)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 = ((Long)a[i]).longValue(), y;
            while (i < bound) {
                if (x > (y = ((Long)a[++i]).longValue()))
                    throw new Error("Unsorted " + x + " / " + y);
                x = y;
            }
            tryComplete();
        }
    }

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