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 */ 46 47 import static java.util.concurrent.TimeUnit.MILLISECONDS; 48 49 import java.util.Map; 50 import java.util.SplittableRandom; 51 import java.util.concurrent.CyclicBarrier; 52 import java.util.concurrent.ExecutorService; 53 import java.util.concurrent.Executors; 54 import jdk.test.lib.Utils; 55 56 public class MapLoops { 57 static final long LONG_DELAY_MS = Utils.adjustTimeout(10_000); 58 static final int NKEYS = 100000; 59 static int pinsert = 60; 60 static int premove = 2; 61 static int maxThreads = 5; 62 static int nops = 10000; // 1000000 63 static int removesPerMaxRandom; 64 static int insertsPerMaxRandom; 65 66 static final ExecutorService pool = Executors.newCachedThreadPool(); 67 68 public static void main(String[] args) throws Exception { 69 70 Class mapClass = null; 71 if (args.length > 0) { 72 try { 73 mapClass = Class.forName(args[0]); 74 } catch (ClassNotFoundException e) { 75 throw new RuntimeException("Class " + args[0] + " not found."); 76 } 77 } 78 else 79 mapClass = RWMap.class; 80 81 if (args.length > 1) 82 maxThreads = Integer.parseInt(args[1]); 83 84 if (args.length > 2) 85 nops = Integer.parseInt(args[2]); 86 87 if (args.length > 3) 88 pinsert = Integer.parseInt(args[3]); 89 90 if (args.length > 4) 91 premove = Integer.parseInt(args[4]); 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.println("Using " + mapClass.getName()); 98 99 SplittableRandom rnd = new SplittableRandom(); 100 Integer[] key = new Integer[NKEYS]; 101 for (int i = 0; i < key.length; ++i) 102 key[i] = new Integer(rnd.nextInt()); 103 104 // warmup 105 System.out.println("Warmup..."); 106 for (int k = 0; k < 2; ++k) { 107 Map<Integer, Integer> map = (Map<Integer, Integer>) 108 mapClass.getDeclaredConstructor().newInstance(); 109 LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); 110 CyclicBarrier barrier = new CyclicBarrier(1, timer); 111 new Runner(map, key, barrier, rnd.split()).run(); 112 map.clear(); 113 } 114 115 for (int i = 1; i <= maxThreads; i += (i+1) >>> 1) { 116 System.out.print("Threads: " + i + "\t:"); 117 Map<Integer, Integer> map = (Map<Integer, Integer>) 118 mapClass.getDeclaredConstructor().newInstance(); 119 LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); 120 CyclicBarrier barrier = new CyclicBarrier(i+1, timer); 121 for (int k = 0; k < i; ++k) 122 pool.execute(new Runner(map, key, barrier, rnd.split())); 123 barrier.await(); 124 barrier.await(); 125 long time = timer.getTime(); 126 long tpo = time / (i * (long)nops); 127 System.out.print(LoopHelpers.rightJustify(tpo) + " ns per op"); 128 double secs = (double)(time) / 1000000000.0; 129 System.out.println("\t " + secs + "s run time"); 130 map.clear(); 131 } 132 pool.shutdown(); 133 if (! pool.awaitTermination(LONG_DELAY_MS, MILLISECONDS)) 134 throw new Error(); 135 } 136 137 static class Runner implements Runnable { 138 final Map<Integer,Integer> map; 139 final Integer[] key; 140 final CyclicBarrier barrier; 141 final SplittableRandom rnd; 142 int position; 143 int total; 144 145 Runner(Map<Integer,Integer> map, 146 Integer[] key, 147 CyclicBarrier barrier, 148 SplittableRandom rnd) { 149 this.map = map; 150 this.key = key; 151 this.barrier = barrier; 152 this.rnd = rnd; 153 position = key.length / 2; 154 } 155 156 int step() { 157 // random-walk around key positions, bunching accesses 158 int r = rnd.nextInt(Integer.MAX_VALUE); 159 position += (r & 7) - 3; 160 while (position >= key.length) position -= key.length; 161 while (position < 0) position += key.length; 162 163 Integer k = key[position]; 164 Integer x = map.get(k); 165 166 if (x != null) { 167 if (x.intValue() != k.intValue()) 168 throw new Error("bad mapping: " + x + " to " + k); 169 170 if (r < removesPerMaxRandom) { 171 // get away from this position 172 position = r % key.length; 173 map.remove(k); 174 return 2; 175 } 176 else 177 total += LoopHelpers.compute2(LoopHelpers.compute1(x.intValue())); 178 } 179 else { 180 if (r < insertsPerMaxRandom) { 181 map.put(k, k); 182 return 2; 183 } 184 } 185 return 1; 186 } 187 188 public void run() { 189 try { 190 barrier.await(); 191 int ops = nops; 192 while (ops > 0) 193 ops -= step(); 194 barrier.await(); 195 } 196 catch (Exception ex) { 197 ex.printStackTrace(); 198 } 199 } 200 } 201 }