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

On Mon, Apr 19, 2010 at 01:34:02AM -0700, perl@0ne.us 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
8bd05d90e59a554e79d73edf32bf35547dbc2c40


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

• [perl #74484] Regex causing exponential runtime+mem usage by perl@0ne.us
• Re: [perl #74484] Regex causing exponential runtime+mem usage by Dave Mitchell
• Re: [perl #74484] Regex causing exponential runtime+mem usage by Dave Mitchell
• Re: [perl #74484] Regex causing exponential runtime+mem usage by demerphq