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 }