Tail recursion would be a great optimization to have, but Perl doesn't do it except through the clunky use of goto BLOCK;. And that doesn't appear to give any time optimization (admittedly, that p5p message could be long out of date).
I think you mean goto ⊂
#!perl
use strict;
use Benchmark;
sub normal {
return 0 unless $_[0];
@_ = ($_[0] - 1);
return normal(@_);
}
sub tail {
return 0 unless $_[0];
@_ = ($_[0] - 1);
goto &tail;
}
timethese( 10, {
"normal" => sub { normal(500000) },
"tail" => sub { tail(500000) },
}
);
Output:
normal: 25 wallclock secs (23.19 usr + 0.59 sys = 23.78 CPU) @ 0
+.42/s (n=10)
tail: 18 wallclock secs (17.44 usr + 0.03 sys = 17.47 CPU) @ 0
+.57/s (n=10
Not
very impressive, but there is a clear improvement in speed. The improvement in wallclock seconds becomes far larger if you start swapping with the normal recursive call (at my machine at 1_000_000 levels of recursion). I tried this only with 1 iteration because I got impatient:
#!perl
use strict;
use Benchmark;
sub normal {
return 0 unless $_[0];
@_ = ($_[0] - 1);
return normal(@_);
}
sub tail {
return 0 unless $_[0];
@_ = ($_[0] - 1);
goto &tail;
}
timethese( 1, {
"normal" => sub { normal(1000000) },
"tail" => sub { tail(1000000) },
}
);
output:
Benchmark: timing 1 iterations of normal, tail...
normal: 123 wallclock secs ( 6.58 usr + 1.13 sys = 7.71 CPU) @
+0.13/s (n=1)
(warning: too few iterations for a reliable count)
tail: 3 wallclock secs ( 3.50 usr + 0.01 sys = 3.51 CPU) @ 0
+.28/s (n=1)
(warning: too few iterations for a reliable count)
