Tail recursion using goto ⊂ (was: Re^3: Trinary Operator Semantics)

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) },
    }
);
[download]

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
[download]

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) },
    }
);
[download]

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)
[download]

"What should it profit a man, if he should win a flame war, yet lose his cool?"

Comment on Tail recursion using goto ⊂ (was: Re^3: Trinary Operator Semantics) Select or Download Code

Replies are listed 'Best First'.
Re: Tail recursion using goto ⊂ (was: Re^3: Trinary Operator Semantics) by Roy Johnson (Monsignor) on May 27, 2005 at 17:07 UTC
Oddly enough, "optimized" tail recursion is significantly slower than recursing the same way without the goto: `sub faster { return 0 unless $_[0]; @_ = ($_[0] - 1); &faster; }` [download] Using this test: `cmpthese( -10, { "normal" => sub { normal(50000) }, "tail" => sub { tail(50000) }, "faster" => sub { faster(50000) }, } );` [download] I got these results: `Rate normal tail faster normal 2.34/s -- -0% -41% tail 2.35/s 0% -- -41% faster 3.96/s 69% 68% --` [download] Caution: Contents may have been coded under pressure.	[reply] [d/l] [select]
Re^2: Tail recursion using goto ⊂ (was: Re^3: Trinary Operator Semantics) by demerphq (Chancellor) on May 27, 2005 at 17:59 UTC
Of course a loop is even faster... #!perl use strict; use Benchmark qw(cmpthese); my %counter; sub normal { return 0 unless $_[0]; @_ = ($_[0] - 1); $counter{(caller(0))[3]}++; return normal(@_); } sub tail { return 0 unless $_[0]; @_ = ($_[0] - 1); $counter{(caller(0))[3]}++; goto &tail; } sub faster { return 0 unless $_[0]; @_ = ($_[0] - 1); $counter{(caller(0))[3]}++; &faster; } sub loop { for (0..$_[0]) { $counter{(caller(0))[3]}++; } return 0; } cmpthese( -3, { "normal" => sub { normal(50000) }, "tail" => sub { tail(50000) }, "faster" => sub { faster(50000) }, "loop" => sub { loop(50000) }, } ); __END__ Rate normal tail faster loop normal 2.15/s -- -8% -18% -38% tail 2.35/s 9% -- -11% -32% faster 2.64/s 23% 12% -- -24% loop 3.45/s 60% 47% 31% -- [download] I put the caller thingee in there to ensure that the for loop didnt get optimized away. Which is in itself also a good argument for just using a loop in the first place. --- $world=~s/war/peace/g	[reply] [d/l]
Re^2: Tail recursion using goto ⊂ (was: Re^3: Trinary Operator Semantics) by Joost (Canon) on May 27, 2005 at 17:21 UTC
Wierd, though the tail version gets relatively more efficient if you increase the recursion level: `cmpthese( -10, { "normal" => sub { normal(500000) }, "tail" => sub { tail(500000) }, "faster" => sub { faster(500000) }, } );` [download] `s/iter normal tail faster normal 2.26 -- -22% -40% tail 1.77 28% -- -23% faster 1.36 66% 30% --` [download] "What should it profit a man, if he should win a flame war, yet lose his cool?"	[reply] [d/l] [select]