Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
p6rt opened this issue Sep 17, 2013 · 1 comment
Labels

Comments

@p6rt
Copy link

p6rt commented Sep 17, 2013

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

Searchable as RT119865$

@p6rt
Copy link
Author

p6rt commented Sep 17, 2013

From @masak

<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.

@p6rt p6rt added the perf label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant