in reply to Re: Re: Re: Recursion Alternatives?
in thread Recursion Alternatives?

I think the idea the OP was trying to touch on was that you can reduce the size and time of the stack by using some kind of "global" variable instead of passing everything by parameter. Pascal had a mechanism for this (nested subroutines) that C lacks, and that Perl more or less lacks. (Yes believe it or not there are one or two cooler features in Pascal than in C/Perl. ;-) This is also nice because with recursive routines you often want to have a "wrapper" sub that sets up the recursion (perhaps does argument checking and the other initialization) that then calls the "real" recursive sub. Since Perl doesnt have "real" nested subs (Broquaints efforts aside :-) you need to do it like this: 

sub inorder {
  my ($root)=@_;
  my $code;
  my @inorder;
  $code=sub {
             my $node=shift;
             $code->($node->left) if $node->left;
             push @inorder,$node->value;
             $code->($node->right) if $node->right;
            };
  $code->($root);
  return \@inorder;
}

[download]
Admittedly this example is so simple it probably doesnt deserve the extra treatment, but you can see my point in that it mimizes the amount of usage of the stack. We neither have to pass a reference into the sub to hold our results, nor utilize the much less efficient means of returning larger and larger lists to the calling sub. I've done a number of benchmarks using this approach with much less trivial recursion that this and the benefits were non-negligble. I also like it because it means that noone "accidentally" calls a sub intended for recursion that does not do argument checking on the pretense that the wrapper handles it already.

Dont get me wrong though, I agree that there is usually more benefit in writing an iterative solution than this approach (just having to _really_ think the problem through results in unforseen optimizations in my experience). The real question is whether its worth the effort when a reasonable middle ground is available. :-)

---
demerphq


Replies are listed 'Best First'.
Re: Re: Re: Re: Re: Recursion Alternatives?
by no_slogan (Deacon) on Mar 03, 2003 at 20:52 UTC
    ... you can reduce the size and time of the stack by using some kind of "global" variable instead of passing everything by parameter. Pascal had a mechanism for this (nested subroutines) that C lacks...

    If a nested subroutine refers to variables from an enclosing sub, it needs a pointer to the enclosing sub's stack frame. This means that the compiler is passing around an extra parameter that you don't see. No free lunch here.

    We neither have to pass a reference into the sub to hold our results, nor ...

    Correction: You don't have to pass a reference into the sub explicitly. Perl does it for you automatically. The mechanism for that might be a bit more efficient than using ordinary references, but that's not necessarily true beyond the current incarnation of Perl.

[reply]

      If a nested subroutine refers to variables from an enclosing sub, it needs a pointer to the enclosing sub's stack frame.

      Hmm. On reading your node I perused a bit of the literature on the subject, and I agree that you are generally correct. However to nitpick, if the outer sub is not visited from the inner, and we dont have to support threading then a single statically allocated pointer can be utilized without requiring additional room on the stack. When the outer sub is entered the pointer to the outer stack frame can be copied into the static memory, the inner sub knows the location of this memory (and the layout of the enclosing subs stack frame) at compile time, so can use it to access all extra data. Thus the overhead is reduced to a single "assignment", and not the expense of repeatedly passing the pointer on the stack.

      I guess however that in the general case nested subs actually represent the implicit definition of a struct, and the passing of a pointer to that struct when the inner sub is called. Which means that the effect can be easily simulated in perl/c. However I think the elegance of the Pascal approach, as well as the encapsulation it provides is quite nice. You dont have to worry that the inner sub could be called incorrectly, as it is only visible to the outer. Nor do you have to worry about what your structs look like, the compiler handles it all transparently.

      Correction: You don't have to pass a reference into the sub explicitly. Perl does it for you automatically. The mechanism for that might be a bit more efficient than using ordinary references, but that's not necessarily true beyond the current incarnation of Perl.

      No correction actually. The point was that this reference doen't need to be placed on the stack. It can be resolved once and then never again. Contrast this to the same pointer being on the stack many many times, the space it occupies and the operations required to add and remove it from the stack. From this I think its safe to assume that the closure approach will probably outperform the stack based approach in virtually all non-trivial applications. (This assumes the cost of doing the single initialization is reasonably close to the cost of transfering the data on the stack, reasonably being up to several times slower. An assumption I dont think is particularly unreasonable.) Maybe ill throw some benchmarks together to do a careful analysis of the costs involved (under the currently available version of perl.)

      Anyway, interesting points here. Thanks.

      ---
      demerphq


[reply]
[d/l]
        However I think the elegance of the Pascal approach, as well as the encapsulation it provides is quite nice.

        I missed nested functions when I switched from Pascal to C. (Gawd... that was 15 years ago. I feel so old.) That kind of procedural encapsulation seems to be out of style, though. Nowadays, if you want to keep people from calling your functions, you just make them private methods.

        The point was that this reference doen't need to be placed on the stack. It can be resolved once and then never again.

        I'm not sure I follow you here. Are you thinking that each instance of a closure gets a clone of the optree with the reference inserted in the right place? That doesn't seem to be the case, if I'm reading the Devel::Peek output right. It wouldn't be very efficient for large closures, either.

[reply]

In Section Meditations