[Wellington-pm] Perl 5 faster than C

Douglas Bagnall douglas at paradise.net.nz
Tue Mar 14 19:27:51 PST 2006


Sam Vilain wrote:
> Douglas Bagnall wrote:
>>... with Memoize
>
> According to http://www.xgc.com/benchmarks/benchmarks.htm,

I found the idea here:

http://en.wikipedia.org/wiki/Ackermann_function#Use_as_benchmark

     For example, a compiler which, in analyzing the computation of
     A(3, 30), is able to save intermediate values like the A(3, n) and
     A(2, n) in that calculation rather than recomputing them, can
     speed up computation of A(3, 30) by a factor of hundreds of
     thousands.

btw, Wikipedia has a link to

http://shootout.alioth.debian.org/benchmark.php?test=ackermann&lang=all&sort=fullcpu

and from there a little program that memoises by poking results into
an array with '||=':

http://shootout.alioth.debian.org/benchmark.php?test=ackermann&lang=perl&id=3

------------
sub Ack {
     $_[0] ? ($Ack[$_[0]][$_[1]] ||= $_[1] ?
                       Ack($_[0]-1, Ack($_[0], $_[1]-1))
		    : Ack($_[0]-1, 1))
	: $_[1]+1;
}
------------

$ time perl ack-array.pl 11
Ack(3,11): 16381

real    0m0.202s
user    0m0.080s
sys     0m0.000s

(vs 0.8/0.8 for the Memoize version).

For people without built in perl parsers, $_[0] ? checks whether the
first parameter is zero or not.  If it isn't, it looks at
$Ack[$_[0]][$_[1]], which implicitly declares and indexes into a 2
dimensional array (@Ack).  ||= tests whether the indexed value is
there, and if not, fills it from the appropriate call to Ack.  If
$_[0] was zero, it evaluates the $_[1]+1.  In either case, the answer
found falls out the bottom as a return value.

Of course this is cheating, but that's what perl is for.

douglas




More information about the Wellington-pm mailing list