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 * @run main/timeout=240 MapCheck 38 * @summary Times and checks basic map operations 39 */ 40 41import java.io.Serializable; 42import java.io.BufferedInputStream; 43import java.io.BufferedOutputStream; 44import java.io.FileInputStream; 45import java.io.FileOutputStream; 46import java.io.ObjectInputStream; 47import java.io.ObjectOutputStream; 48import java.util.Enumeration; 49import java.util.Hashtable; 50import java.util.IdentityHashMap; 51import java.util.Iterator; 52import java.util.Map; 53import java.util.Set; 54import java.util.concurrent.ThreadLocalRandom; 55 56public class MapCheck { 57 58 static final int absentSize = 1 << 17; 59 static final int absentMask = absentSize - 1; 60 static Object[] absent = new Object[absentSize]; 61 62 static final Object MISSING = new Object(); 63 64 static TestTimer timer = new TestTimer(); 65 66 static void reallyAssert(boolean b) { 67 if (!b) throw new Error("Failed Assertion"); 68 } 69 70 public static void main(String[] args) throws Exception { 71 Class mapClass = java.util.concurrent.ConcurrentHashMap.class; 72 int numTests = 8; 73 int size = 50000; 74 75 if (args.length > 0) { 76 try { 77 mapClass = Class.forName(args[0]); 78 } catch (ClassNotFoundException e) { 79 throw new RuntimeException("Class " + args[0] + " not found."); 80 } 81 } 82 83 if (args.length > 1) 84 numTests = Integer.parseInt(args[1]); 85 86 if (args.length > 2) 87 size = Integer.parseInt(args[2]); 88 89 boolean doSerializeTest = args.length > 3; 90 91 System.out.println("Testing " + mapClass.getName() + " trials: " + numTests + " size: " + size); 92 93 for (int i = 0; i < absentSize; ++i) absent[i] = new Object(); 94 95 Object[] key = new Object[size]; 96 for (int i = 0; i < size; ++i) key[i] = new Object(); 97 98 forceMem(size * 8); 99 100 for (int rep = 0; rep < numTests; ++rep) { 101 runTest(newMap(mapClass), key); 102 } 103 104 TestTimer.printStats(); 105 106 if (doSerializeTest) 107 stest(newMap(mapClass), size); 108 } 109 110 static Map newMap(Class cl) { 111 try { 112 Map m = (Map)cl.newInstance(); 113 return m; 114 } catch (Exception e) { 115 throw new RuntimeException("Can't instantiate " + cl + ": " + e); 116 } 117 } 118 119 120 static void runTest(Map s, Object[] key) { 121 shuffle(key); 122 int size = key.length; 123 long startTime = System.currentTimeMillis(); 124 test(s, key); 125 long time = System.currentTimeMillis() - startTime; 126 } 127 128 static void forceMem(int n) { 129 // force enough memory 130 Long[] junk = new Long[n]; 131 for (int i = 0; i < junk.length; ++i) junk[i] = new Long(i); 132 int sum = 0; 133 for (int i = 0; i < junk.length; ++i) 134 sum += (int)(junk[i].longValue() + i); 135 if (sum == 0) System.out.println("Useless number = " + sum); 136 junk = null; 137 // System.gc(); 138 } 139 140 141 static void t1(String nm, int n, Map s, Object[] key, int expect) { 142 int sum = 0; 143 int iters = 4; 144 timer.start(nm, n * iters); 145 for (int j = 0; j < iters; ++j) { 146 for (int i = 0; i < n; i++) { 147 if (s.get(key[i]) != null) ++sum; 148 } 149 } 150 timer.finish(); 151 reallyAssert(sum == expect * iters); 152 } 153 154 static void t2(String nm, int n, Map s, Object[] key, int expect) { 155 int sum = 0; 156 timer.start(nm, n); 157 for (int i = 0; i < n; i++) { 158 if (s.remove(key[i]) != null) ++sum; 159 } 160 timer.finish(); 161 reallyAssert(sum == expect); 162 } 163 164 static void t3(String nm, int n, Map s, Object[] key, int expect) { 165 int sum = 0; 166 timer.start(nm, n); 167 for (int i = 0; i < n; i++) { 168 if (s.put(key[i], absent[i & absentMask]) == null) ++sum; 169 } 170 timer.finish(); 171 reallyAssert(sum == expect); 172 } 173 174 static void t4(String nm, int n, Map s, Object[] key, int expect) { 175 int sum = 0; 176 timer.start(nm, n); 177 for (int i = 0; i < n; i++) { 178 if (s.containsKey(key[i])) ++sum; 179 } 180 timer.finish(); 181 reallyAssert(sum == expect); 182 } 183 184 static void t5(String nm, int n, Map s, Object[] key, int expect) { 185 int sum = 0; 186 timer.start(nm, n/2); 187 for (int i = n-2; i >= 0; i-=2) { 188 if (s.remove(key[i]) != null) ++sum; 189 } 190 timer.finish(); 191 reallyAssert(sum == expect); 192 } 193 194 static void t6(String nm, int n, Map s, Object[] k1, Object[] k2) { 195 int sum = 0; 196 timer.start(nm, n * 2); 197 for (int i = 0; i < n; i++) { 198 if (s.get(k1[i]) != null) ++sum; 199 if (s.get(k2[i & absentMask]) != null) ++sum; 200 } 201 timer.finish(); 202 reallyAssert(sum == n); 203 } 204 205 static void t7(String nm, int n, Map s, Object[] k1, Object[] k2) { 206 int sum = 0; 207 timer.start(nm, n * 2); 208 for (int i = 0; i < n; i++) { 209 if (s.containsKey(k1[i])) ++sum; 210 if (s.containsKey(k2[i & absentMask])) ++sum; 211 } 212 timer.finish(); 213 reallyAssert(sum == n); 214 } 215 216 static void t8(String nm, int n, Map s, Object[] key, int expect) { 217 int sum = 0; 218 timer.start(nm, n); 219 for (int i = 0; i < n; i++) { 220 if (s.get(key[i]) != null) ++sum; 221 } 222 timer.finish(); 223 reallyAssert(sum == expect); 224 } 225 226 227 static void t9(Map s) { 228 int sum = 0; 229 int iters = 20; 230 timer.start("ContainsValue (/n) ", iters * s.size()); 231 int step = absentSize / iters; 232 for (int i = 0; i < absentSize; i += step) 233 if (s.containsValue(absent[i])) ++sum; 234 timer.finish(); 235 reallyAssert(sum != 0); 236 } 237 238 239 static void ktest(Map s, int size, Object[] key) { 240 timer.start("ContainsKey ", size); 241 Set ks = s.keySet(); 242 int sum = 0; 243 for (int i = 0; i < size; i++) { 244 if (ks.contains(key[i])) ++sum; 245 } 246 timer.finish(); 247 reallyAssert(sum == size); 248 } 249 250 251 static void ittest1(Map s, int size) { 252 int sum = 0; 253 timer.start("Iter Key ", size); 254 for (Iterator it = s.keySet().iterator(); it.hasNext(); ) { 255 if (it.next() != MISSING) 256 ++sum; 257 } 258 timer.finish(); 259 reallyAssert(sum == size); 260 } 261 262 static void ittest2(Map s, int size) { 263 int sum = 0; 264 timer.start("Iter Value ", size); 265 for (Iterator it = s.values().iterator(); it.hasNext(); ) { 266 if (it.next() != MISSING) 267 ++sum; 268 } 269 timer.finish(); 270 reallyAssert(sum == size); 271 } 272 static void ittest3(Map s, int size) { 273 int sum = 0; 274 timer.start("Iter Entry ", size); 275 for (Iterator it = s.entrySet().iterator(); it.hasNext(); ) { 276 if (it.next() != MISSING) 277 ++sum; 278 } 279 timer.finish(); 280 reallyAssert(sum == size); 281 } 282 283 static void ittest4(Map s, int size, int pos) { 284 IdentityHashMap seen = new IdentityHashMap(size); 285 reallyAssert(s.size() == size); 286 int sum = 0; 287 timer.start("Iter XEntry ", size); 288 Iterator it = s.entrySet().iterator(); 289 Object k = null; 290 Object v = null; 291 for (int i = 0; i < size-pos; ++i) { 292 Map.Entry x = (Map.Entry)(it.next()); 293 k = x.getKey(); 294 v = x.getValue(); 295 seen.put(k, k); 296 if (x != MISSING) 297 ++sum; 298 } 299 reallyAssert(s.containsKey(k)); 300 it.remove(); 301 reallyAssert(!s.containsKey(k)); 302 while (it.hasNext()) { 303 Map.Entry x = (Map.Entry)(it.next()); 304 Object k2 = x.getKey(); 305 seen.put(k2, k2); 306 if (x != MISSING) 307 ++sum; 308 } 309 310 reallyAssert(s.size() == size-1); 311 s.put(k, v); 312 reallyAssert(seen.size() == size); 313 timer.finish(); 314 reallyAssert(sum == size); 315 reallyAssert(s.size() == size); 316 } 317 318 319 static void ittest(Map s, int size) { 320 ittest1(s, size); 321 ittest2(s, size); 322 ittest3(s, size); 323 // for (int i = 0; i < size-1; ++i) 324 // ittest4(s, size, i); 325 } 326 327 static void entest1(Hashtable ht, int size) { 328 int sum = 0; 329 330 timer.start("Iter Enumeration Key ", size); 331 for (Enumeration en = ht.keys(); en.hasMoreElements(); ) { 332 if (en.nextElement() != MISSING) 333 ++sum; 334 } 335 timer.finish(); 336 reallyAssert(sum == size); 337 } 338 339 static void entest2(Hashtable ht, int size) { 340 int sum = 0; 341 timer.start("Iter Enumeration Value ", size); 342 for (Enumeration en = ht.elements(); en.hasMoreElements(); ) { 343 if (en.nextElement() != MISSING) 344 ++sum; 345 } 346 timer.finish(); 347 reallyAssert(sum == size); 348 } 349 350 351 static void entest3(Hashtable ht, int size) { 352 int sum = 0; 353 354 timer.start("Iterf Enumeration Key ", size); 355 Enumeration en = ht.keys(); 356 for (int i = 0; i < size; ++i) { 357 if (en.nextElement() != MISSING) 358 ++sum; 359 } 360 timer.finish(); 361 reallyAssert(sum == size); 362 } 363 364 static void entest4(Hashtable ht, int size) { 365 int sum = 0; 366 timer.start("Iterf Enumeration Value", size); 367 Enumeration en = ht.elements(); 368 for (int i = 0; i < size; ++i) { 369 if (en.nextElement() != MISSING) 370 ++sum; 371 } 372 timer.finish(); 373 reallyAssert(sum == size); 374 } 375 376 static void entest(Map s, int size) { 377 if (s instanceof Hashtable) { 378 Hashtable ht = (Hashtable)s; 379 // entest3(ht, size); 380 // entest4(ht, size); 381 entest1(ht, size); 382 entest2(ht, size); 383 entest1(ht, size); 384 entest2(ht, size); 385 entest1(ht, size); 386 entest2(ht, size); 387 } 388 } 389 390 static void rtest(Map s, int size) { 391 timer.start("Remove (iterator) ", size); 392 for (Iterator it = s.keySet().iterator(); it.hasNext(); ) { 393 it.next(); 394 it.remove(); 395 } 396 timer.finish(); 397 } 398 399 static void rvtest(Map s, int size) { 400 timer.start("Remove (iterator) ", size); 401 for (Iterator it = s.values().iterator(); it.hasNext(); ) { 402 it.next(); 403 it.remove(); 404 } 405 timer.finish(); 406 } 407 408 409 static void dtest(Map s, int size, Object[] key) { 410 timer.start("Put (putAll) ", size * 2); 411 Map s2 = null; 412 try { 413 s2 = (Map) (s.getClass().newInstance()); 414 s2.putAll(s); 415 } 416 catch (Exception e) { e.printStackTrace(); return; } 417 timer.finish(); 418 419 timer.start("Iter Equals ", size * 2); 420 boolean eqt = s2.equals(s) && s.equals(s2); 421 reallyAssert(eqt); 422 timer.finish(); 423 424 timer.start("Iter HashCode ", size * 2); 425 int shc = s.hashCode(); 426 int s2hc = s2.hashCode(); 427 reallyAssert(shc == s2hc); 428 timer.finish(); 429 430 timer.start("Put (present) ", size); 431 s2.putAll(s); 432 timer.finish(); 433 434 timer.start("Iter EntrySet contains ", size * 2); 435 Set es2 = s2.entrySet(); 436 int sum = 0; 437 for (Iterator i1 = s.entrySet().iterator(); i1.hasNext(); ) { 438 Object entry = i1.next(); 439 if (es2.contains(entry)) ++sum; 440 } 441 timer.finish(); 442 reallyAssert(sum == size); 443 444 t6("Get ", size, s2, key, absent); 445 446 Object hold = s2.get(key[size-1]); 447 s2.put(key[size-1], absent[0]); 448 timer.start("Iter Equals ", size * 2); 449 eqt = s2.equals(s) && s.equals(s2); 450 reallyAssert(!eqt); 451 timer.finish(); 452 453 timer.start("Iter HashCode ", size * 2); 454 int s1h = s.hashCode(); 455 int s2h = s2.hashCode(); 456 reallyAssert(s1h != s2h); 457 timer.finish(); 458 459 s2.put(key[size-1], hold); 460 timer.start("Remove (iterator) ", size * 2); 461 Iterator s2i = s2.entrySet().iterator(); 462 Set es = s.entrySet(); 463 while (s2i.hasNext()) 464 es.remove(s2i.next()); 465 timer.finish(); 466 467 reallyAssert(s.isEmpty()); 468 469 timer.start("Clear ", size); 470 s2.clear(); 471 timer.finish(); 472 reallyAssert(s2.isEmpty() && s.isEmpty()); 473 } 474 475 static void stest(Map s, int size) throws Exception { 476 if (!(s instanceof Serializable)) 477 return; 478 System.out.print("Serialize : "); 479 480 for (int i = 0; i < size; i++) { 481 s.put(new Integer(i), Boolean.TRUE); 482 } 483 484 long startTime = System.currentTimeMillis(); 485 486 FileOutputStream fs = new FileOutputStream("MapCheck.dat"); 487 ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(fs)); 488 out.writeObject(s); 489 out.close(); 490 491 FileInputStream is = new FileInputStream("MapCheck.dat"); 492 ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(is)); 493 Map m = (Map)in.readObject(); 494 495 long endTime = System.currentTimeMillis(); 496 long time = endTime - startTime; 497 498 System.out.print(time + "ms"); 499 500 if (s instanceof IdentityHashMap) return; 501 reallyAssert(s.equals(m)); 502 } 503 504 505 static void test(Map s, Object[] key) { 506 int size = key.length; 507 508 t3("Put (absent) ", size, s, key, size); 509 t3("Put (present) ", size, s, key, 0); 510 t7("ContainsKey ", size, s, key, absent); 511 t4("ContainsKey ", size, s, key, size); 512 ktest(s, size, key); 513 t4("ContainsKey ", absentSize, s, absent, 0); 514 t6("Get ", size, s, key, absent); 515 t1("Get (present) ", size, s, key, size); 516 t1("Get (absent) ", absentSize, s, absent, 0); 517 t2("Remove (absent) ", absentSize, s, absent, 0); 518 t5("Remove (present) ", size, s, key, size / 2); 519 t3("Put (half present) ", size, s, key, size / 2); 520 521 ittest(s, size); 522 entest(s, size); 523 t9(s); 524 rtest(s, size); 525 526 t4("ContainsKey ", size, s, key, 0); 527 t2("Remove (absent) ", size, s, key, 0); 528 t3("Put (presized) ", size, s, key, size); 529 dtest(s, size, key); 530 } 531 532 static class TestTimer { 533 private String name; 534 private long numOps; 535 private long startTime; 536 private String cname; 537 538 static final java.util.TreeMap accum = new java.util.TreeMap(); 539 540 static void printStats() { 541 for (Iterator it = accum.entrySet().iterator(); it.hasNext(); ) { 542 Map.Entry e = (Map.Entry)(it.next()); 543 Stats stats = ((Stats)(e.getValue())); 544 int n = stats.number; 545 double t; 546 if (n > 0) 547 t = stats.sum / n; 548 else 549 t = stats.least; 550 long nano = Math.round(1000000.0 * t); 551 System.out.println(e.getKey() + ": " + nano); 552 } 553 } 554 555 void start(String name, long numOps) { 556 this.name = name; 557 this.cname = classify(); 558 this.numOps = numOps; 559 startTime = System.currentTimeMillis(); 560 } 561 562 563 String classify() { 564 if (name.startsWith("Get")) 565 return "Get "; 566 else if (name.startsWith("Put")) 567 return "Put "; 568 else if (name.startsWith("Remove")) 569 return "Remove "; 570 else if (name.startsWith("Iter")) 571 return "Iter "; 572 else 573 return null; 574 } 575 576 void finish() { 577 long endTime = System.currentTimeMillis(); 578 long time = endTime - startTime; 579 double timePerOp = ((double)time)/numOps; 580 581 Object st = accum.get(name); 582 if (st == null) 583 accum.put(name, new Stats(timePerOp)); 584 else { 585 Stats stats = (Stats) st; 586 stats.sum += timePerOp; 587 stats.number++; 588 if (timePerOp < stats.least) stats.least = timePerOp; 589 } 590 591 if (cname != null) { 592 st = accum.get(cname); 593 if (st == null) 594 accum.put(cname, new Stats(timePerOp)); 595 else { 596 Stats stats = (Stats) st; 597 stats.sum += timePerOp; 598 stats.number++; 599 if (timePerOp < stats.least) stats.least = timePerOp; 600 } 601 } 602 603 } 604 605 } 606 607 static class Stats { 608 double sum = 0; 609 double least; 610 int number = 0; 611 Stats(double t) { least = t; } 612 } 613 614 static void shuffle(Object[] keys) { 615 ThreadLocalRandom rnd = ThreadLocalRandom.current(); 616 int size = keys.length; 617 for (int i=size; i>1; i--) { 618 int r = rnd.nextInt(i); 619 Object t = keys[i-1]; 620 keys[i-1] = keys[r]; 621 keys[r] = t; 622 } 623 } 624 625} 626