|
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. | [reply] |
|
|
| [reply]
[d/l] |
Re: What perl operations will consume C stack space?
by hv (Prior) on Feb 25, 2006 at 11:40 UTC
|
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 | [reply]
[d/l] |
|
|
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.
| [reply] |
|
|
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 | [reply]
[d/l] |
|
|
|
|
|
|
|
Re: What perl operations will consume C stack space?
by dave_the_m (Monsignor) on Feb 24, 2006 at 23:41 UTC
|
Traditionally, regexes fulfill this role.
Dave. | [reply] |
|
|
| [reply]
[d/l] |
|
|
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.
| [reply]
[d/l] |
|
|
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). | [reply] |
