Skip Menu |
Report information
Id: 119865
Status: new
Priority: 0/
Queue: perl6

Owner: Nobody
Requestors: masak <cmasak [at] gmail.com>
Cc:
AdminCc:

Severity: (no value)
Tag: (no value)
Platform: (no value)
Patch Status: (no value)
VM: (no value)



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>
Download (untitled) / with headers
text/plain 717b
<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 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.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org