in reply to Re: Re: Pure Perl tail call optimization
in thread Pure Perl tail call optimization
Okay, you say that goto &SUB doesn't create a new stack frame, so let's test it shall we:
Run the code twice, one with tail as an arg, and one with nontail, here is what I get on Perl 5.6.1:#!/usr/bin/perl -w my $method = shift or usage(); if($method eq 'tail'){ $0 = 'tail'; tail_inf(); } elsif($method eq 'nontail'){ $0 = 'nontail'; nontail_inf(); } else { usage(); } sub tail_inf{ L1: print_resources(); goto L2; L2: goto L1; } sub nontail_inf{ goto &T1; sub T1{ print_resources(); goto &T2; } sub T2{ goto &T1; } } { my $i=0; my $j=0; sub print_resources{ $i++; $i = $i % 100000; return unless $i == 0; my @lines = grep {$_ =~ /\s+(\d+)/ and $1 eq $$} `ps u`; print @lines; $j++; exit if $j == 10; } } sub usage{ print "Usage: $0 tail|nontail\n"; exit(-1); }
Clearly, the nontail calls (goto &SUB) creates new stack frames while the goto LABEL doesn't.[334]: ./tail.pl tail abstract 5843 0.0 0.2 2324 1052 pts/0 S 01:00 0:00 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:01 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:01 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:02 tail abstract 5843 83.6 0.2 2328 1100 pts/0 S 01:00 0:02 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:03 tail abstract 5843 88.0 0.2 2328 1100 pts/0 S 01:00 0:03 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:04 tail abstract 5843 90.6 0.2 2328 1100 pts/0 S 01:00 0:04 tail abstract 5843 83.8 0.2 2328 1100 pts/0 S 01:00 0:05 tail [335]: ./tail.pl nontail abstract 5854 86.0 0.9 6300 5040 pts/0 S 01:00 0:00 nontail abstract 5854 85.5 1.7 10276 9056 pts/0 S 01:00 0:01 nontail abstract 5854 85.3 2.5 14244 13024 pts/0 S 01:00 0:02 nontail abstract 5854 85.7 3.3 18212 16996 pts/0 S 01:00 0:03 nontail abstract 5854 86.0 4.0 22184 20964 pts/0 S 01:00 0:04 nontail abstract 5854 85.8 4.8 26148 24928 pts/0 S 01:00 0:05 nontail abstract 5854 85.8 5.6 30116 28900 pts/0 S 01:00 0:06 nontail abstract 5854 85.7 6.3 34084 32868 pts/0 S 01:00 0:06 nontail abstract 5854 85.7 7.1 38056 36836 pts/0 S 01:00 0:07 nontail abstract 5854 85.9 7.9 42024 40808 pts/0 S 01:00 0:08 nontail
So, to *correctly* implement tail calls, I think goto &SUB is improper.
As for speed, and carrying this example, one can see that the tail call is faster than the nontail call:
However, in this example we have two functions calling each other, so perl might not optimize that.[340]: time ./tail.pl tail > /dev/null real 0m6.079s user 0m5.450s sys 0m0.620s [341]: time ./tail.pl nontail > /dev/null real 0m10.423s user 0m9.530s sys 0m0.890s
As for using computed values for goto (ie goto "label value", you can do a jump table. Basically, you have a segment of the code that looks something like this:
SCM_BRANCH: if($br eq 'SCM_F1'){ goto SCM_F1; } elsif ($br eq 'SCM_F2'){ goto SCM_F2; } ... SCM_F1: # before doing a call, set $rv to where you wanna go # and pass the name of where you want to return as first arg # ie: call F2 with args $a,$b; @_ = ('RET1', $a, $b); $br = 'SCM_F2'; goto SCM_BRANCH; # here we go RET1: # here we return my @returned_vals = @_; ... $br = $rp; goto SCM_BRANCH;
Update: I agree with samtregar that the reason might not be a creation of a new stack frame. I don't know if this is by design or a bug. However, goto LABEL does not leak: it can run forever juggeling from label to another and *can* be used to create proper tail recursion.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Re: Re: Re: Pure Perl tail call optimization
by samtregar (Abbot) on Apr 26, 2002 at 08:37 UTC |
In Section
Meditations