1 // A case of catastrophic backtracking in Java 9+

     2 //------------------------------------------------

     3 //

     4 // It is actually not too bad in comparison what Python

     5 // and Java 8 are to compute. But it is still pretty

     6 // bad, even in Java 9, considering that the the basic

     7 // part of the CW improves on this by a factor of 100

     8 // (...if implemented correctly).

     9 //

    10 // regexp: (a*)*b

    11 // strings: aa....aaa

    12 //

    13 // compile with: javac catastrophic9.java

    14 // call with:    java catastrophic9

    15 //

    16 //

    17 

    18 import java.util.regex.*;

    19 

    20 public class catastrophic9 {

    21     public static void main(String[] args) {

    22 

    23         //we always run all the tests twice -> to warmup of the JVM

    24         for (int runs = 0; runs < 2; runs++) {

    25             

    26             Pattern pattern = Pattern.compile("(a*)*b");

    27             

    28             // Run from 5 to 28 characters

    29             for (int length = 0; length < 50000; length += 5000) {

    30                 

    31                 // Build input of specified length

    32                 String input = "";

    33                 for (int i = 0; i < length; i++) { input += "a"; }

    34                 

    35                 // Measure the average duration of two calls...  

    36                 long start = System.nanoTime();

    37                 for (int i = 0; i < 2; i++) {

    38                     pattern.matcher(input).find();

    39                 }

    40 

    41                 // Print out time

    42                 System.out.println(length + " a's : " 

    43                        + ((System.nanoTime() - start) / 2000000000d) 

    44                        + " secs");

    45             }

    46         }

    47     }

    48 }