|Subject:||[SLOW] Enough quantifiers in the declarative prefix in a regex takes exponential time in Rakudo|
|Date:||Tue, 17 Sep 2013 16:43:53 +0200|
|To:||rakudobug [...] perl.org|
|From:||Carl Mäsak <cmasak [...] gmail.com>|
<masak> r: my $N = 5; my $rx = "a?" x $N ~ "a" x $N; say "a" x $N ~~ /<$rx>/ <camelia> rakudo c0814a: OUTPUT«｢aaaaa｣␤␤» <masak> r: my $N = 32; my $rx = "a?" x $N ~ "a" x $N; say "a" x $N ~~ /<$rx>/ <tadzik> moritz: oh yes, that'd work too <camelia> rakudo c0814a: OUTPUT«(timeout)» * masak submits rakudobug * masak throws inas a reference As that page shows, this can be made into a polynomial thing rather than an exponential one, by dealing directly with the NFA. NQP's regex engine should be perfectly suited for this already. Even disregarding that, there are various optimization tricks (à la Perl 5) that can be done to make such a regex do less work.