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