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/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 |
jsr166 |
1.2 |
static String sep() { return print ? "\n" : " "; } |
40 |
dl |
1.1 |
|
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 |
dl |
1.3 |
ctest(new ConcurrentSkipListSet<Integer>(), klist, ksum, size, trials); |
78 |
|
|
ctest(new ConcurrentSkipListSet<Integer>(), vlist, vsum, size, trials); |
79 |
dl |
1.1 |
|
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 |
dl |
1.3 |
if (checksum.get() != 0) throw new Error("bad computation"); |
112 |
dl |
1.1 |
} |
113 |
|
|
|
114 |
jsr166 |
1.2 |
static void ctest(Collection<Integer> c, List<Integer> klist, int ksum, int size, int trials) |
115 |
dl |
1.1 |
throws Exception { |
116 |
|
|
String cn = c.getClass().getName(); |
117 |
|
|
if (cn.startsWith("java.util.concurrent.")) |
118 |
|
|
cn = cn.substring(21); |
119 |
|
|
else if (cn.startsWith("java.util.")) |
120 |
|
|
cn = cn.substring(10); |
121 |
|
|
c.addAll(klist); |
122 |
|
|
isptest(c, ksum, size, trials); |
123 |
|
|
System.out.print(cn + sep()); |
124 |
|
|
} |
125 |
|
|
|
126 |
|
|
static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int ksum, int vsum, int size, int trials) throws Exception { |
127 |
|
|
String cn = m.getClass().getName(); |
128 |
|
|
if (cn.startsWith("java.util.concurrent.")) |
129 |
|
|
cn = cn.substring(21); |
130 |
|
|
else if (cn.startsWith("java.util.")) |
131 |
|
|
cn = cn.substring(10); |
132 |
|
|
for (int i = 0; i < size; ++i) |
133 |
|
|
m.put(keys[i], vals[i]); |
134 |
|
|
isptest(m.keySet(), ksum, size, trials); |
135 |
|
|
System.out.print(cn + ".keys" + sep()); |
136 |
|
|
isptest(m.values(), vsum, size, trials); |
137 |
|
|
System.out.print(cn + ".vals" + sep()); |
138 |
|
|
} |
139 |
|
|
|
140 |
|
|
static void isptest(Collection<Integer> c, int sum, int size, int trials) throws Exception { |
141 |
|
|
long ti = itest(c, sum, trials); |
142 |
|
|
long ts = stest(c, sum, trials); |
143 |
|
|
long tp = ptest(c, sum, trials); |
144 |
dl |
1.3 |
if (checksum.get() != 0) throw new Error("bad computation"); |
145 |
dl |
1.1 |
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 |
jsr166 |
1.4 |
long tlast = System.nanoTime(); |
161 |
dl |
1.1 |
for (int i = 0; i < trials; ++i) { |
162 |
|
|
Integer psum = Integer.valueOf(checksum.get()); |
163 |
jsr166 |
1.2 |
for (Integer x : c) |
164 |
dl |
1.1 |
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 |
jsr166 |
1.4 |
long tlast = System.nanoTime(); |
174 |
dl |
1.1 |
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 |
jsr166 |
1.4 |
long tlast = System.nanoTime(); |
186 |
dl |
1.1 |
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 |
|
|
} |