1/* 2 * PerformanceTest.java 3 * Copyright (C) 2007 Amin Ahmad. 4 * 5 * This file is part of Java Ropes. 6 * 7 * Java Ropes is free software: you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation, either version 3 of the License, or 10 * (at your option) any later version. 11 * 12 * Java Ropes is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with Java Ropes. If not, see <http://www.gnu.org/licenses/>. 19 * 20 * Amin Ahmad can be contacted at amin.ahmad@gmail.com or on the web at 21 * www.ahmadsoft.org. 22 */ 23package org.ahmadsoft.ropes.test; 24 25import java.io.BufferedReader; 26import java.io.CharArrayWriter; 27import java.io.FileReader; 28import java.io.IOException; 29import java.io.PrintStream; 30import java.io.StringWriter; 31import java.io.Writer; 32import java.util.Arrays; 33import java.util.Random; 34import java.util.regex.Matcher; 35import java.util.regex.Pattern; 36 37import javolution.text.Text; 38 39import org.ahmadsoft.ropes.Rope; 40import org.ahmadsoft.ropes.impl.AbstractRope; 41 42/** 43 * Performs an extensive performance test comparing Ropes, Strings, and 44 * StringBuffers. 45 * @author aahmad 46 */ 47public class PerformanceTest { 48 49 private static int seed=342342; 50 private static Random random = new Random(PerformanceTest.seed); 51 private static int lenCC = 182029; 52 private static int lenBF = 467196; 53 54 private static final int ITERATION_COUNT = 7; 55 private static final int PLAN_LENGTH = 500; 56 57 58 private static String complexString=null; 59 private static StringBuffer complexStringBuffer=null; 60 private static Rope complexRope=null; 61 private static Text complexText=null; 62 63 /** 64 * @param args 65 */ 66 public static void main(final String[] args) throws Exception { 67 68 if (args.length == 1) { 69 seed = Integer.parseInt(args[0]); 70 } 71 72 long x,y; 73 74 x=System.nanoTime(); 75 final char[] aChristmasCarol_RAW = PerformanceTest.readCC(); 76 final char[] bensAuto_RAW = PerformanceTest.readBF(); 77 final String aChristmasCarol = new String(aChristmasCarol_RAW); 78 final String bensAuto = new String(bensAuto_RAW); 79 y=System.nanoTime(); 80 System.out.println("Read " + aChristmasCarol.length() + " bytes in " + PerformanceTest.time(x,y)); 81 82 System.out.println(); 83 System.out.println("**** DELETE PLAN TEST ****"); 84 System.out.println(); 85 86 int newSize = PerformanceTest.lenCC; 87 final int[][] deletePlan=new int[PLAN_LENGTH][2]; 88 for (int j=0;j<deletePlan.length;++j) { 89 deletePlan[j][0] = PerformanceTest.random.nextInt(newSize); 90 deletePlan[j][1] = PerformanceTest.random.nextInt(Math.min(100, newSize - deletePlan[j][0])); 91 newSize -= deletePlan[j][1]; 92 } 93 94 for (int k=20; k<=deletePlan.length; k+=20) { 95 System.out.println("Delete plan length: " + k); 96 { 97 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT]; 98 for (int j=0;j<ITERATION_COUNT;++j){ 99 stats0[j] = PerformanceTest.stringDeleteTest(aChristmasCarol, deletePlan); 100 stats1[j] = PerformanceTest.stringBufferDeleteTest(aChristmasCarol, deletePlan); 101 stats2[j] = PerformanceTest.ropeDeleteTest(aChristmasCarol, deletePlan); 102 } 103 stat(System.out, stats0, "ns", "[String]"); 104 stat(System.out, stats1, "ns", "[StringBuffer]"); 105 stat(System.out, stats2, "ns", "[Rope]"); 106 } 107 } 108 109 System.out.println(); 110 System.out.println("**** PREPEND PLAN TEST ****"); 111 System.out.println(); 112 113 final int[][] prependPlan=new int[PLAN_LENGTH][2]; 114 for (int j=0;j<prependPlan.length;++j) { 115 prependPlan[j][0] = PerformanceTest.random.nextInt(PerformanceTest.lenCC); 116 prependPlan[j][1] = PerformanceTest.random.nextInt(PerformanceTest.lenCC - prependPlan[j][0]); 117 } 118 119 for (int k=20; k<=prependPlan.length; k+=20) { 120 System.out.println("Prepend plan length: " + k); 121 { 122 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT]; 123 for (int j=0;j<ITERATION_COUNT;++j){ 124 stats0[j] = PerformanceTest.stringPrependTest(aChristmasCarol, prependPlan, k); 125 stats1[j] = PerformanceTest.stringBufferPrependTest(aChristmasCarol, prependPlan, k); 126 stats2[j] = PerformanceTest.ropePrependTest(aChristmasCarol, prependPlan, k); 127 stats3[j] = PerformanceTest.textPrependTest(aChristmasCarol, prependPlan, k); 128 } 129 stat(System.out, stats0, "ns", "[String]"); 130 stat(System.out, stats1, "ns", "[StringBuffer]"); 131 stat(System.out, stats2, "ns", "[Rope]"); 132 stat(System.out, stats3, "ns", "[Text]"); 133 } 134 } 135 136 System.out.println(); 137 System.out.println("**** APPEND PLAN TEST ****"); 138 System.out.println(); 139 140 final int[][] appendPlan=new int[PLAN_LENGTH][2]; 141 for (int j=0;j<appendPlan.length;++j) { 142 appendPlan[j][0] = PerformanceTest.random.nextInt(PerformanceTest.lenCC); 143 appendPlan[j][1] = PerformanceTest.random.nextInt(PerformanceTest.lenCC - appendPlan[j][0]); 144 } 145 146 147 for (int k=20; k<=appendPlan.length; k+=20) { 148 System.out.println("Append plan length: " + k); 149 { 150 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT]; 151 for (int j=0;j<ITERATION_COUNT;++j){ 152 stats0[j] = PerformanceTest.stringAppendTest(aChristmasCarol, appendPlan, k); 153 stats1[j] = PerformanceTest.stringBufferAppendTest(aChristmasCarol, appendPlan, k); 154 stats2[j] = PerformanceTest.ropeAppendTest(aChristmasCarol, appendPlan, k); 155 } 156 stat(System.out, stats0, "ns", "[String]"); 157 stat(System.out, stats1, "ns", "[StringBuffer]"); 158 stat(System.out, stats2, "ns", "[Rope]"); 159 } 160 } 161 162 163 System.out.println(); 164 System.out.println("**** INSERT PLAN TEST ****"); 165 System.out.println("* Insert fragments of A Christmas Carol back into itself.\n"); 166 167 final int[][] insertPlan=new int[PLAN_LENGTH][3]; 168 for (int j=0;j<insertPlan.length;++j) { 169 insertPlan[j][0] = PerformanceTest.random.nextInt(PerformanceTest.lenCC); //location to insert 170 insertPlan[j][1] = PerformanceTest.random.nextInt(PerformanceTest.lenCC); //clip from 171 insertPlan[j][2] = PerformanceTest.random.nextInt(PerformanceTest.lenCC - insertPlan[j][1]); //clip length 172 } 173 174 175 176 for (int k=insertPlan.length; k<=insertPlan.length; k+=20) { 177 System.out.println("Insert plan length: " + k); 178 { 179 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT]; 180 for (int j=0;j<1;++j){ 181 stats0[j] = PerformanceTest.stringInsertTest(aChristmasCarol_RAW, insertPlan, k); 182 stats1[j] = PerformanceTest.stringBufferInsertTest(aChristmasCarol_RAW, insertPlan, k); 183 stats2[j] = PerformanceTest.ropeInsertTest(aChristmasCarol_RAW, insertPlan, k); 184 stats3[j] = PerformanceTest.textInsertTest(aChristmasCarol_RAW, insertPlan, k); 185 } 186 stat(System.out, stats0, "ns", "[String]"); 187 stat(System.out, stats1, "ns", "[StringBuffer]"); 188 stat(System.out, stats2, "ns", "[Rope]"); 189 stat(System.out, stats3, "ns", "[Text]"); 190 } 191 } 192 193 System.out.println(); 194 System.out.println("**** INSERT PLAN TEST 2 ****"); 195 System.out.println("* Insert fragments of Benjamin Franklin's Autobiography into\n" + 196 "* A Christmas Carol.\n"); 197 198 final int[][] insertPlan2=new int[PLAN_LENGTH][3]; 199 for (int j=0;j<insertPlan2.length;++j) { 200 insertPlan2[j][0] = PerformanceTest.random.nextInt(PerformanceTest.lenCC); //location to insert 201 insertPlan2[j][1] = PerformanceTest.random.nextInt(PerformanceTest.lenBF); //clip from 202 insertPlan2[j][2] = PerformanceTest.random.nextInt(PerformanceTest.lenBF - insertPlan2[j][1]); //clip length 203 } 204 205 { 206 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT]; 207 for (int j=0;j<ITERATION_COUNT;++j){ 208 stats0[j] = PerformanceTest.stringInsertTest2(aChristmasCarol, bensAuto, insertPlan2); 209 stats1[j] = PerformanceTest.stringBufferInsertTest2(aChristmasCarol, bensAuto, insertPlan2); 210 stats2[j] = PerformanceTest.ropeInsertTest2(aChristmasCarol, bensAuto, insertPlan2); 211 } 212 stat(System.out, stats0, "ns", "[String]"); 213 stat(System.out, stats1, "ns", "[StringBuffer]"); 214 stat(System.out, stats2, "ns", "[Rope]"); 215 } 216 217 System.out.println(); 218 System.out.println("**** TRAVERSAL TEST 1 (SIMPLY-CONSTRUCTED DATASTRUCTURES) ****"); 219 System.out.println("* A traversal test wherein the datastructures are simply\n" + 220 "* constructed, meaning constructed straight from the data\n" + 221 "* file with no further modifications. In this case, we expect\n" + 222 "* rope performance to be competitive, with the charAt version\n" + 223 "* performing better than the iterator version."); 224 System.out.println(); 225 226 { 227 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT]; 228 for (int j=0;j<ITERATION_COUNT;++j){ 229 stats0[j] = PerformanceTest.stringTraverseTest(aChristmasCarol_RAW); 230 stats1[j] = PerformanceTest.stringBufferTraverseTest(aChristmasCarol_RAW); 231 stats2[j] = PerformanceTest.ropeTraverseTest_1(aChristmasCarol_RAW); 232 stats3[j] = PerformanceTest.ropeTraverseTest_2(aChristmasCarol_RAW); 233 } 234 stat(System.out, stats0, "ns", "[String]"); 235 stat(System.out, stats1, "ns", "[StringBuffer]"); 236 stat(System.out, stats2, "ns", "[Rope/charAt]"); 237 stat(System.out, stats3, "ns", "[Rope/itr]"); 238 } 239 240 System.out.println(); 241 System.out.println("**** TRAVERSAL TEST 2 (COMPLEXLY-CONSTRUCTED DATASTRUCTURES) ****"); 242 System.out.println("* A traversal test wherein the datastructures are complexly\n" + 243 "* constructed, meaning constructed through hundreds of insertions,\n" + 244 "* substrings, and deletions (deletions not yet implemented). In\n" + 245 "* this case, we expect rope performance to suffer, with the\n" + 246 "* iterator version performing better than the charAt version."); 247 System.out.println(); 248 249 { 250 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT], stats4 = new long[ITERATION_COUNT]; 251 for (int j=0;j<3;++j){ 252 stats0[j] = PerformanceTest.stringTraverseTest2(complexString); 253 stats1[j] = PerformanceTest.stringBufferTraverseTest2(complexStringBuffer); 254 stats2[j] = PerformanceTest.ropeTraverseTest2_1(complexRope); 255 stats3[j] = PerformanceTest.ropeTraverseTest2_2(complexRope); 256 stats4[j] = PerformanceTest.textTraverseTest2(complexText); 257 } 258 stat(System.out, stats0, "ns", "[String]"); 259 stat(System.out, stats1, "ns", "[StringBuffer]"); 260 stat(System.out, stats2, "ns", "[Rope/charAt]"); 261 stat(System.out, stats3, "ns", "[Rope/itr]"); 262 stat(System.out, stats4, "ns", "[Text/charAt]"); 263 } 264 265 System.out.println(); 266 System.out.println("**** REGULAR EXPRESSION TEST (SIMPLY-CONSTRUCTED DATASTRUCTURES) ****"); 267 System.out.println("* Using a simply-constructed rope and the pattern 'Crachit'."); 268 269 Pattern p1 = Pattern.compile("Cratchit"); 270 271 { 272 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT], stats4 = new long[ITERATION_COUNT]; 273 for (int j=0;j<ITERATION_COUNT;++j){ 274 stats0[j] = PerformanceTest.stringRegexpTest(aChristmasCarol_RAW, p1); 275 stats1[j] = PerformanceTest.stringBufferRegexpTest(aChristmasCarol_RAW, p1); 276 stats2[j] = PerformanceTest.ropeRegexpTest(aChristmasCarol_RAW, p1); 277 stats3[j] = PerformanceTest.ropeMatcherRegexpTest(aChristmasCarol_RAW, p1); 278 stats4[j] = PerformanceTest.textRegexpTest(aChristmasCarol_RAW, p1); 279 } 280 stat(System.out, stats0, "ns", "[String]"); 281 stat(System.out, stats1, "ns", "[StringBuffer]"); 282 stat(System.out, stats2, "ns", "[Rope]"); 283 stat(System.out, stats3, "ns", "[Rope.matcher]"); 284 stat(System.out, stats4, "ns", "[Text]"); 285 } 286 287 System.out.println(); 288 System.out.println("**** REGULAR EXPRESSION TEST (SIMPLY-CONSTRUCTED DATASTRUCTURES) ****"); 289 System.out.println("* Using a simply-constructed rope and the pattern 'plea.*y'."); 290 291 p1 = Pattern.compile("plea.*y"); 292 { 293 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT]; 294 for (int j=0;j<ITERATION_COUNT;++j){ 295 stats0[j] = PerformanceTest.stringRegexpTest(aChristmasCarol_RAW, p1); 296 stats1[j] = PerformanceTest.stringBufferRegexpTest(aChristmasCarol_RAW, p1); 297 stats2[j] = PerformanceTest.ropeRegexpTest(aChristmasCarol_RAW, p1); 298 stats3[j] = PerformanceTest.ropeMatcherRegexpTest(aChristmasCarol_RAW, p1); 299 } 300 stat(System.out, stats0, "ns", "[String]"); 301 stat(System.out, stats1, "ns", "[StringBuffer]"); 302 stat(System.out, stats2, "ns", "[Rope]"); 303 stat(System.out, stats3, "ns", "[Rope.matcher]"); 304 } 305 306 System.out.println(); 307 System.out.println("**** REGULAR EXPRESSION TEST (COMPLEXLY-CONSTRUCTED DATASTRUCTURES) ****"); 308 System.out.println("* Using a complexly-constructed rope and the pattern 'Crachit'."); 309 310 p1 = Pattern.compile("Cratchit"); 311 { 312 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT], stats3 = new long[ITERATION_COUNT], stats4 = new long[ITERATION_COUNT], stats5 = new long[ITERATION_COUNT]; 313 for (int j=0;j<ITERATION_COUNT;++j){ 314 stats0[j] = PerformanceTest.stringRegexpTest2(complexString, p1); 315 stats1[j] = PerformanceTest.stringBufferRegexpTest2(complexStringBuffer, p1); 316 stats2[j] = PerformanceTest.ropeRegexpTest2(complexRope, p1); 317 stats3[j] = PerformanceTest.ropeRebalancedRegexpTest2(complexRope, p1); 318 stats4[j] = PerformanceTest.ropeMatcherRegexpTest2(complexRope, p1); 319 stats5[j] = PerformanceTest.textRegexpTest2(complexText, p1); 320 } 321 stat(System.out, stats0, "ns", "[String]"); 322 stat(System.out, stats1, "ns", "[StringBuffer]"); 323 stat(System.out, stats2, "ns", "[Rope]"); 324 stat(System.out, stats3, "ns", "[Reblncd Rope]"); 325 stat(System.out, stats4, "ns", "[Rope.matcher]"); 326 stat(System.out, stats5, "ns", "[Text]"); 327 } 328 329 System.out.println(); 330 System.out.println("**** STRING SEARCH TEST ****"); 331 System.out.println("* Using a simply constructed rope and the pattern 'Bob was very\n" + 332 "* cheerful with them, and spoke pleasantly to'."); 333 334 String toFind = "consumes faster than Labor wears; while the used key is always bright,"; 335 { 336 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT]; 337 for (int j=0;j<ITERATION_COUNT;++j){ 338 stats0[j] = PerformanceTest.stringFindTest(bensAuto_RAW, toFind); 339 stats1[j] = PerformanceTest.stringBufferFindTest(bensAuto_RAW, toFind); 340 stats2[j] = PerformanceTest.ropeFindTest(bensAuto_RAW, toFind); 341 } 342 stat(System.out, stats0, "ns", "[String]"); 343 stat(System.out, stats1, "ns", "[StringBuffer]"); 344 stat(System.out, stats2, "ns", "[Rope]"); 345 } 346 347 System.out.println(); 348 System.out.println("**** STRING SEARCH TEST (COMPLEXLY-CONSTRUCTED DATASTRUCTURES)****"); 349 System.out.println("* Using a complexly constructed rope and the pattern 'consumes faster\n" + 350 "* than Labor wears; while the used key is always bright,'."); 351 352 toFind = "Bob was very cheerful with them, and spoke pleasantly to"; 353 { 354 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT], stats2 = new long[ITERATION_COUNT]; 355 for (int j=0;j<ITERATION_COUNT;++j){ 356 stats0[j] = PerformanceTest.stringFindTest2(complexString, toFind); 357 stats1[j] = PerformanceTest.stringBufferFindTest2(complexStringBuffer, toFind); 358 stats2[j] = PerformanceTest.ropeFindTest2(complexRope, toFind); 359 } 360 stat(System.out, stats0, "ns", "[String]"); 361 stat(System.out, stats1, "ns", "[StringBuffer]"); 362 stat(System.out, stats2, "ns", "[Rope]"); 363 } 364 365 366 System.out.println(); 367 System.out.println("**** WRITE TEST ****"); 368 System.out.println("* Illustrates how to write a Rope to a stream efficiently."); 369 370 { 371 long[] stats0 = new long[ITERATION_COUNT], stats1 = new long[ITERATION_COUNT]; 372 for (int j=0;j<ITERATION_COUNT;++j){ 373 stats0[j] = PerformanceTest.ropeWriteBad(complexRope); 374 stats1[j] = PerformanceTest.ropeWriteGood(complexRope); 375 } 376 stat(System.out, stats0, "ns", "[Out.write]"); 377 stat(System.out, stats1, "ns", "[Rope.write]"); 378 } 379 } 380 381 private static long stringFindTest(char[] aChristmasCarol, String toFind) { 382 long x,y; 383 384 String b = new String(aChristmasCarol); 385 x = System.nanoTime(); 386 int loc = b.indexOf(toFind); 387 y = System.nanoTime(); 388 System.out.printf("[String.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 389 return (y-x); 390 } 391 392 private static long stringBufferFindTest(char[] aChristmasCarol, String toFind) { 393 long x,y; 394 395 StringBuffer b = new StringBuffer(aChristmasCarol.length); b.append(aChristmasCarol); 396 x = System.nanoTime(); 397 int loc = b.indexOf(toFind); 398 y = System.nanoTime(); 399 System.out.printf("[StringBuffer.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 400 return (y-x); 401 } 402 403 private static long ropeFindTest(char[] aChristmasCarol, String toFind) { 404 long x,y; 405 406 Rope b = Rope.BUILDER.build(aChristmasCarol); 407 x = System.nanoTime(); 408 int loc = b.indexOf(toFind); 409 y = System.nanoTime(); 410 System.out.printf("[Rope.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 411 return (y-x); 412 } 413 414 private static long stringFindTest2(String aChristmasCarol, String toFind) { 415 long x,y; 416 417 x = System.nanoTime(); 418 int loc = aChristmasCarol.indexOf(toFind); 419 y = System.nanoTime(); 420 System.out.printf("[String.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 421 return (y-x); 422 } 423 424 private static long stringBufferFindTest2(StringBuffer aChristmasCarol, String toFind) { 425 long x,y; 426 427 x = System.nanoTime(); 428 int loc = aChristmasCarol.indexOf(toFind); 429 y = System.nanoTime(); 430 System.out.printf("[StringBuffer.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 431 return (y-x); 432 } 433 434 private static long ropeFindTest2(Rope aChristmasCarol, String toFind) { 435 long x,y; 436 437 x = System.nanoTime(); 438 int loc = aChristmasCarol.indexOf(toFind); 439 y = System.nanoTime(); 440 System.out.printf("[Rope.find] indexOf needle length %d found at index %d in % ,18d ns.\n", toFind.length(), loc, (y-x)); 441 return (y-x); 442 } 443 444 private static long ropeWriteGood(Rope complexRope) { 445 long x,y; 446 447 Writer out = new StringWriter(complexRope.length()); 448 x = System.nanoTime(); 449 try { 450 complexRope.write(out); 451 } catch (IOException e) { 452 e.printStackTrace(); 453 } 454 y = System.nanoTime(); 455 System.out.printf("[Rope.write] Executed write in % ,18d ns.\n", (y-x)); 456 return (y-x); 457 } 458 459 private static long ropeWriteBad(Rope complexRope) { 460 long x,y; 461 462 Writer out = new StringWriter(complexRope.length()); 463 x = System.nanoTime(); 464 try { 465 out.write(complexRope.toString()); 466 } catch (IOException e) { 467 e.printStackTrace(); 468 } 469 y = System.nanoTime(); 470 System.out.printf("[Out.write] Executed write in % ,18d ns.\n", (y-x)); 471 return (y-x); 472 } 473 474 private static char[] readBF() throws Exception { 475 final CharArrayWriter out = new CharArrayWriter(467196); 476 final BufferedReader in = new BufferedReader(new FileReader("AutobiographyOfBenjaminFranklin_BenjaminFranklin.txt")); 477 478 final char[] c = new char[256]; 479 int x = -1; 480 while (-1 != (x=in.read(c))) { 481 out.write(c, 0, x); 482 } 483 out.close(); 484 return out.toCharArray(); 485 } 486 487 private static char[] readCC() throws Exception { 488 final CharArrayWriter out = new CharArrayWriter(182029); 489 final BufferedReader in = new BufferedReader(new FileReader("AChristmasCarol_CharlesDickens.txt")); 490 491 final char[] c = new char[256]; 492 int x = -1; 493 while (-1 != (x=in.read(c))) { 494 out.write(c, 0, x); 495 } 496 out.close(); 497 return out.toCharArray(); 498 } 499 500 private static long ropeAppendTest(final String aChristmasCarol, final int[][] appendPlan, final int planLength) { 501 long x,y; 502 503 x = System.nanoTime(); 504 Rope result=Rope.BUILDER.build(aChristmasCarol); 505 506 for (int j=0; j<planLength; ++j) { 507 final int offset = appendPlan[j][0]; 508 final int length = appendPlan[j][1]; 509 result = result.append(result.subSequence(offset, offset+length)); 510 } 511 y = System.nanoTime(); 512 System.out.printf("[Rope] Executed append plan in % ,18d ns. Result has length: %d. Rope Depth: %d\n", (y-x), result.length(), ((AbstractRope)result).depth()); 513 return (y-x); 514 } 515 516 private static long ropeDeleteTest(final String aChristmasCarol, final int[][] prependPlan) { 517 long x,y; 518 519 x = System.nanoTime(); 520 Rope result=Rope.BUILDER.build(aChristmasCarol); 521 522 for (int j=0; j<prependPlan.length; ++j) { 523 final int offset = prependPlan[j][0]; 524 final int length = prependPlan[j][1]; 525 result = result.delete(offset, offset + length); 526 } 527 y = System.nanoTime(); 528 System.out.printf("[Rope] Executed delete plan in % ,18d ns. Result has length: %d. Rope Depth: %d\n", (y-x), result.length(), ((AbstractRope)result).depth()); 529 return (y-x); 530 } 531 532 private static long ropeInsertTest(final char[] aChristmasCarol, final int[][] insertPlan, int planLength) { 533 long x,y; 534 Rope result=Rope.BUILDER.build(aChristmasCarol); 535 536 x = System.nanoTime(); 537 538 for (int j=0; j<planLength; ++j) { 539 final int into = insertPlan[j][0]; 540 final int offset = insertPlan[j][1]; 541 final int length = insertPlan[j][2]; 542 result = result.insert(into, result.subSequence(offset, offset+length)); 543 } 544 y = System.nanoTime(); 545 System.out.printf("[Rope] Executed insert plan in % ,18d ns. Result has length: %d. Rope Depth: %d\n", (y-x), result.length(), ((AbstractRope)result).depth()); 546 complexRope = result; 547 return (y-x); 548 } 549 550 private static long textInsertTest(final char[] aChristmasCarol, final int[][] insertPlan, int planLength) { 551 long x,y; 552 Text result=new Text(new String(aChristmasCarol)); 553 554 x = System.nanoTime(); 555 556 for (int j=0; j<planLength; ++j) { 557 final int into = insertPlan[j][0]; 558 final int offset = insertPlan[j][1]; 559 final int length = insertPlan[j][2]; 560 result = result.insert(into, result.subtext(offset, offset+length)); 561 } 562 y = System.nanoTime(); 563 System.out.printf("[Text] Executed insert plan in % ,18d ns. Result has length: %d.\n", (y-x), result.length()); 564 complexText = result; 565 return (y-x); 566 } 567 568 private static long ropeInsertTest2(final String aChristmasCarol, final String bensAuto, final int[][] insertPlan) { 569 long x,y; 570 571 x = System.nanoTime(); 572 Rope result=Rope.BUILDER.build(aChristmasCarol); 573 574 for (int j=0; j<insertPlan.length; ++j) { 575 final int into = insertPlan[j][0]; 576 final int offset = insertPlan[j][1]; 577 final int length = insertPlan[j][2]; 578 result = result.insert(into, bensAuto.subSequence(offset, offset+length)); 579 } 580 y = System.nanoTime(); 581 System.out.printf("[Rope] Executed insert plan in % ,18d ns. Result has length: %d. Rope Depth: %d\n", (y-x), result.length(), ((AbstractRope)result).depth()); 582 return (y-x); 583 } 584 585 private static long ropePrependTest(final String aChristmasCarol, final int[][] prependPlan, int planLength) { 586 long x,y; 587 588 x = System.nanoTime(); 589 Rope result=Rope.BUILDER.build(aChristmasCarol); 590 591 for (int j=0; j<planLength; ++j) { 592 final int offset = prependPlan[j][0]; 593 final int length = prependPlan[j][1]; 594 result = result.subSequence(offset, offset+length).append(result); 595 } 596 y = System.nanoTime(); 597 System.out.printf("[Rope] Executed prepend plan in % ,18d ns. Result has length: %d. Rope Depth: %d\n", (y-x), result.length(), ((AbstractRope)result).depth()); 598 return (y-x); 599 } 600 601 private static long textPrependTest(final String aChristmasCarol, final int[][] prependPlan, int planLength) { 602 long x,y; 603 604 x = System.nanoTime(); 605 Text result=new Text(aChristmasCarol); 606 607 for (int j=0; j<planLength; ++j) { 608 final int offset = prependPlan[j][0]; 609 final int length = prependPlan[j][1]; 610 result = result.subtext(offset, offset+length).concat(result); 611 } 612 y = System.nanoTime(); 613 System.out.printf("[Text] Executed prepend plan in % ,18d ns. Result has length: %d.\n", (y-x), result.length()); 614 return (y-x); 615 } 616 617 private static long ropeTraverseTest_1(final char[] aChristmasCarol) { 618 long x,y,result=0; 619 final Rope r=Rope.BUILDER.build(aChristmasCarol); 620 621 x = System.nanoTime(); 622 623 for (int j=0; j<r.length(); ++j) result+=r.charAt(j); 624 625 y = System.nanoTime(); 626 System.out.printf("[Rope/charAt] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), result); 627 return (y-x); 628 } 629 630 private static long ropeTraverseTest_2(final char[] aChristmasCarol) { 631 long x,y,result=0; 632 final Rope r=Rope.BUILDER.build(aChristmasCarol); 633 634 x = System.nanoTime(); 635 636 for (final char c: r) result+=c; 637 638 y = System.nanoTime(); 639 System.out.printf("[Rope/itr] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), result); 640 return (y-x); 641 } 642 643 private static long ropeTraverseTest2_1(Rope aChristmasCarol) { 644 long x,y; 645 646 Rope result=aChristmasCarol; 647 648 int r=0; 649 x = System.nanoTime(); 650 for (int j=0; j<result.length(); ++j) r+=result.charAt(j); 651 y = System.nanoTime(); 652 System.out.printf("[Rope/charAt] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), r); 653 return (y-x); 654 } 655 656 private static long textTraverseTest2(Text aChristmasCarol) { 657 long x,y; 658 659 Text result=aChristmasCarol; 660 661 int r=0; 662 x = System.nanoTime(); 663 for (int j=0; j<result.length(); ++j) r+=result.charAt(j); 664 y = System.nanoTime(); 665 System.out.printf("[Text/charAt] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), r); 666 return (y-x); 667 } 668 669 private static long ropeTraverseTest2_2(Rope aChristmasCarol) { 670 long x,y; 671 672 Rope result=aChristmasCarol; 673 674 int r=0; 675 x = System.nanoTime(); 676 for (final char c: result) r+=c; 677 y = System.nanoTime(); 678 System.out.printf("[Rope/itr] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), r); 679 return (y-x); 680 } 681 682 private static long stringAppendTest(final String aChristmasCarol, final int[][] appendPlan, final int planLength) { 683 long x,y; 684 685 x = System.nanoTime(); 686 String result=aChristmasCarol; 687 688 for (int j=0; j<planLength; ++j) { 689 final int offset = appendPlan[j][0]; 690 final int length = appendPlan[j][1]; 691 result = result.concat(result.substring(offset, offset + length)); 692 } 693 y = System.nanoTime(); 694 System.out.printf("[String] Executed append plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 695 return (y-x); 696 } 697 698 private static long stringBufferAppendTest(final String aChristmasCarol, final int[][] appendPlan, final int planLength) { 699 long x,y; 700 701 x = System.nanoTime(); 702 final StringBuffer result=new StringBuffer(aChristmasCarol); 703 704 for (int j=0; j<planLength; ++j) { 705 final int offset = appendPlan[j][0]; 706 final int length = appendPlan[j][1]; 707 result.append(result.subSequence(offset, offset+length)); 708 } 709 y = System.nanoTime(); 710 System.out.printf("[StringBuffer] Executed append plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 711 return (y-x); 712 } 713 714 private static long stringBufferDeleteTest(final String aChristmasCarol, final int[][] prependPlan) { 715 long x,y; 716 717 x = System.nanoTime(); 718 final StringBuffer result=new StringBuffer(aChristmasCarol); 719 720 for (int j=0; j<prependPlan.length; ++j) { 721 final int offset = prependPlan[j][0]; 722 final int length = prependPlan[j][1]; 723 result.delete(offset, offset+length); 724 } 725 y = System.nanoTime(); 726 System.out.printf("[StringBuffer] Executed delete plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 727 return (y-x); 728 } 729 730 private static long stringBufferInsertTest(final char[] aChristmasCarol, final int[][] insertPlan, int planLength) { 731 long x,y; 732 final StringBuffer result=new StringBuffer(aChristmasCarol.length); result.append(aChristmasCarol); 733 734 x = System.nanoTime(); 735 736 for (int j=0; j<planLength; ++j) { 737 final int into = insertPlan[j][0]; 738 final int offset = insertPlan[j][1]; 739 final int length = insertPlan[j][2]; 740 result.insert(into, result.subSequence(offset, offset+length)); 741 } 742 y = System.nanoTime(); 743 System.out.printf("[StringBuffer] Executed insert plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 744 complexStringBuffer = result; 745 return (y-x); 746 } 747 748 private static long stringBufferInsertTest2(final String aChristmasCarol, final String bensAuto, final int[][] insertPlan) { 749 long x,y; 750 751 x = System.nanoTime(); 752 final StringBuffer result=new StringBuffer(aChristmasCarol); 753 754 for (int j=0; j<insertPlan.length; ++j) { 755 final int into = insertPlan[j][0]; 756 final int offset = insertPlan[j][1]; 757 final int length = insertPlan[j][2]; 758 result.insert(into, bensAuto.subSequence(offset, offset+length)); 759 } 760 y = System.nanoTime(); 761 System.out.printf("[StringBuffer] Executed insert plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 762 return (y-x); 763 } 764 765 private static long stringBufferPrependTest(final String aChristmasCarol, final int[][] prependPlan, int planLength) { 766 long x,y; 767 768 x = System.nanoTime(); 769 final StringBuffer result=new StringBuffer(aChristmasCarol); 770 771 for (int j=0; j<planLength; ++j) { 772 final int offset = prependPlan[j][0]; 773 final int length = prependPlan[j][1]; 774 result.insert(0, result.subSequence(offset, offset+length)); 775 } 776 y = System.nanoTime(); 777 System.out.printf("[StringBuffer] Executed prepend plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 778 return (y-x); 779 } 780 781 private static long stringBufferTraverseTest(final char[] aChristmasCarol) { 782 long x,y,result=0; 783 final StringBuffer b=new StringBuffer(aChristmasCarol.length); b.append(aChristmasCarol); 784 785 x = System.nanoTime(); 786 787 for (int j=0; j<b.length(); ++j) result+=b.charAt(j); 788 789 y = System.nanoTime(); 790 System.out.printf("[StringBuffer] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), result); 791 return (y-x); 792 793 } 794 795 private static long stringBufferTraverseTest2(final StringBuffer aChristmasCarol) { 796 long x,y; 797 798 final StringBuffer result=aChristmasCarol; 799 800 int r=0; 801 x = System.nanoTime(); 802 for (int j=0; j<result.length(); ++j) r+=result.charAt(j); 803 y = System.nanoTime(); 804 System.out.printf("[StringBuffer] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), r); 805 return (y-x); 806 } 807 808 private static long stringDeleteTest(final String aChristmasCarol, final int[][] prependPlan) { 809 long x,y; 810 811 x = System.nanoTime(); 812 String result=aChristmasCarol; 813 814 for (int j=0; j<prependPlan.length; ++j) { 815 final int offset = prependPlan[j][0]; 816 final int length = prependPlan[j][1]; 817 result = result.substring(0, offset).concat(result.substring(offset+length)); 818 } 819 y = System.nanoTime(); 820 System.out.printf("[String] Executed delete plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 821 return (y-x); 822 } 823 824 private static long stringInsertTest(final char[] aChristmasCarol, final int[][] insertPlan, int planLength) { 825 long x,y; 826 String result=new String(aChristmasCarol); 827 828 x = System.nanoTime(); 829 830 for (int j=0; j<planLength; ++j) { 831 final int into = insertPlan[j][0]; 832 final int offset = insertPlan[j][1]; 833 final int length = insertPlan[j][2]; 834 result = result.substring(0, into).concat(result.substring(offset, offset + length)).concat(result.substring(into)); 835 836 } 837 y = System.nanoTime(); 838 System.out.printf("[String] Executed insert plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 839 complexString = result; 840 return (y-x); 841 } 842 843 private static long stringInsertTest2(final String aChristmasCarol, final String bensAuto, final int[][] insertPlan) { 844 long x,y; 845 846 x = System.nanoTime(); 847 String result=aChristmasCarol; 848 849 for (int j=0; j<insertPlan.length; ++j) { 850 final int into = insertPlan[j][0]; 851 final int offset = insertPlan[j][1]; 852 final int length = insertPlan[j][2]; 853 result = result.substring(0, into).concat(bensAuto.substring(offset, offset + length)).concat(result.substring(into)); 854 } 855 y = System.nanoTime(); 856 System.out.printf("[String] Executed insert plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 857 return (y-x); 858 } 859 860 private static long stringPrependTest(final String aChristmasCarol, final int[][] prependPlan, int planLength) { 861 long x,y; 862 863 x = System.nanoTime(); 864 String result=aChristmasCarol; 865 866 for (int j=0; j<planLength; ++j) { 867 final int offset = prependPlan[j][0]; 868 final int length = prependPlan[j][1]; 869 result = result.substring(offset, offset + length).concat(result); 870 } 871 y = System.nanoTime(); 872 System.out.printf("[String] Executed prepend plan in % ,18d ns. Result has length: %d\n", (y-x), result.length()); 873 return (y-x); 874 } 875 876 private static long stringTraverseTest(final char[] aChristmasCarol) { 877 long x,y,result=0; 878 String s = new String(aChristmasCarol); 879 880 x = System.nanoTime(); 881 882 for (int j=0; j<s.length(); ++j) result+=s.charAt(j); 883 884 y = System.nanoTime(); 885 System.out.printf("[String] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), result); 886 return (y-x); 887 } 888 889 private static long stringTraverseTest2(final String aChristmasCarol) { 890 long x,y; 891 892 String result=aChristmasCarol; 893 894 int r=0; 895 x = System.nanoTime(); 896 for (int j=0; j<result.length(); ++j) r+=result.charAt(j); 897 y = System.nanoTime(); 898 System.out.printf("[String] Executed traversal in % ,18d ns. Result checksum: %d\n", (y-x), r); 899 return (y-x); 900 } 901 902 private static long stringRegexpTest(final char[] aChristmasCarol, Pattern pattern) { 903 long x,y; 904 String s = new String(aChristmasCarol); 905 906 x = System.nanoTime(); 907 908 int result = 0; 909 Matcher m = pattern.matcher(s); 910 while (m.find()) ++result; 911 912 y = System.nanoTime(); 913 System.out.printf("[String] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 914 return (y-x); 915 } 916 917 private static long textRegexpTest(final char[] aChristmasCarol, Pattern pattern) { 918 long x,y; 919 Text s = new Text(new String(aChristmasCarol)); 920 921 x = System.nanoTime(); 922 923 int result = 0; 924 Matcher m = pattern.matcher(s); 925 while (m.find()) ++result; 926 927 y = System.nanoTime(); 928 System.out.printf("[Text] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 929 return (y-x); 930 } 931 932 private static long stringBufferRegexpTest(final char[] aChristmasCarol, Pattern pattern) { 933 long x,y; 934 StringBuffer buffer = new StringBuffer(aChristmasCarol.length); buffer.append(aChristmasCarol); 935 936 x = System.nanoTime(); 937 938 int result = 0; 939 Matcher m = pattern.matcher(buffer); 940 while (m.find()) ++result; 941 942 y = System.nanoTime(); 943 System.out.printf("[StringBuffer] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 944 return (y-x); 945 } 946 947 private static long ropeRegexpTest(final char[] aChristmasCarol, Pattern pattern) { 948 long x,y; 949 Rope rope = Rope.BUILDER.build(aChristmasCarol); 950 951 x = System.nanoTime(); 952 953 int result = 0; 954 Matcher m = pattern.matcher(rope); 955 while (m.find()) ++result; 956 957 y = System.nanoTime(); 958 System.out.printf("[Rope] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 959 return (y-x); 960 } 961 962 private static long ropeMatcherRegexpTest(final char[] aChristmasCarol, Pattern pattern) { 963 long x,y; 964 Rope rope = Rope.BUILDER.build(aChristmasCarol); 965 966 x = System.nanoTime(); 967 968 int result = 0; 969 Matcher m = rope.matcher(pattern); 970 while (m.find()) ++result; 971 972 y = System.nanoTime(); 973 System.out.printf("[Rope.matcher] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 974 return (y-x); 975 } 976 977 978 979 private static long stringRegexpTest2(final String aChristmasCarol, Pattern pattern) { 980 long x,y; 981 982 x = System.nanoTime(); 983 984 int result = 0; 985 Matcher m = pattern.matcher(aChristmasCarol); 986 while (m.find()) ++result; 987 988 y = System.nanoTime(); 989 System.out.printf("[String] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 990 return (y-x); 991 } 992 993 994 995 private static long textRegexpTest2(final Text aChristmasCarol, Pattern pattern) { 996 long x,y; 997 998 x = System.nanoTime(); 999 1000 int result = 0; 1001 Matcher m = pattern.matcher(aChristmasCarol); 1002 while (m.find()) ++result; 1003 1004 y = System.nanoTime(); 1005 System.out.printf("[Text] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 1006 return (y-x); 1007 } 1008 1009 private static long stringBufferRegexpTest2(final StringBuffer aChristmasCarol, Pattern pattern) { 1010 long x,y; 1011 1012 x = System.nanoTime(); 1013 1014 int result = 0; 1015 Matcher m = pattern.matcher(aChristmasCarol); 1016 while (m.find()) ++result; 1017 1018 y = System.nanoTime(); 1019 System.out.printf("[StringBuffer] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 1020 return (y-x); 1021 } 1022 1023 private static long ropeRegexpTest2(final Rope aChristmasCarol, Pattern pattern) { 1024 long x,y; 1025 1026 x = System.nanoTime(); 1027 1028 int result = 0; 1029 Matcher m = pattern.matcher(aChristmasCarol); 1030 while (m.find()) ++result; 1031 1032 y = System.nanoTime(); 1033 System.out.printf("[Rope] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 1034 return (y-x); 1035 } 1036 1037 private static long ropeRebalancedRegexpTest2(final Rope aChristmasCarol, Pattern pattern) { 1038 long x,y; 1039 1040 x = System.nanoTime(); 1041 1042 CharSequence adaptedRope = aChristmasCarol.rebalance(); //Rope.BUILDER.buildForRegexpSearching(aChristmasCarol); 1043 int result = 0; 1044 Matcher m = pattern.matcher(adaptedRope); 1045 while (m.find()) ++result; 1046 1047 y = System.nanoTime(); 1048 System.out.printf("[Reblncd Rope] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 1049 return (y-x); 1050 } 1051 1052 private static long ropeMatcherRegexpTest2(final Rope aChristmasCarol, Pattern pattern) { 1053 long x,y; 1054 1055 x = System.nanoTime(); 1056 1057 int result = 0; 1058 Matcher m = aChristmasCarol.matcher(pattern); 1059 while (m.find()) ++result; 1060 1061 y = System.nanoTime(); 1062 System.out.printf("[Rope.matcher] Executed regexp test in % ,18d ns. Found %d matches.\n", (y-x), result); 1063 return (y-x); 1064 } 1065 1066 private static String time(final long x, final long y) { 1067 return (y-x) + "ns"; 1068 } 1069 1070 private static void stat(PrintStream out, long[] stats, String unit, String prefix) { 1071 if (stats.length < 3) 1072 System.err.println("Cannot print stats."); 1073 Arrays.sort(stats); 1074 1075 double median = ((stats.length & 1) == 1 ? stats[stats.length >> 1]: (stats[stats.length >> 1] + stats[1 + (stats.length >> 1)]) / 2); 1076 double average = 0; 1077 for (int j=1;j<stats.length-1;++j) { 1078 average += stats[j]; 1079 } 1080 average /= stats.length - 2; 1081 out.printf("%-14s Average=% ,16.0f %s Median=% ,16.0f%s\n", prefix, average, unit, median, unit); 1082 } 1083 1084} 1085