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 }