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