develooper Front page | perl.perl5.porters | Postings from April 2010

Re: [perl #74484] Regex causing exponential runtime+mem usage

Thread Previous | Thread Next
Dave Mitchell
April 21, 2010 04:24
Re: [perl #74484] Regex causing exponential runtime+mem usage
Message ID:
On Mon, Apr 19, 2010 at 01:34:02AM -0700, wrote:
> I've been smoking CPAN modules for CPANTesters and noticed that my bots
> got OOMKilled from time to time.

Thanks for the report.

It appears there are two (mostly) unrelated issues here. First is the
performance, which is quadratic in string length.

This is due to String::Perl::Warnings creating a regexp that looks
essentially like /.*?..../. This is equivalent to /^.*?.*?...../
(note the anchor) and on repeated backtracking the two .*? make it go
quadratic. The fix for the String::Perl::Warnings module's author is to
either remove the initial .*?, or add an initial anchor.

The second issue is the memory usage, which again appears to be quadratic
on string length. This is due to the trie code leaking SVs on the tmps
stack (which then accumulate quadratically with the quadratic backtracking
caused by the first issue). I've currently got some ideas on how to rework
that bit of code to not need to create temp SVs to store the accept
states, but in the meantime I've added a TODO test with commit

I don't want to achieve immortality through my work... I want to achieve
it through not dying.
    -- Woody Allen

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About