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

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>

[download]

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.

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

    You can avoid magic stuff with a more cumbersome notation: 

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

    [download]

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

    ---
    demerphq

[reply]
[d/l]

      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>

      [download]
      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]
[d/l]

        Well, thats true I suppose but im not sure its entirely relevent, the tail recursion optimization only applies to subs which call themselves as the last statement. So insofar as the mutually recursive routines are tail recursive as well this optimization pattern still applies.

        For those that dont know, (not you BrowserUK) tail optimization is really only _important_ in languages without looping constructs, in any language with looping constructs its just a nice bonus.

        ---
        demerphq

[reply]
Re^6: Who's a thief? (No memory growth with magic goto)
by dragonchild (Archbishop) on Jan 14, 2005 at 19:59 UTC
    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.

[reply]
[d/l]

      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.
[reply]
        I've seen goto ⊂ ... I've never seen goto \⊂, which is what you did. Is there a difference?

        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.

[reply]
[d/l]
[select]

In Section Meditations