View Javadoc

1   /* InterruptibleCharSequenceTest
2    * 
3    * Created on Jun 27, 2007
4    *
5    * Copyright (C) 2007 Internet Archive.
6    * 
7    * This file is part of the Heritrix web crawler (crawler.archive.org).
8    * 
9    * Heritrix is free software; you can redistribute it and/or modify
10   * it under the terms of the GNU Lesser Public License as published by
11   * the Free Software Foundation; either version 2.1 of the License, or
12   * any later version.
13   * 
14   * Heritrix is distributed in the hope that it will be useful, 
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17   * GNU Lesser Public License for more details.
18   * 
19   * You should have received a copy of the GNU Lesser Public License
20   * along with Heritrix; if not, write to the Free Software
21   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
22   */
23  package org.archive.util;
24  
25  import java.util.concurrent.BlockingQueue;
26  import java.util.concurrent.LinkedBlockingQueue;
27  import java.util.regex.Pattern;
28  
29  import junit.framework.TestCase;
30  
31  /***
32   * Tests (and 
33   * @author gojomo
34   */
35  public class InterruptibleCharSequenceTest extends TestCase {
36      // this regex takes many seconds to fail on the input
37      // (~20 seconds on 2Ghz Athlon64 JDK 1.6)
38      public static String BACKTRACKER = "^(((((a+)*)*)*)*)*$";
39      public static String INPUT = "aaaaab";
40      
41      /***
42       * Development-time benchmarking of InterruptibleCharSequence in
43       * regex use. (Rename 'xest' to 'test' if wanted as unit test, 
44       * but never actually fails anything -- just measures.)
45       * 
46       * For reference the regex "^(((((a+)*)*)*)*)*$" requires 
47       * 239,286,636 charAt(s) to fail on "aaaaab", which takes
48       * around 20 seconds on a 2Ghz Athlon64(x2) with JDK 1.6. 
49       * The runtime overhead of checking interrupt status in this
50       * extreme case is around 5% in my tests.
51       */
52      public void xestOverhead() {
53          String regex = BACKTRACKER;
54          String inputNormal = INPUT;
55          InterruptibleCharSequence inputWrapped = new InterruptibleCharSequence(inputNormal); 
56          // warm up 
57          tryMatch(inputNormal,regex);
58          tryMatch(inputWrapped,regex);
59          // inputWrapped.counter=0;
60          int trials = 5; 
61          long stringTally = 0;
62          long icsTally = 0; 
63          for(int i = 1; i <= trials; i++) {
64              System.out.println("trial "+i+" of "+trials);
65              long start = System.currentTimeMillis();
66              System.out.print("String ");
67              tryMatch(inputNormal,regex);
68              long end = System.currentTimeMillis();
69              System.out.println(end-start); 
70              stringTally += (end-start); 
71              start = System.currentTimeMillis();
72              System.out.print("InterruptibleCharSequence ");
73              tryMatch(inputWrapped,regex);
74              end = System.currentTimeMillis();
75              System.out.println(end-start); 
76              //System.out.println(inputWrapped.counter+" steps");
77              //inputWrapped.counter=0;
78              icsTally += (end-start); 
79          }
80          System.out.println("InterruptibleCharSequence took "+((float)icsTally)/stringTally+" longer."); 
81      }
82      
83      public boolean tryMatch(CharSequence input, String regex) {
84          return Pattern.matches(regex,input);
85      }
86      
87      public Thread tryMatchInThread(final CharSequence input, final String regex, final BlockingQueue<Object> atFinish) {
88          Thread t = new Thread() { 
89              public void run() { 
90                  boolean result; 
91                  try {
92                      result = tryMatch(input,regex); 
93                  } catch (Exception e) {
94                      atFinish.offer(e);
95                      return;
96                  }
97                  atFinish.offer(result);
98              } 
99          };
100         t.start();
101         return t; 
102     }
103     
104     public void testNoninterruptible() throws InterruptedException {
105         BlockingQueue<Object> q = new LinkedBlockingQueue<Object>();
106         Thread t = tryMatchInThread(INPUT, BACKTRACKER, q);
107         Thread.sleep(1000);
108         t.interrupt();
109         Object result = q.take(); 
110         assertTrue("mismatch uncompleted",Boolean.FALSE.equals(result));
111     }
112     
113     public void testInterruptibility() throws InterruptedException {
114         BlockingQueue<Object> q = new LinkedBlockingQueue<Object>();
115         Thread t = tryMatchInThread(new InterruptibleCharSequence(INPUT), BACKTRACKER, q);
116         Thread.sleep(1000);
117         t.interrupt();
118         Object result = q.take(); 
119         assertTrue("exception not thrown",result instanceof RuntimeException);
120     }
121 }