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 IntegerSum { |
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 |
|
18 |
static final BinaryOperator<Integer> SUM = (Integer x, Integer 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 |
int ksum = 0; |
46 |
for (int i = 0; i < size; ++i) { |
47 |
ksum += i; |
48 |
keys[i] = Integer.valueOf(i); |
49 |
} |
50 |
int vsum = ksum; |
51 |
Integer[] vals = Arrays.copyOf(keys, size); |
52 |
shuffle(vals); |
53 |
List<Integer> klist = Arrays.asList(keys); |
54 |
List<Integer> vlist = Arrays.asList(vals); |
55 |
|
56 |
isptest(klist, ksum, size, trials); |
57 |
System.out.print("Arrays.asList.keys" + sep()); |
58 |
isptest(vlist, vsum, size, trials); |
59 |
System.out.print("Arrays.asList.values" + sep()); |
60 |
|
61 |
ctest(new ArrayList<Integer>(), klist, ksum, size, trials); |
62 |
ctest(new ArrayList<Integer>(), vlist, vsum, size, trials); |
63 |
ctest(new Vector<Integer>(), klist, ksum, size, trials); |
64 |
ctest(new Vector<Integer>(), vlist, vsum, size, trials); |
65 |
ctest(new ArrayDeque<Integer>(), klist, ksum, size, trials); |
66 |
ctest(new ArrayDeque<Integer>(), vlist, vsum, size, trials); |
67 |
ctest(new CopyOnWriteArrayList<Integer>(), klist, ksum, size, trials); |
68 |
ctest(new CopyOnWriteArrayList<Integer>(), vlist, vsum, size, trials); |
69 |
ctest(new PriorityQueue<Integer>(), klist, ksum, size, trials); |
70 |
ctest(new PriorityQueue<Integer>(), vlist, vsum, size, trials); |
71 |
ctest(new HashSet<Integer>(), klist, ksum, size, trials); |
72 |
ctest(new HashSet<Integer>(), vlist, vsum, size, trials); |
73 |
ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, ksum, size, trials); |
74 |
ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vsum, size, trials); |
75 |
ctest(new TreeSet<Integer>(), klist, ksum, size, trials); |
76 |
ctest(new TreeSet<Integer>(), vlist, vsum, size, trials); |
77 |
ctest(ConcurrentSkipListMap.<Integer>newKeySet(), klist, ksum, size, trials); |
78 |
ctest(ConcurrentSkipListMap.<Integer>newKeySet(), vlist, vsum, size, trials); |
79 |
|
80 |
mtest(new HashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
81 |
mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
82 |
mtest(new WeakHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
83 |
mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
84 |
|
85 |
mtest(new TreeMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
86 |
mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
87 |
|
88 |
if (allClasses) { |
89 |
mtest(new Hashtable<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
90 |
mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials); |
91 |
ctest(new LinkedHashSet<Integer>(), klist, ksum, size, trials); |
92 |
ctest(new LinkedHashSet<Integer>(), vlist, vsum, size, trials); |
93 |
ctest(new LinkedList<Integer>(), klist, ksum, size, trials); |
94 |
ctest(new LinkedList<Integer>(), vlist, vsum, size, trials); |
95 |
ctest(new ConcurrentLinkedQueue<Integer>(), klist, ksum, size, trials); |
96 |
ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vsum, size, trials); |
97 |
ctest(new ConcurrentLinkedDeque<Integer>(), klist, ksum, size, trials); |
98 |
ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vsum, size, trials); |
99 |
ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, ksum, size, trials); |
100 |
ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials); |
101 |
ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, ksum, size, trials); |
102 |
ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vsum, size, trials); |
103 |
ctest(new LinkedTransferQueue<Integer>(), klist, ksum, size, trials); |
104 |
ctest(new LinkedTransferQueue<Integer>(), vlist, vsum, size, trials); |
105 |
ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, ksum, size, trials); |
106 |
ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials); |
107 |
ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, ksum, size, trials); |
108 |
ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials); |
109 |
} |
110 |
|
111 |
if (checksum.get() != 0) |
112 |
throw new Error("bad computation"); |
113 |
} |
114 |
|
115 |
static void ctest(Collection<Integer> c, List<Integer> klist, int ksum, int size, int trials) |
116 |
throws Exception { |
117 |
String cn = c.getClass().getName(); |
118 |
if (cn.startsWith("java.util.concurrent.")) |
119 |
cn = cn.substring(21); |
120 |
else if (cn.startsWith("java.util.")) |
121 |
cn = cn.substring(10); |
122 |
c.addAll(klist); |
123 |
isptest(c, ksum, size, trials); |
124 |
System.out.print(cn + sep()); |
125 |
} |
126 |
|
127 |
static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int ksum, int vsum, int size, int trials) throws Exception { |
128 |
String cn = m.getClass().getName(); |
129 |
if (cn.startsWith("java.util.concurrent.")) |
130 |
cn = cn.substring(21); |
131 |
else if (cn.startsWith("java.util.")) |
132 |
cn = cn.substring(10); |
133 |
for (int i = 0; i < size; ++i) |
134 |
m.put(keys[i], vals[i]); |
135 |
isptest(m.keySet(), ksum, size, trials); |
136 |
System.out.print(cn + ".keys" + sep()); |
137 |
isptest(m.values(), vsum, size, trials); |
138 |
System.out.print(cn + ".vals" + sep()); |
139 |
} |
140 |
|
141 |
static void isptest(Collection<Integer> c, int sum, int size, int trials) throws Exception { |
142 |
long ti = itest(c, sum, trials); |
143 |
long ts = stest(c, sum, trials); |
144 |
long tp = ptest(c, sum, trials); |
145 |
if (print) { |
146 |
long scale = (long)size * trials; |
147 |
double di = ((double)ti) / scale; |
148 |
double ds = ((double)ts) / scale; |
149 |
double dp = ((double)tp) / scale; |
150 |
System.out.printf("n:%7d ", size); |
151 |
System.out.printf("i:%8.2f ", di); |
152 |
System.out.printf("s:%8.2f ", ds); |
153 |
System.out.printf("p:%8.2f ", dp); |
154 |
} |
155 |
} |
156 |
|
157 |
static long itest(Collection<Integer> c, int sum, int trials) throws Exception { |
158 |
if (c == null) throw new Error(); |
159 |
Thread.sleep(250); |
160 |
long tlast = System.nanoTime(); |
161 |
for (int i = 0; i < trials; ++i) { |
162 |
Integer psum = Integer.valueOf(checksum.get()); |
163 |
for (Integer x : c) |
164 |
psum = SUM.apply(psum, x); |
165 |
checksum.getAndAdd(sum - psum); |
166 |
} |
167 |
return System.nanoTime() - tlast; |
168 |
} |
169 |
|
170 |
static long stest(Collection<Integer> c, int sum, int trials) throws Exception { |
171 |
if (c == null) throw new Error(); |
172 |
Thread.sleep(250); |
173 |
long tlast = System.nanoTime(); |
174 |
for (int i = 0; i < trials; ++i) { |
175 |
int psum = c.stream().reduce |
176 |
(Integer.valueOf(checksum.get()), SUM); |
177 |
checksum.getAndAdd(sum - psum); |
178 |
} |
179 |
return System.nanoTime() - tlast; |
180 |
} |
181 |
|
182 |
static long ptest(Collection<Integer> c, int sum, int trials) throws Exception { |
183 |
if (c == null) throw new Error(); |
184 |
Thread.sleep(250); |
185 |
long tlast = System.nanoTime(); |
186 |
for (int i = 0; i < trials; ++i) { |
187 |
int psum = c.parallelStream().reduce |
188 |
(Integer.valueOf(checksum.get()), SUM); |
189 |
checksum.getAndAdd(sum - psum); |
190 |
} |
191 |
return System.nanoTime() - tlast; |
192 |
} |
193 |
|
194 |
// misc |
195 |
|
196 |
static final long NPS = (1000L * 1000 * 1000); |
197 |
static double elapsedTime(long startTime) { |
198 |
return (double)(System.nanoTime() - startTime) / NPS; |
199 |
} |
200 |
|
201 |
static void shuffle(Object[] a) { |
202 |
ThreadLocalRandom rng = ThreadLocalRandom.current(); |
203 |
for (int i = a.length; i > 1; i--) { |
204 |
Object t = a[i-1]; |
205 |
int r = rng.nextInt(i); |
206 |
a[i-1] = a[r]; |
207 |
a[r] = t; |
208 |
} |
209 |
} |
210 |
|
211 |
} |