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