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