Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

What perl operations will consume C stack space?

by BrowserUk (Pope)
on Feb 24, 2006 at 18:36 UTC ( #532616=perlquestion: print w/ replies, xml ) Need Help??
BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

The title says it all really. I would like suggestions for what I can do from Perl that will consume the most C-time stack (as opposed to Perl's stacks)?


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.

Comment on What perl operations will consume C stack space?
Re: What perl operations will consume C stack space?
by dave_the_m (Parson) on Feb 24, 2006 at 23:41 UTC
    Traditionally, regexes fulfill this role.

    Dave.

      Any good (as in pathologically stack consuming) examples? I've created many that consume time, but not stack.


      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.
        Aren't Perl regexes compiled into NFAs, and matching NFAs requires backtracking ? So I guess backtracking-heavy regexes like [a-e][r-z][4-9][^xyz] should eat up lots of stack.
Re: What perl operations will consume C stack space?
by TimToady (Parson) on Feb 25, 2006 at 10:16 UTC
    I can think of two things. First, as mentioned above, is certain regex executions. In particular, ones that quantify a compound submatch of varying length. I believe these are still done with C recursion, though I haven't looked lately.

    Second, calls into XS routines that then call back into Perl.

    There are probably a few others (recursive sorts? recursive runloop switches?) but by and large part of the initial design of Perl 5 was to be as stackless as practical (in the C-stackless sense). So all of Perl's stacks are really on the heap, and nearly all of the standard opcodes leave the C stack in the same state.

      Thankyou. This was extremely helpful.


      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.
Re: What perl operations will consume C stack space?
by hv (Parson) on Feb 25, 2006 at 11:40 UTC

    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

      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

Re: What perl operations will consume C stack space?
by ysth (Canon) on Apr 23, 2006 at 04:21 UTC
    dave_the_m has fixed the regex stack usage, as I understand it. I don't know if this will make it into 5.8.x or not.

    One other situation I don't see mentioned here that I think qualifies is freeing of a deeply nested structure (e.g. \\\\\\\...\\\\\\\\\\\\\$x).

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://532616]
Approved by pileofrogs
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (8)
As of 2014-08-23 13:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (173 votes), past polls