Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: What perl operations will consume C stack space?

by hv (Parson)
on Feb 25, 2006 at 11:40 UTC ( #532761=note: print w/ replies, xml ) Need Help??


in reply to What perl operations will consume C stack space?

Here's about the simplest one I can come up with:

perl -wle '$n=32766; $_="a" x $n; /(ab*){$n}/'

On most implementations this will coredump; depending on stacksize, it may coredump for much lower $n.

See the #24274 regexp metabug for more detail.

Hugo


Comment on Re: What perl operations will consume C stack space?
Download Code
Re^2: What perl operations will consume C stack space?
by BrowserUk (Pope) on Feb 27, 2006 at 04:04 UTC

    Thankyou. This was extremely helpful.

    One further question. Do you know of any legitimate, non-error uses of heavily backtracking regexes that cannot be better expressed using less stack hungry varients?


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Sorry, I can't answer that without fuller definitions of "legitimate" and "cannot be better expressed" - which does my previous example fall foul of?

      Any pattern that repeats a "non-simple" expression will consume C-stack space on each repetition. At least 3 of the 4 bugs linked to the metabug #24274 arose from people solving real world tasks, and there are more in the bugs database that should also be linked to the metabug - more recent ones often involve searching for particular structures in a genome.

      Here's another common fragment that invokes the problem:

      $_ = sprintf q{"%s"}, "a" x 32768; /"((?:\\.|[^"])+)"/;
      though it consumes stack at only half the rate of the /(ab*)*/ variety.

      Hugo

        I'm probably missing something, but I don't see the circumstances under which /(ab*){32766}/ couldn't be replaced by /(ab+|a){32766}/ with the same outcome (except the core dump), but much less backtracking?

        Likewise, is there anything that /"((?:\\.|[^"])+)"/ would match that /"([^"]+)"/ wouldn't?


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://532761]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (11)
As of 2014-11-28 19:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (200 votes), past polls