tail.pl

#!/usr/bin/perl
use strict; use warnings;
use Benchmark qw/timethese cmpthese/;

sub recur {
    my $n = shift;
    if ($n) {
        return $n + recur($n-1);
    } else {
        return 0;
    }
}

sub tail {
    my ($n, $m) = @_;
    if ($n) {
        return tail($n-1, $n+($m||0));
    } else {
        return $m;
    }
}

sub tce {
    my ($n, $m) = @_;
    if ($n) {
        @_ = ($n-1, ($m||0)+$n);
        goto &tce;
    } else {
        return $m;
    }
}

sub iter {
    my $n = shift;
    my $m = 0;
    while ($n) {
        $m += $n--;
    }
    return $m;
}

use Test::More tests => 3;

my $h = recur (50);
my $i = tail  (50);
my $j = tce   (50);
my $k = iter  (50);

is ($h, $i, "sanity check ($h == $i)");
is ($i, $j, "sanity check ($i == $j)");
is ($j, $k, "sanity check ($j == $k)");

my $results = timethese( 100_000 => {
        recur   => sub { recur  (50) },
        tail    => sub { tail(50) },
        tce     => sub { tce(50) },
        iter    => sub { iter(50) },
    });
cmpthese($results);

__DATA__
1..3
ok 1 - sanity check (1275 == 1275)
ok 2 - sanity check (1275 == 1275)
ok 3 - sanity check (1275 == 1275)
Benchmark: timing 100000 iterations of iter, recur, tail, tce...
      iter:  1 wallclock secs ( 0.87 usr +  0.00 sys =  0.87 CPU) @ 114942.53/s (n=100000)
     recur:  4 wallclock secs ( 3.47 usr +  0.01 sys =  3.48 CPU) @ 28735.63/s (n=100000)
      tail:  4 wallclock secs ( 4.73 usr +  0.00 sys =  4.73 CPU) @ 21141.65/s (n=100000)
       tce: 11 wallclock secs (10.60 usr +  0.00 sys = 10.60 CPU) @ 9433.96/s (n=100000)
          Rate   tce  tail recur  iter
tce     9434/s    --  -55%  -67%  -92%
tail   21142/s  124%    --  -26%  -82%
recur  28736/s  205%   36%    --  -75%
iter  114943/s 1118%  444%  300%    --

# joel cites http://daerr.livejournal.com/15070.html