test/extra166y/CombineDemo.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 jsr166y.*;
import extra166y.*;
import java.util.*;

class CombineDemo {

    static final Random rng = new Random();
    static final long NPS = (1000L * 1000 * 1000);
    static ForkJoinPool fjpool = new ForkJoinPool();
    static int reps = 16;
    static final long maxValue = 1 << 12;

    public static void main(String[] args) throws Exception {
        int n = 1 << 20;
        Long[] a = new Long[n];
        ParallelArray<Long> pa = ParallelArray.createUsingHandoff(a, fjpool);
        System.out.printf("Using %d Longs, %d replications\n", n, reps);
        seqSelectTest(pa);
        selectTest(pa);
        seqRemoveTest(pa);
        removeTest(pa);
        seqUniqTest(pa);
        parUniqTest(pa);
        sortUniqTest(pa);
        seqFindTest(pa);
        parFindTest(pa);
        fjpool.shutdown();
    }


    static int nresets = 0;
    static void reset(ParallelArray<Long> pa) {
        pa.replaceWithGeneratedValue(rlg);
        if (nresets++ == 0) System.out.println(pa.summary());
    }

    static void resetToEvens(ParallelArray<Long> pa) {
        pa.replaceWithMappedIndex(evens);
    }

    static class Evens implements Ops.IntToObject<Long> {
        public Long op(int i) {
            return Long.valueOf((long)(i << 1));
        }
    }

    static class IsOdd implements Ops.Predicate<Long> {
        public boolean op(Long x) {
            return (x.longValue() & 1) != 0;
        }
    }

    static class IsEven implements Ops.Predicate<Long> {
        public boolean op(Long x) {
            return (x.longValue() & 1) == 0;
        }
    }

    static final IsOdd isOdd = new IsOdd();
    static final IsEven isEven = new IsEven();
    static final Evens evens = new Evens();

    static void parUniqTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelArray<Long> u = pa.allUniqueElements();
            elapsed += System.nanoTime() - last;
            u.sort();
            checkSorted(u);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Uniq time             %7.3f\n", de);
    }

    static void seqUniqTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            Long[] u = seqUnique(pa.getArray());
            elapsed += System.nanoTime() - last;
            ParallelArray<Long> pu = ParallelArray.createUsingHandoff(u, fjpool);
            pu.sort();
            checkSorted(pu);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq Uniq time:        %7.3f\n", de);
    }

    static void sortUniqTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            last = System.nanoTime();
            ParallelArray<Long> u = pa.all();
            u.sort();
            u.removeConsecutiveDuplicates();
            elapsed += System.nanoTime() - last;
            checkSorted(u);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Par Uniq Sort time :  %7.3f\n", de);
    }

    static void removeTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            ParallelArray<Long> u = pa.all();
            last = System.nanoTime();
            u.removeAll(isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != evenSize)
                throw new Error(usize + " should be " + evenSize);
            Long a = u.withFilter(isOdd).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("RemoveAll time :      %7.3f\n", de);
    }

    static void seqRemoveTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            ParallelArray<Long> u = pa.all();
            last = System.nanoTime();
            seqRemoveAll(u, isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != evenSize)
                throw new Error(usize + " should be " + evenSize);
            Long a = u.withFilter(isOdd).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq RemoveAll time :  %7.3f\n", de);
    }

    static void selectTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            last = System.nanoTime();
            ParallelArray<Long> u = pa.withFilter(isOdd).all();
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != oddSize)
                throw new Error(usize + " should be " + evenSize);
            Long a = u.withFilter(isEven).any();
            if (a != null)
                throw new Error("found " + a);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("SelectAll time :      %7.3f\n", de);
    }

    static void seqSelectTest(ParallelArray<Long> pa) {
        int n = pa.size();
        long last;
        long elapsed = 0;
        for (int i = 0; i < reps; ++i) {
            reset(pa);
            int psize = pa.size();
            int oddSize = pa.withFilter(isOdd).size();
            int evenSize = psize - oddSize;
            last = System.nanoTime();
            ArrayList<Long> u = seqSelectAll(pa, isOdd);
            elapsed += System.nanoTime() - last;
            int usize = u.size();
            if (usize != oddSize)
                throw new Error(usize + " should be " + evenSize);
        }
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq SelectAll time :  %7.3f\n", de);
    }

    static void parFindTest(ParallelArray<Long> pa) {
        Random rng = new Random();
        int n = pa.size();
        long last;
        long elapsed = 0;
        resetToEvens(pa);
        last = System.nanoTime();
        for (int i = 0; i < reps * 16; ++i) {
            int rnd = rng.nextInt(n * 2);
            boolean expect = (rnd & 1) == 0;
            Long t = Long.valueOf(rnd);
            boolean contains = pa.indexOf(t) >= 0;
            if (expect != contains)
                throw new Error();
        }
        elapsed += System.nanoTime() - last;
        double de = (double)(elapsed) / NPS;
        System.out.printf("Par index time :      %7.3f\n", de);
    }

    static void seqFindTest(ParallelArray<Long> pa) {
        List<Long> pal = pa.asList();
        Random rng = new Random();
        int n = pa.size();
        long last;
        long elapsed = 0;
        resetToEvens(pa);
        last = System.nanoTime();
        for (int i = 0; i < reps * 16; ++i) {
            int rnd = rng.nextInt(n * 2);
            boolean expect = (rnd & 1) == 0;
            Long t = Long.valueOf(rnd);
            boolean contains = pal.indexOf(t) >= 0;
            if (expect != contains)
                throw new Error();
        }
        elapsed += System.nanoTime() - last;
        double de = (double)(elapsed) / NPS;
        System.out.printf("Seq index time :      %7.3f\n", de);
    }

    // ............

    static void seqRemoveAll(ParallelArray<Long> pa,
                             Ops.Predicate<Long> selector) {
        Long[] a = pa.getArray();
        int n = pa.size();
        int k = 0;
        for (int i = 0; i < n; ++i) {
            Long x = a[i];
            if (!selector.op(x))
                a[k++] = x;
        }
        for (int j = k; j < n; ++j)
            a[j] = null;
        pa.setLimit(k);
    }

    static ArrayList<Long> seqSelectAll(ParallelArray<Long> pa,
                                        Ops.Predicate<Long> selector) {
        ArrayList<Long> al = new ArrayList<Long>();
        Long[] a = pa.getArray();
        int n = pa.size();
        for (int i = 0; i < n; ++i) {
            Long x = a[i];
            if (selector.op(x))
                al.add(x);
        }
        return al;
    }

    static Long[] seqUnique(Long[] a) {
        int n = a.length;
        HashSet<Long> m = new HashSet<Long>(n);
        for (int i = 0; i < n; ++i)
            m.add(a[i]);
        int ul = m.size();
        Long[] u = new Long[ul];
        int k = 0;
        for (Long e : m)
            u[k++] = e;
        return u;
    }

    static void checkSorted(ParallelArray<Long> pa) {
        int n = pa.size();
        for (int i = 0; i < n - 1; i++) {
            if (pa.get(i).compareTo(pa.get(i+1)) >= 0) {
                throw new Error("Unsorted at " + i + ": " + pa.get(i) + " / " + pa.get(i+1));
            }
        }
    }

    static final class RandomLongGenerator implements Ops.Generator<Long> {
        public Long op() {
            return new Long(ThreadLocalRandom.current().nextLong(maxValue));
        }
    }

    static final RandomLongGenerator rlg = new RandomLongGenerator();
}
Revision:	1.5
Committed:	Tue Mar 15 19:47:04 2011 UTC (13 years, 1 month ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0, HEAD
Changes since 1.4:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices
#	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	jsr166	1.5	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.1	*/
6
7			import jsr166y.*;
8			import extra166y.*;
9			import java.util.*;
10
11			class CombineDemo {
12
13			static final Random rng = new Random();
14			static final long NPS = (1000L * 1000 * 1000);
15			static ForkJoinPool fjpool = new ForkJoinPool();
16			static int reps = 16;
17			static final long maxValue = 1 << 12;
18
19	jsr166	1.3	public static void main(String[] args) throws Exception {
20	dl	1.1	int n = 1 << 20;
21			Long[] a = new Long[n];
22			ParallelArray<Long> pa = ParallelArray.createUsingHandoff(a, fjpool);
23			System.out.printf("Using %d Longs, %d replications\n", n, reps);
24			seqSelectTest(pa);
25			selectTest(pa);
26			seqRemoveTest(pa);
27			removeTest(pa);
28			seqUniqTest(pa);
29			parUniqTest(pa);
30			sortUniqTest(pa);
31			seqFindTest(pa);
32			parFindTest(pa);
33			fjpool.shutdown();
34			}
35
36
37			static int nresets = 0;
38			static void reset(ParallelArray<Long> pa) {
39			pa.replaceWithGeneratedValue(rlg);
40			if (nresets++ == 0) System.out.println(pa.summary());
41			}
42
43			static void resetToEvens(ParallelArray<Long> pa) {
44			pa.replaceWithMappedIndex(evens);
45			}
46
47			static class Evens implements Ops.IntToObject<Long> {
48	jsr166	1.2	public Long op(int i) {
49	dl	1.1	return Long.valueOf((long)(i << 1));
50			}
51			}
52
53			static class IsOdd implements Ops.Predicate<Long> {
54			public boolean op(Long x) {
55			return (x.longValue() & 1) != 0;
56			}
57			}
58
59			static class IsEven implements Ops.Predicate<Long> {
60			public boolean op(Long x) {
61			return (x.longValue() & 1) == 0;
62			}
63			}
64
65			static final IsOdd isOdd = new IsOdd();
66			static final IsEven isEven = new IsEven();
67			static final Evens evens = new Evens();
68
69			static void parUniqTest(ParallelArray<Long> pa) {
70			int n = pa.size();
71			long last;
72			long elapsed = 0;
73			for (int i = 0; i < reps; ++i) {
74			reset(pa);
75			last = System.nanoTime();
76			ParallelArray<Long> u = pa.allUniqueElements();
77			elapsed += System.nanoTime() - last;
78			u.sort();
79			checkSorted(u);
80			}
81			double de = (double)(elapsed) / NPS;
82			System.out.printf("Uniq time %7.3f\n", de);
83			}
84
85			static void seqUniqTest(ParallelArray<Long> pa) {
86			int n = pa.size();
87			long last;
88			long elapsed = 0;
89			for (int i = 0; i < reps; ++i) {
90			reset(pa);
91			last = System.nanoTime();
92			Long[] u = seqUnique(pa.getArray());
93			elapsed += System.nanoTime() - last;
94			ParallelArray<Long> pu = ParallelArray.createUsingHandoff(u, fjpool);
95			pu.sort();
96			checkSorted(pu);
97			}
98			double de = (double)(elapsed) / NPS;
99			System.out.printf("Seq Uniq time: %7.3f\n", de);
100			}
101
102			static void sortUniqTest(ParallelArray<Long> pa) {
103			int n = pa.size();
104			long last;
105			long elapsed = 0;
106			for (int i = 0; i < reps; ++i) {
107			reset(pa);
108			last = System.nanoTime();
109			ParallelArray<Long> u = pa.all();
110			u.sort();
111			u.removeConsecutiveDuplicates();
112			elapsed += System.nanoTime() - last;
113			checkSorted(u);
114			}
115			double de = (double)(elapsed) / NPS;
116			System.out.printf("Par Uniq Sort time : %7.3f\n", de);
117			}
118
119			static void removeTest(ParallelArray<Long> pa) {
120			int n = pa.size();
121			long last;
122			long elapsed = 0;
123			for (int i = 0; i < reps; ++i) {
124			reset(pa);
125			int psize = pa.size();
126			int oddSize = pa.withFilter(isOdd).size();
127			int evenSize = psize - oddSize;
128			ParallelArray<Long> u = pa.all();
129			last = System.nanoTime();
130			u.removeAll(isOdd);
131			elapsed += System.nanoTime() - last;
132			int usize = u.size();
133			if (usize != evenSize)
134			throw new Error(usize + " should be " + evenSize);
135			Long a = u.withFilter(isOdd).any();
136			if (a != null)
137			throw new Error("found " + a);
138			}
139			double de = (double)(elapsed) / NPS;
140			System.out.printf("RemoveAll time : %7.3f\n", de);
141			}
142
143			static void seqRemoveTest(ParallelArray<Long> pa) {
144			int n = pa.size();
145			long last;
146			long elapsed = 0;
147			for (int i = 0; i < reps; ++i) {
148			reset(pa);
149			int psize = pa.size();
150			int oddSize = pa.withFilter(isOdd).size();
151			int evenSize = psize - oddSize;
152			ParallelArray<Long> u = pa.all();
153			last = System.nanoTime();
154			seqRemoveAll(u, isOdd);
155			elapsed += System.nanoTime() - last;
156			int usize = u.size();
157			if (usize != evenSize)
158			throw new Error(usize + " should be " + evenSize);
159			Long a = u.withFilter(isOdd).any();
160			if (a != null)
161			throw new Error("found " + a);
162			}
163			double de = (double)(elapsed) / NPS;
164			System.out.printf("Seq RemoveAll time : %7.3f\n", de);
165			}
166
167			static void selectTest(ParallelArray<Long> pa) {
168			int n = pa.size();
169			long last;
170			long elapsed = 0;
171			for (int i = 0; i < reps; ++i) {
172			reset(pa);
173			int psize = pa.size();
174			int oddSize = pa.withFilter(isOdd).size();
175			int evenSize = psize - oddSize;
176			last = System.nanoTime();
177			ParallelArray<Long> u = pa.withFilter(isOdd).all();
178			elapsed += System.nanoTime() - last;
179			int usize = u.size();
180			if (usize != oddSize)
181			throw new Error(usize + " should be " + evenSize);
182			Long a = u.withFilter(isEven).any();
183			if (a != null)
184			throw new Error("found " + a);
185			}
186			double de = (double)(elapsed) / NPS;
187			System.out.printf("SelectAll time : %7.3f\n", de);
188			}
189
190			static void seqSelectTest(ParallelArray<Long> pa) {
191			int n = pa.size();
192			long last;
193			long elapsed = 0;
194			for (int i = 0; i < reps; ++i) {
195			reset(pa);
196			int psize = pa.size();
197			int oddSize = pa.withFilter(isOdd).size();
198			int evenSize = psize - oddSize;
199			last = System.nanoTime();
200			ArrayList<Long> u = seqSelectAll(pa, isOdd);
201			elapsed += System.nanoTime() - last;
202			int usize = u.size();
203			if (usize != oddSize)
204			throw new Error(usize + " should be " + evenSize);
205			}
206			double de = (double)(elapsed) / NPS;
207			System.out.printf("Seq SelectAll time : %7.3f\n", de);
208			}
209
210			static void parFindTest(ParallelArray<Long> pa) {
211			Random rng = new Random();
212			int n = pa.size();
213			long last;
214			long elapsed = 0;
215			resetToEvens(pa);
216			last = System.nanoTime();
217			for (int i = 0; i < reps * 16; ++i) {
218			int rnd = rng.nextInt(n * 2);
219			boolean expect = (rnd & 1) == 0;
220			Long t = Long.valueOf(rnd);
221			boolean contains = pa.indexOf(t) >= 0;
222			if (expect != contains)
223			throw new Error();
224			}
225			elapsed += System.nanoTime() - last;
226			double de = (double)(elapsed) / NPS;
227			System.out.printf("Par index time : %7.3f\n", de);
228			}
229
230			static void seqFindTest(ParallelArray<Long> pa) {
231			List<Long> pal = pa.asList();
232			Random rng = new Random();
233			int n = pa.size();
234			long last;
235			long elapsed = 0;
236			resetToEvens(pa);
237			last = System.nanoTime();
238			for (int i = 0; i < reps * 16; ++i) {
239			int rnd = rng.nextInt(n * 2);
240			boolean expect = (rnd & 1) == 0;
241			Long t = Long.valueOf(rnd);
242			boolean contains = pal.indexOf(t) >= 0;
243			if (expect != contains)
244			throw new Error();
245			}
246			elapsed += System.nanoTime() - last;
247			double de = (double)(elapsed) / NPS;
248			System.out.printf("Seq index time : %7.3f\n", de);
249			}
250
251			// ............
252
253	jsr166	1.2	static void seqRemoveAll(ParallelArray<Long> pa,
254	dl	1.1	Ops.Predicate<Long> selector) {
255			Long[] a = pa.getArray();
256			int n = pa.size();
257			int k = 0;
258			for (int i = 0; i < n; ++i) {
259			Long x = a[i];
260			if (!selector.op(x))
261			a[k++] = x;
262			}
263			for (int j = k; j < n; ++j)
264			a[j] = null;
265			pa.setLimit(k);
266			}
267
268	jsr166	1.2	static ArrayList<Long> seqSelectAll(ParallelArray<Long> pa,
269	dl	1.1	Ops.Predicate<Long> selector) {
270			ArrayList<Long> al = new ArrayList<Long>();
271			Long[] a = pa.getArray();
272			int n = pa.size();
273			for (int i = 0; i < n; ++i) {
274			Long x = a[i];
275			if (selector.op(x))
276			al.add(x);
277			}
278			return al;
279			}
280
281			static Long[] seqUnique(Long[] a) {
282			int n = a.length;
283			HashSet<Long> m = new HashSet<Long>(n);
284	jsr166	1.2	for (int i = 0; i < n; ++i)
285	dl	1.1	m.add(a[i]);
286			int ul = m.size();
287			Long[] u = new Long[ul];
288			int k = 0;
289			for (Long e : m)
290			u[k++] = e;
291			return u;
292			}
293	jsr166	1.2
294	jsr166	1.4	static void checkSorted(ParallelArray<Long> pa) {
295	dl	1.1	int n = pa.size();
296			for (int i = 0; i < n - 1; i++) {
297			if (pa.get(i).compareTo(pa.get(i+1)) >= 0) {
298			throw new Error("Unsorted at " + i + ": " + pa.get(i) + " / " + pa.get(i+1));
299			}
300			}
301			}
302	jsr166	1.2
303	dl	1.1	static final class RandomLongGenerator implements Ops.Generator<Long> {
304			public Long op() {
305			return new Long(ThreadLocalRandom.current().nextLong(maxValue));
306			}
307			}
308
309			static final RandomLongGenerator rlg = new RandomLongGenerator();
310			}