>Date: Fri, 05 Apr 2013 20:23:30 -0400
>From: Uri Guttman <u...@stemsystems.com>
>To: boston-pm@mail.pm.org
>Subject: Re: [Boston.pm] Perl and recursion
>Message-ID: <515f6b02.70...@stemsystems.com>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>On 04/05/2013 08:13 PM, Adam Russell wrote:
>> I am currently in the midst of implementing a fairly non-trivial
>> recursive algorithm in Perl. The depth of the recursion is quite
>> large, so much so that I have set no warning recursion which warns
>> with a depth over 100. This seems pretty small to me! If the default
>> is to warn at a depth of 100 does this imply that Perl runs into
>> issues internally somewhere? A quick profiling via top does indeed
>> confirm what I consider an unusually large memory allocation when run
>> with inputs that force a depth of greater than a few hundred.
>> Googling did not provide much insight and in fact it seems only small
>> trivial examples are mainly discussed on this topic. Can anyone here
>> comment on what should be considered here?
>
><massive delete>
Ha! Sorry about that. The massive amount of quoted text was was caused by
uncareful use of email by phone.
>the depth of 100 to warn for deep recursion was sort of chosen
>arbitrarily. rarely do most recursive programs need to go that deep and
>then you can shut off the warning as you know. i read something on p5p
>very recently where some other thing was limited to 100 and the
>recursion depth warning was mentioned. they may be changing it to make
>it 1000. afaik, it wasn't due to ram usage but just a general warning
>that you might have infinite recursion happening.
Yes, that is what the docs say, a depth of 100 is a symptom of an infinite
recursion. This is just too low in many practical cases but, yes, it is
just a warning that can easily be turned off.
>as for your ram usage, all recursions can be unrolled into plain loops
>by managing your own stack. this is a classic way to save ram and sub
>call overhead. with perl it would be a fairly trivial thing to do. use
>an array for the stack and each element could be a hash ref containing
>all the data/args for that level's call. then you just loop and decide
>to 'recurse' or not. if you recurse you push a new hash ref onto the
>stack and loop. if you don't recurse you pop a value from the stack and
>maybe modify the previous top of the stack (like doing a return early in
>recursion). i leave the details to you. this would save you a ton of ram
>and cpu for each call if you go very deep and complex.
The initial implementation was of the algorithm from the literature as a
reference
and baseline. I do plan on eventually doing an iterative solution. I was just
curious about
why the had to be the case. I now understand the interpreter is storing lots of
info
at each level of recursion. What seems to be the case though is that when we
start going back
up the stack that memory doesn't seem to be released at each pop. If, say, at
max depth
500mb of ram has been allocated I don't see that released at any point except
for when
perl exits and then of course it is all released at once. Or at least that is
what
seems to happen.
_______________________________________________
Boston-pm mailing list
Boston-pm@mail.pm.org
http://mail.pm.org/mailman/listinfo/boston-pm
