1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 */
22
23 /*
24 * This file is available under and governed by the GNU General Public
25 * License version 2 only, as published by the Free Software Foundation.
26 * However, the following notice accompanied the original version of this
27 * file:
28 *
29 * Written by Doug Lea with assistance from members of JCP JSR-166
30 * Expert Group and released to the public domain, as explained at
31 * http://creativecommons.org/publicdomain/zero/1.0/
32 */
33
34 /*
35 * @test
36 * @bug 4486658
37 * @summary Exercise multithreaded maps, by default ConcurrentHashMap.
38 * Multithreaded hash table test. Each thread does a random walk
39 * though elements of "key" array. On each iteration, it checks if
40 * table includes key. If absent, with probability pinsert it
41 * inserts it, and if present, with probability premove it removes
42 * it. (pinsert and premove are expressed as percentages to simplify
43 * parsing from command line.)
44 * @library /test/lib
45 * @run main/timeout=1600 MapLoops
46 */
47
48 /*
49 * @test
50 * @summary Exercise multithreaded maps, using only heavy monitors.
51 * @requires os.arch=="x86" | os.arch=="i386" | os.arch=="amd64" | os.arch=="x86_64" | os.arch=="aarch64" | os.arch == "ppc64" | os.arch == "ppc64le" | os.arch == "riscv64"
52 * @library /test/lib
53 * @run main/othervm/timeout=1600 -XX:+IgnoreUnrecognizedVMOptions -XX:+UseHeavyMonitors -XX:+VerifyHeavyMonitors MapLoops
54 */
55
56 import static java.util.concurrent.TimeUnit.MILLISECONDS;
57
58 import java.util.List;
59 import java.util.Map;
60 import java.util.SplittableRandom;
61 import java.util.concurrent.CopyOnWriteArrayList;
62 import java.util.concurrent.CyclicBarrier;
63 import java.util.concurrent.ExecutorService;
64 import java.util.concurrent.Executors;
65 import jdk.test.lib.Utils;
66
67 public class MapLoops {
68 static final long LONG_DELAY_MS = Utils.adjustTimeout(10_000);
69 static int nkeys = 1000; // 10_000
70 static int pinsert = 60;
71 static int premove = 2;
72 static int maxThreads = 100;
73 static int nops = 10000; // 100_000
74 static int removesPerMaxRandom;
75 static int insertsPerMaxRandom;
76
77 static final ExecutorService pool = Executors.newCachedThreadPool();
78
79 static final List<Throwable> throwables = new CopyOnWriteArrayList<>();
80
81 public static void main(String[] args) throws Exception {
82
83 Class mapClass = null;
84 if (args.length > 0) {
85 try {
86 mapClass = Class.forName(args[0]);
87 } catch (ClassNotFoundException e) {
88 throw new RuntimeException("Class " + args[0] + " not found.");
89 }
90 }
91 else
92 mapClass = java.util.concurrent.ConcurrentHashMap.class;
93
94 if (args.length > 1)
95 maxThreads = Integer.parseInt(args[1]);
96
97 if (args.length > 2)
98 nkeys = Integer.parseInt(args[2]);
99
100 if (args.length > 3)
101 pinsert = Integer.parseInt(args[3]);
102
103 if (args.length > 4)
104 premove = Integer.parseInt(args[4]);
105
106 if (args.length > 5)
107 nops = Integer.parseInt(args[5]);
108
109 // normalize probabilities wrt random number generator
110 removesPerMaxRandom = (int)((double)premove/100.0 * 0x7FFFFFFFL);
111 insertsPerMaxRandom = (int)((double)pinsert/100.0 * 0x7FFFFFFFL);
112
113 System.out.print("Class: " + mapClass.getName());
114 System.out.print(" threads: " + maxThreads);
115 System.out.print(" size: " + nkeys);
116 System.out.print(" ins: " + pinsert);
117 System.out.print(" rem: " + premove);
118 System.out.print(" ops: " + nops);
119 System.out.println();
120
121 int k = 1;
122 int warmups = 2;
123 for (int i = 1; i <= maxThreads;) {
124 test(i, nkeys, mapClass);
125 if (warmups > 0)
126 --warmups;
127 else if (i == k) {
128 k = i << 1;
129 i = i + (i >>> 1);
130 }
131 else if (i == 1 && k == 2) {
132 i = k;
133 warmups = 1;
134 }
135 else
136 i = k;
137 }
138 pool.shutdown();
139 if (! pool.awaitTermination(LONG_DELAY_MS, MILLISECONDS))
140 throw new Error();
141
142 if (! throwables.isEmpty())
143 throw new Error
144 (throwables.size() + " thread(s) terminated abruptly.");
145 }
146
147 static Integer[] makeKeys(int n) {
148 SplittableRandom rnd = new SplittableRandom();
149 Integer[] key = new Integer[n];
150 for (int i = 0; i < key.length; ++i)
151 key[i] = new Integer(rnd.nextInt());
152 return key;
153 }
154
155 static void shuffleKeys(Integer[] key) {
156 SplittableRandom rnd = new SplittableRandom();
157 for (int i = key.length; i > 1; --i) {
158 int j = rnd.nextInt(i);
159 Integer tmp = key[j];
160 key[j] = key[i-1];
161 key[i-1] = tmp;
162 }
163 }
164
165 static void test(int i, int nkeys, Class mapClass) throws Exception {
166 System.out.print("Threads: " + i + "\t:");
167 Map<Integer, Integer> map = (Map<Integer, Integer>)
168 mapClass.getDeclaredConstructor().newInstance();
169 Integer[] key = makeKeys(nkeys);
170 // Uncomment to start with a non-empty table
171 // for (int j = 0; j < nkeys; j += 4) // start 1/4 occupied
172 // map.put(key[j], key[j]);
173 LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
174 CyclicBarrier barrier = new CyclicBarrier(i+1, timer);
175 SplittableRandom rnd = new SplittableRandom();
176 for (int t = 0; t < i; ++t)
177 pool.execute(new Runner(map, key, barrier, rnd.split()));
178 barrier.await();
179 barrier.await();
180 long time = timer.getTime();
181 long tpo = time / (i * (long)nops);
182 System.out.print(LoopHelpers.rightJustify(tpo) + " ns per op");
183 double secs = (double)time / 1000000000.0;
184 System.out.println("\t " + secs + "s run time");
185 map.clear();
186 }
187
188 static class Runner implements Runnable {
189 final Map<Integer,Integer> map;
190 final Integer[] key;
191 final CyclicBarrier barrier;
192 final SplittableRandom rnd;
193 int position;
194 int total;
195
196 Runner(Map<Integer,Integer> map,
197 Integer[] key,
198 CyclicBarrier barrier,
199 SplittableRandom rnd) {
200 this.map = map;
201 this.key = key;
202 this.barrier = barrier;
203 this.rnd = rnd;
204 position = key.length / 2;
205 }
206
207 int step() {
208 // random-walk around key positions, bunching accesses
209 int r = rnd.nextInt(Integer.MAX_VALUE);
210 position += (r & 7) - 3;
211 while (position >= key.length) position -= key.length;
212 while (position < 0) position += key.length;
213
214 Integer k = key[position];
215 Integer x = map.get(k);
216
217 if (x != null) {
218 if (x.intValue() != k.intValue())
219 throw new Error("bad mapping: " + x + " to " + k);
220
221 if (r < removesPerMaxRandom) {
222 if (map.remove(k) != null) {
223 position = total % key.length; // move from position
224 return 2;
225 }
226 }
227 }
228 else if (r < insertsPerMaxRandom) {
229 ++position;
230 map.put(k, k);
231 return 2;
232 }
233
234 // Uncomment to add a little computation between accesses
235 // total += LoopHelpers.compute1(k.intValue());
236 total += r;
237 return 1;
238 }
239
240 public void run() {
241 try {
242 barrier.await();
243 int ops = nops;
244 while (ops > 0)
245 ops -= step();
246 barrier.await();
247 }
248 catch (Throwable throwable) {
249 synchronized (System.err) {
250 System.err.println("--------------------------------");
251 throwable.printStackTrace();
252 }
253 throwables.add(throwable);
254 }
255 }
256 }
257 }