Enough quantifiers in the declarative prefix in a regex takes exponential time in Rakudo

[p6rt]

Migrated from rt.perl.org#119865 (status was 'new')

Searchable as RT119865$

[p6rt]

From @masak

\ r​: my $N = 5; my $rx = "a?" x $N ~ "a" x $N; say "a" x $N ~~ /\<$rx>/ \ rakudo c0814a​: OUTPUT«｢aaaaa｣␤␤» \ r​: my $N = 32; my $rx = "a?" x $N ~ "a" x $N; say "a" x $N ~~ /\<$rx>/ \ moritz​: oh yes, that'd work too \ rakudo c0814a​: OUTPUT«(timeout)» * masak submits rakudobug * masak throws in http://swtch.com/~rsc/regexp/regexp1.html as 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.