Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^4: Who's a thief? (recursion limitations)

by Ovid (Cardinal)
on Jan 14, 2005 at 18:47 UTC ( #422344=note: print w/replies, xml ) Need Help??


in reply to Re^3: Who's a thief? (recursion limitations)
in thread Who's a thief? -- the follow up

As soon as I tried your "deep" program, I immediately got a "deep recursion" error. I've a 1.6 GHz machine with 640 megs of RAM. I don't know how you could have run that. Every time Perl enters a sub (normally), it creates a new stack frame and this quickly eats memory.

On my machine, it pretty much ground the box to a halt after about 1.5 million iterations.

Cheers,
Ovid

New address of my CGI Course.

  • Comment on Re^4: Who's a thief? (recursion limitations)

Replies are listed 'Best First'.
Re^5: Who's a thief? (No memory growth with magic goto)
by BrowserUk (Pope) on Jan 14, 2005 at 19:16 UTC

    If you can arrange your algorithm to be tail recursive, and use the magic form of goto, you can cut the memory growth to zero and achieve some very impressive figures.

    8 seconds for 10 million recursions and 83 seconds for 100 million with the memory consumption never over 1.5 MB.

    #!/usr/bin/perl -w use strict; $|++; my $count; deep( $ARGV[ 0 ] ); print $count; sub deep { ++$count and --$_[ 0 ] and goto \&deep; } __DATA__ [19:09:45.02] P:\test>422344 10000000 10000000 [19:09:53.02] P:\test> [19:10:03.21] P:\test>422344 100000000 100000000 [19:11:26.84] P:\test>

    It takes a little effort to do, but when you need it it is worth it.


    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.

      You can avoid magic stuff with a more cumbersome notation:

      sub deep {SUB:{ ++$count and --$_[ 0 ] and redo SUB; }}

      Which is actually going to be faster afaik. (Havent tested though)

      ---
      demerphq

        Yes, that does appear to be (crudely measured) about twice as fast, though it wouldn't work for mutally recursive subs.

        #!/usr/bin/perl -w use strict; $|++; my $count; deep( $ARGV[ 0 ] ); print $count; sub deep {SUB:{ ++$count and --$_[ 0 ] and redo SUB; }} #sub deep { # ++$count and --$_[ 0 ] and goto \&deep; #} __DATA__ [20:54:56.63] P:\test>422344 10000000 10000000 [20:54:59.48] P:\test>422344 [20:55:17.40] P:\test>422344 100000000 100000000 [20:55:41.24] P:\test>

        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
      I've never seen doing a goto to a reference of a named subroutine. Does this really get around the non-tail-recursive nature of goto &deep;?

      Being right, does not endow the right to be rude; politeness costs nothing.
      Being unknowing, is not the same as being stupid.
      Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
      Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

        From perlsyn:

        The goto-&NAME form is highly magical, and substitutes a call to the named subroutine for the currently running subroutine

        Limbic~Region's post referenced a post by TimToady which will give the real skinny of how it works, but it does avoid the stack growth at the penalty of requiring the programmer to arrange for the algorithm to be tail-recursive.

        You can use closures to provide yourself with one or more "stacks" if that is required. By controlling what gets stacked and when, even some non-tail recursive algorithms can benefit from reduced memory consumption and greater speed. It is especially useful for mutually recursive algorithms that need to share intermediate results.

        That takes some effort, but if you have an inherently recursive algorithm that lends itself to that process, and a need for speed, then it can be worth it.


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re^5: Who's a thief? (recursion limitations)
by Limbic~Region (Chancellor) on Jan 14, 2005 at 19:27 UTC
    Ovid,
    Every time Perl enters a sub (normally), it creates a new stack frame and this quickly eats memory.

    Presumably, you are referring to &sub as the abnormal example where you could use goto &sub to bypass the recursion limit as seen in the following example:

    #!/usr/bin/perl use strict; use warnings; print sum( 1000 ); sub sum { my ($num, $tot) = @_; return $tot if ! $num; @_ = ($num - 1, $tot += $num); goto ∑ }
    According to TimToady, this actually does create a new stack, but only after the old one is stripped off. Of course you could always ignore the warning, turn off the 'recursion' warning, or recompile Perl to avoid the warning. In practice, I have never needed this kind of technique because it seems that iterative solutions aren't that difficult to come up with. In this case, the formula (n^2 + n) / 2 would do the trick.

    And as I am previewing this, I see BrowserUk has already said something similar - oh well.

    Cheers - L~R

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (13)
As of 2019-10-17 15:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?