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