1 // A case of catastrophic backtracking in Java 8

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

     3 //

     4 // regexp: (a*)*b

     5 // strings: aa....

     6 //

     7 // compile:    javac catastrophic.java

     8 // call with:  java catastrophic

     9 //

    10 // IMPORTANT: 

    11 // Java 9 improved its regex matching engine.

    12 // This example is now much faster.

    13 //

    14 

    15 import java.util.regex.*;

    16 

    17 public class catastrophic {

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

    19 	

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

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

    22             

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

    24             

    25             // Run from 5 to 28 characters

    26             for (int length = 5; length < 28; length++) {

    27                 

    28                 // Build input of specified length

    29                 String input = "";

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

    31                 

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

    33                 long start = System.nanoTime();

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

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

    36                 }

    37 

    38                 // Print out time

    39                 System.out.println(length + " " + input + ": " 

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

    41                        + "s");

    42             }

    43         }

    44     }

    45 }