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.*; |
8 |
import java.util.function.*; |
9 |
import java.util.concurrent.*; |
10 |
import java.util.concurrent.atomic.*; |
11 |
|
12 |
public class IntegerMax { |
13 |
static final int SIZE = 1000000; |
14 |
static final AtomicInteger checksum = new AtomicInteger(); |
15 |
static boolean print; |
16 |
static boolean allClasses = false; // true if also test dumb/default classes |
17 |
static final BinaryOperator<Integer> MAX = |
18 |
(Integer x, Integer y) -> x >= y ? x : y; |
19 |
|
20 |
public static void main(String[] args) throws Exception { |
21 |
if (args.length > 0) |
22 |
allClasses = true; |
23 |
print = false; |
24 |
System.out.println("warmup..."); |
25 |
allTests(10000, 100); |
26 |
System.out.println("..."); |
27 |
print = true; |
28 |
int step = 10; |
29 |
// int step = 100; |
30 |
for (int reps = 0; reps < 2; ++reps) { |
31 |
int trials = SIZE; |
32 |
for (int size = 1; size <= SIZE; size *= step) { |
33 |
allTests(size, trials); |
34 |
trials /= (step / 2); |
35 |
} |
36 |
} |
37 |
} |
38 |
|
39 |
static String sep() { return print ? "\n" : " "; } |
40 |
|
41 |
static void allTests(int size, int trials) throws Exception { |
42 |
System.out.println("---------------------------------------------"); |
43 |
System.out.println("size: " + size + " trials: " + trials); |
44 |
Integer[] keys = new Integer[size]; |
45 |
for (int i = 0; i < size; ++i) |
46 |
keys[i] = Integer.valueOf(i); |
47 |
Integer[] vals = Arrays.copyOf(keys, size); |
48 |
shuffle(keys); |
49 |
shuffle(vals); |
50 |
List<Integer> klist = Arrays.asList(keys); |
51 |
List<Integer> vlist = Arrays.asList(vals); |
52 |
int kmax = size - 1; |
53 |
int vmax = size - 1; |
54 |
|
55 |
isptest(klist, kmax, size, trials); |
56 |
System.out.print("Arrays.asList.keys" + sep()); |
57 |
isptest(vlist, vmax, size, trials); |
58 |
System.out.print("Arrays.asList.values" + sep()); |
59 |
|
60 |
ctest(new ArrayList<Integer>(), klist, kmax, size, trials); |
61 |
ctest(new ArrayList<Integer>(), vlist, vmax, size, trials); |
62 |
ctest(new Vector<Integer>(), klist, kmax, size, trials); |
63 |
ctest(new Vector<Integer>(), vlist, vmax, size, trials); |
64 |
ctest(new ArrayDeque<Integer>(), klist, kmax, size, trials); |
65 |
ctest(new ArrayDeque<Integer>(), vlist, vmax, size, trials); |
66 |
ctest(new CopyOnWriteArrayList<Integer>(), klist, kmax, size, trials); |
67 |
ctest(new CopyOnWriteArrayList<Integer>(), vlist, vmax, size, trials); |
68 |
ctest(new PriorityQueue<Integer>(), klist, kmax, size, trials); |
69 |
ctest(new PriorityQueue<Integer>(), vlist, vmax, size, trials); |
70 |
|
71 |
ctest(new HashSet<Integer>(), klist, kmax, size, trials); |
72 |
ctest(new HashSet<Integer>(), vlist, vmax, size, trials); |
73 |
ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, kmax, size, trials); |
74 |
ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vmax, size, trials); |
75 |
ctest(new TreeSet<Integer>(), klist, kmax, size, trials); |
76 |
ctest(new TreeSet<Integer>(), vlist, vmax, size, trials); |
77 |
ctest(new ConcurrentSkipListSet<Integer>(), klist, kmax, size, trials); |
78 |
ctest(new ConcurrentSkipListSet<Integer>(), vlist, vmax, size, trials); |
79 |
|
80 |
mtest(new HashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
81 |
mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
82 |
mtest(new WeakHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
83 |
mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
84 |
|
85 |
mtest(new TreeMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
86 |
mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
87 |
|
88 |
if (allClasses) { |
89 |
mtest(new Hashtable<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
90 |
mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials); |
91 |
ctest(new LinkedHashSet<Integer>(), klist, kmax, size, trials); |
92 |
ctest(new LinkedHashSet<Integer>(), vlist, vmax, size, trials); |
93 |
ctest(new LinkedList<Integer>(), klist, kmax, size, trials); |
94 |
ctest(new LinkedList<Integer>(), vlist, vmax, size, trials); |
95 |
// catest(new LinkedList<Integer>(), klist, kmax, size, trials); |
96 |
// catest(new LinkedList<Integer>(), vlist, vmax, size, trials); |
97 |
ctest(new ConcurrentLinkedQueue<Integer>(), klist, kmax, size, trials); |
98 |
ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vmax, size, trials); |
99 |
ctest(new ConcurrentLinkedDeque<Integer>(), klist, kmax, size, trials); |
100 |
ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vmax, size, trials); |
101 |
ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, kmax, size, trials); |
102 |
ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials); |
103 |
ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, kmax, size, trials); |
104 |
ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vmax, size, trials); |
105 |
ctest(new LinkedTransferQueue<Integer>(), klist, kmax, size, trials); |
106 |
ctest(new LinkedTransferQueue<Integer>(), vlist, vmax, size, trials); |
107 |
ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, kmax, size, trials); |
108 |
ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials); |
109 |
ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, kmax, size, trials); |
110 |
ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials); |
111 |
} |
112 |
|
113 |
if (checksum.get() != 0) throw new Error("bad computation"); |
114 |
} |
115 |
|
116 |
static void ctest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials) |
117 |
throws Exception { |
118 |
String cn = c.getClass().getName(); |
119 |
if (cn.startsWith("java.util.concurrent.")) |
120 |
cn = cn.substring(21); |
121 |
else if (cn.startsWith("java.util.")) |
122 |
cn = cn.substring(10); |
123 |
c.addAll(klist); |
124 |
isptest(c, kmax, size, trials); |
125 |
System.out.print(cn + sep()); |
126 |
} |
127 |
|
128 |
static void catest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials) |
129 |
throws Exception { |
130 |
String cn = c.getClass().getName(); |
131 |
if (cn.startsWith("java.util.concurrent.")) |
132 |
cn = cn.substring(21); |
133 |
else if (cn.startsWith("java.util.")) |
134 |
cn = cn.substring(10); |
135 |
cn = cn + ".toArrayList"; |
136 |
c.addAll(klist); |
137 |
ArrayList<Integer> ac = new ArrayList<Integer>(c); |
138 |
isptest(ac, kmax, size, trials); |
139 |
System.out.print(cn + sep()); |
140 |
} |
141 |
|
142 |
static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int kmax, int vmax, int size, int trials) throws Exception { |
143 |
String cn = m.getClass().getName(); |
144 |
if (cn.startsWith("java.util.concurrent.")) |
145 |
cn = cn.substring(21); |
146 |
else if (cn.startsWith("java.util.")) |
147 |
cn = cn.substring(10); |
148 |
for (int i = 0; i < size; ++i) |
149 |
m.put(keys[i], vals[i]); |
150 |
isptest(m.keySet(), kmax, size, trials); |
151 |
System.out.print(cn + ".keys" + sep()); |
152 |
isptest(m.values(), vmax, size, trials); |
153 |
System.out.print(cn + ".vals" + sep()); |
154 |
} |
155 |
|
156 |
static void isptest(Collection<Integer> c, int max, int size, int trials) throws Exception { |
157 |
long ti = itest(c, max, trials); |
158 |
long ts = stest(c, max, trials); |
159 |
long tp = ptest(c, max, trials); |
160 |
if (checksum.get() != 0) throw new Error("bad computation"); |
161 |
if (print) { |
162 |
long scale = (long)size * trials; |
163 |
double di = ((double)ti) / scale; |
164 |
double ds = ((double)ts) / scale; |
165 |
double dp = ((double)tp) / scale; |
166 |
System.out.printf("n:%7d ", size); |
167 |
System.out.printf("i:%8.2f ", di); |
168 |
System.out.printf("s:%8.2f ", ds); |
169 |
System.out.printf("p:%8.2f ", dp); |
170 |
} |
171 |
} |
172 |
|
173 |
static long itest(Collection<Integer> c, int max, int trials) throws Exception { |
174 |
if (c == null) throw new Error(); |
175 |
Thread.sleep(250); |
176 |
long tlast = System.nanoTime(); |
177 |
for (int i = 0; i < trials; ++i) { |
178 |
Integer pmax = Integer.valueOf(Integer.MIN_VALUE - checksum.get()); |
179 |
for (Integer x : c) |
180 |
pmax = MAX.apply(pmax, x); |
181 |
checksum.getAndAdd(max - pmax); |
182 |
} |
183 |
return System.nanoTime() - tlast; |
184 |
} |
185 |
|
186 |
static long stest(Collection<Integer> c, int max, int trials) throws Exception { |
187 |
if (c == null) throw new Error(); |
188 |
Thread.sleep(250); |
189 |
long tlast = System.nanoTime(); |
190 |
for (int i = 0; i < trials; ++i) { |
191 |
int pmax = c.stream().reduce |
192 |
(Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX); |
193 |
checksum.getAndAdd(max - pmax); |
194 |
} |
195 |
return System.nanoTime() - tlast; |
196 |
} |
197 |
|
198 |
static long ptest(Collection<Integer> c, int max, int trials) throws Exception { |
199 |
if (c == null) throw new Error(); |
200 |
Thread.sleep(250); |
201 |
long tlast = System.nanoTime(); |
202 |
for (int i = 0; i < trials; ++i) { |
203 |
int pmax = c.parallelStream().reduce |
204 |
(Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX); |
205 |
checksum.getAndAdd(max - pmax); |
206 |
} |
207 |
return System.nanoTime() - tlast; |
208 |
} |
209 |
|
210 |
// misc |
211 |
|
212 |
static final long NPS = (1000L * 1000 * 1000); |
213 |
static double elapsedTime(long startTime) { |
214 |
return (double)(System.nanoTime() - startTime) / NPS; |
215 |
} |
216 |
|
217 |
static void shuffle(Object[] a) { |
218 |
ThreadLocalRandom rng = ThreadLocalRandom.current(); |
219 |
for (int i = a.length; i > 1; i--) { |
220 |
Object t = a[i-1]; |
221 |
int r = rng.nextInt(i); |
222 |
a[i-1] = a[r]; |
223 |
a[r] = t; |
224 |
} |
225 |
} |
226 |
|
227 |
} |