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 import static java.util.concurrent.TimeUnit.MILLISECONDS; 49 50 import java.util.List; 51 import java.util.Map; 52 import java.util.SplittableRandom; 53 import java.util.concurrent.CopyOnWriteArrayList; 54 import java.util.concurrent.CyclicBarrier; 55 import java.util.concurrent.ExecutorService; 56 import java.util.concurrent.Executors; 57 import jdk.test.lib.Utils; 58 59 public class MapLoops { 60 static final long LONG_DELAY_MS = Utils.adjustTimeout(10_000); 61 static int nkeys = 1000; // 10_000 62 static int pinsert = 60; 63 static int premove = 2; 64 static int maxThreads = 100; 65 static int nops = 10000; // 100_000 66 static int removesPerMaxRandom; 67 static int insertsPerMaxRandom; 68 69 static final ExecutorService pool = Executors.newCachedThreadPool(); 70 71 static final List<Throwable> throwables = new CopyOnWriteArrayList<>(); 72 73 public static void main(String[] args) throws Exception { 74 75 Class mapClass = null; 76 if (args.length > 0) { 77 try { 78 mapClass = Class.forName(args[0]); 79 } catch (ClassNotFoundException e) { 80 throw new RuntimeException("Class " + args[0] + " not found."); 81 } 82 } 83 else 84 mapClass = java.util.concurrent.ConcurrentHashMap.class; 85 86 if (args.length > 1) 87 maxThreads = Integer.parseInt(args[1]); 88 89 if (args.length > 2) 90 nkeys = Integer.parseInt(args[2]); 91 92 if (args.length > 3) 93 pinsert = Integer.parseInt(args[3]); 94 95 if (args.length > 4) 96 premove = Integer.parseInt(args[4]); 97 98 if (args.length > 5) 99 nops = Integer.parseInt(args[5]); 100 101 // normalize probabilities wrt random number generator 102 removesPerMaxRandom = (int)(((double)premove/100.0 * 0x7FFFFFFFL)); 103 insertsPerMaxRandom = (int)(((double)pinsert/100.0 * 0x7FFFFFFFL)); 104 105 System.out.print("Class: " + mapClass.getName()); 106 System.out.print(" threads: " + maxThreads); 107 System.out.print(" size: " + nkeys); 108 System.out.print(" ins: " + pinsert); 109 System.out.print(" rem: " + premove); 110 System.out.print(" ops: " + nops); 111 System.out.println(); 112 113 int k = 1; 114 int warmups = 2; 115 for (int i = 1; i <= maxThreads;) { 116 test(i, nkeys, mapClass); 117 if (warmups > 0) 118 --warmups; 119 else if (i == k) { 120 k = i << 1; 121 i = i + (i >>> 1); 122 } 123 else if (i == 1 && k == 2) { 124 i = k; 125 warmups = 1; 126 } 127 else 128 i = k; 129 } 130 pool.shutdown(); 131 if (! pool.awaitTermination(LONG_DELAY_MS, MILLISECONDS)) 132 throw new Error(); 133 134 if (! throwables.isEmpty()) 135 throw new Error 136 (throwables.size() + " thread(s) terminated abruptly."); 137 } 138 139 static Integer[] makeKeys(int n) { 140 SplittableRandom rnd = new SplittableRandom(); 141 Integer[] key = new Integer[n]; 142 for (int i = 0; i < key.length; ++i) 143 key[i] = new Integer(rnd.nextInt()); 144 return key; 145 } 146 147 static void shuffleKeys(Integer[] key) { 148 SplittableRandom rnd = new SplittableRandom(); 149 for (int i = key.length; i > 1; --i) { 150 int j = rnd.nextInt(i); 151 Integer tmp = key[j]; 152 key[j] = key[i-1]; 153 key[i-1] = tmp; 154 } 155 } 156 157 static void test(int i, int nkeys, Class mapClass) throws Exception { 158 System.out.print("Threads: " + i + "\t:"); 159 Map<Integer, Integer> map = (Map<Integer, Integer>) 160 mapClass.getDeclaredConstructor().newInstance(); 161 Integer[] key = makeKeys(nkeys); 162 // Uncomment to start with a non-empty table 163 // for (int j = 0; j < nkeys; j += 4) // start 1/4 occupied 164 // map.put(key[j], key[j]); 165 LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); 166 CyclicBarrier barrier = new CyclicBarrier(i+1, timer); 167 SplittableRandom rnd = new SplittableRandom(); 168 for (int t = 0; t < i; ++t) 169 pool.execute(new Runner(map, key, barrier, rnd.split())); 170 barrier.await(); 171 barrier.await(); 172 long time = timer.getTime(); 173 long tpo = time / (i * (long)nops); 174 System.out.print(LoopHelpers.rightJustify(tpo) + " ns per op"); 175 double secs = (double)(time) / 1000000000.0; 176 System.out.println("\t " + secs + "s run time"); 177 map.clear(); 178 } 179 180 static class Runner implements Runnable { 181 final Map<Integer,Integer> map; 182 final Integer[] key; 183 final CyclicBarrier barrier; 184 final SplittableRandom rnd; 185 int position; 186 int total; 187 188 Runner(Map<Integer,Integer> map, 189 Integer[] key, 190 CyclicBarrier barrier, 191 SplittableRandom rnd) { 192 this.map = map; 193 this.key = key; 194 this.barrier = barrier; 195 this.rnd = rnd; 196 position = key.length / 2; 197 } 198 199 int step() { 200 // random-walk around key positions, bunching accesses 201 int r = rnd.nextInt(Integer.MAX_VALUE); 202 position += (r & 7) - 3; 203 while (position >= key.length) position -= key.length; 204 while (position < 0) position += key.length; 205 206 Integer k = key[position]; 207 Integer x = map.get(k); 208 209 if (x != null) { 210 if (x.intValue() != k.intValue()) 211 throw new Error("bad mapping: " + x + " to " + k); 212 213 if (r < removesPerMaxRandom) { 214 if (map.remove(k) != null) { 215 position = total % key.length; // move from position 216 return 2; 217 } 218 } 219 } 220 else if (r < insertsPerMaxRandom) { 221 ++position; 222 map.put(k, k); 223 return 2; 224 } 225 226 // Uncomment to add a little computation between accesses 227 // total += LoopHelpers.compute1(k.intValue()); 228 total += r; 229 return 1; 230 } 231 232 public void run() { 233 try { 234 barrier.await(); 235 int ops = nops; 236 while (ops > 0) 237 ops -= step(); 238 barrier.await(); 239 } 240 catch (Throwable throwable) { 241 synchronized (System.err) { 242 System.err.println("--------------------------------"); 243 throwable.printStackTrace(); 244 } 245 throwables.add(throwable); 246 } 247 } 248 } 249 }