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 jsr166y.*; |
8 |
import extra166y.*; |
9 |
import java.util.*; |
10 |
import java.util.concurrent.*; |
11 |
|
12 |
|
13 |
public class FindAnyDemo { |
14 |
static final int NCPU = Runtime.getRuntime().availableProcessors(); |
15 |
|
16 |
/** |
17 |
* Sequential version, for performance comparison |
18 |
*/ |
19 |
static<T> int seqIndexOf(T[] array, |
20 |
Ops.Predicate<T> pred) { |
21 |
int n = array.length; |
22 |
for (int i = 0; i < n; ++i) { |
23 |
T x = array[i]; |
24 |
if (pred.op(x)) |
25 |
return i; |
26 |
} |
27 |
return -1; |
28 |
} |
29 |
|
30 |
/** |
31 |
* Slow/dumb prime check |
32 |
*/ |
33 |
static class IsPrime implements Ops.Predicate<Rand> { |
34 |
public boolean op(Rand r) { |
35 |
long n = r.seed; |
36 |
int bound = (int)(Math.sqrt(n)); |
37 |
if (bound >= 3) { |
38 |
for (int i = 3; i <= bound; ++i) |
39 |
if ((n & 1) == 0 || n % i == 0) |
40 |
return false; |
41 |
} |
42 |
return true; |
43 |
} |
44 |
} |
45 |
|
46 |
/** for time conversion */ |
47 |
static final long NPS = (1000L * 1000 * 1000); |
48 |
|
49 |
static class NextRand implements Ops.Procedure<Rand> { |
50 |
public void op(Rand r) { |
51 |
r.next(); |
52 |
} |
53 |
} |
54 |
|
55 |
public static void main(String[] args) throws Exception { |
56 |
int n = 1 << 20; |
57 |
ArrayList<Rand> list = new ArrayList<Rand>(n); |
58 |
long rs = 256203225; |
59 |
for (int i = 0; i < n >>> 1; ++i) |
60 |
list.add(new Rand(rs+=3)); |
61 |
list.add(new Rand(256203221)); |
62 |
for (int i = n >>> 1; i < n >>> 1; ++i) |
63 |
list.add(new Rand(rs+=3)); |
64 |
Rand[] array = list.toArray(new Rand[0]); |
65 |
final IsPrime pred = new IsPrime(); |
66 |
long last, now; |
67 |
double elapsed; |
68 |
boolean present = false; |
69 |
for (int k = 0; k < 2; ++k) { |
70 |
last = System.nanoTime(); |
71 |
for (int reps = 0; reps < 9; ++reps) { |
72 |
int result = seqIndexOf(array, pred); |
73 |
if (k == 0 && reps == 0) |
74 |
present = result != -1; |
75 |
else if (present != (result != -1)) |
76 |
throw new Error("Inconsistent result"); |
77 |
} |
78 |
now = System.nanoTime(); |
79 |
elapsed = (double)(now - last) / NPS; |
80 |
last = now; |
81 |
System.out.printf("seq: %7.3f\n", elapsed); |
82 |
} |
83 |
Thread.sleep(100); |
84 |
ForkJoinPool fjp = new ForkJoinPool(); |
85 |
ParallelArray<Rand> pa = ParallelArray.createUsingHandoff(array, fjp); |
86 |
for (int i = 1; i <= NCPU; i <<= 1) { |
87 |
last = System.nanoTime(); |
88 |
for (int k = 0; k < 2; ++k) { |
89 |
for (int reps = 0; reps < 9; ++reps) { |
90 |
int result = pa.withFilter(pred).anyIndex(); |
91 |
if (present != (result != -1)) |
92 |
throw new Error("Inconsistent result"); |
93 |
} |
94 |
now = System.nanoTime(); |
95 |
elapsed = (double)(now - last) / NPS; |
96 |
last = now; |
97 |
System.out.printf("ps %2d: %7.3f\n", i, elapsed); |
98 |
} |
99 |
} |
100 |
fjp.shutdownNow(); |
101 |
fjp.awaitTermination(1, TimeUnit.SECONDS); |
102 |
} |
103 |
|
104 |
/** |
105 |
* Unsynchronized version of java.util.Random algorithm. |
106 |
*/ |
107 |
static final class Rand { |
108 |
private static final long multiplier = 0x5DEECE66DL; |
109 |
private static final long addend = 0xBL; |
110 |
private static final long mask = (1L << 48) - 1; |
111 |
private long seed; |
112 |
|
113 |
Rand(long s) { |
114 |
seed = s; |
115 |
// next(); |
116 |
// next(); |
117 |
} |
118 |
public int next() { |
119 |
long nextseed = (seed * multiplier + addend) & mask; |
120 |
seed = nextseed; |
121 |
return ((int)(nextseed >>> 17)) & 0x7FFFFFFF; |
122 |
} |
123 |
|
124 |
public String toString() { |
125 |
return String.valueOf(seed); |
126 |
} |
127 |
} |
128 |
|
129 |
} |