Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Perl: porters

[perl #40243] Interesting variation on 'Out of memory'

 

 

Perl porters RSS feed   Index | Next | Previous | View Threaded


perlbug-followup at perl

Aug 27, 2006, 3:21 AM

Post #1 of 4 (277 views)
Permalink
[perl #40243] Interesting variation on 'Out of memory'

# New Ticket Created by Andreas J Koenig
# Please include the string: [perl #40243]
# in the subject line of all future correspondence about this issue.
# <URL: http://rt.perl.org/rt3/Ticket/Display.html?id=40243 >


The following program comes from

http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=perl&id=0

It runs into 'Out of memory' when called with '11'. Now the
interesting bit is that I tried a variation with 5 separate printf
statements instead of the one in the last lines and with this
variation perl computed the correct output.

Can anybody explain the reason for this? I would like to write to the
shootout team and offer the version with the 5 printf statements, but
I'd like to add a few words of reasoning as to why this works better.

Here is the current version of the shootout that runs into 'Out of
memory' when called with argument '11':

# The Computer Language Shootout
# http://shootout.alioth.debian.org/
# recursive test, by Justin Ossevoort, Apr 03 2006

# This is the nice-"perlish" version

### Don't use warnings because at N=4 the Ack() method will
### start complaining about deep recursion (though it'll still
### function as expected)

use strict;
# use warnings;

sub Ack
{
my ($x, $y) = @_;

return $y + 1 if $x == 0;
return Ack($x - 1, 1) if $y == 0;

return Ack($x - 1, Ack($x, $y - 1));
}

sub Fib
{
my ($n) = @_;

return 1 if $n < 2;

return Fib($n - 2) + Fib($n - 1);
}

sub Tak
{
my ($x, $y, $z) = @_;

return Tak(Tak($x - 1.0, $y, $z), Tak($y - 1.0, $z, $x), Tak($z - 1.0, $x, $y)) if $y < $x;

return $z;
}

my $n = ($ARGV[0] || 0) - 1;
printf "Ack(%d,%d): %d\nFib(%.1f): %.1f\nTak(%d,%d,%d): %d\nFib(%d): %d\nTak(%.1f,%.1f,%.1f): %.1f\n",
3, $n + 1, Ack(3, $n + 1),
28.0 + $n, Fib(28.0 + $n),
$n * 3, $n * 2, $n, Tak($n * 3, $n * 2, $n),
3, Fib(3),
3.0,2.0,1.0, Tak(3.0,2.0,1.0);




And here is the last statement broken into 5 statements. This
variation does the computation correctly when called with '11':

printf "Ack(%d,%d): %d\n",
3, $n + 1, Ack(3, $n + 1);
printf "Fib(%.1f): %.1f\n",
28.0 + $n, Fib(28.0 + $n);
printf "Tak(%d,%d,%d): %d\n",
$n * 3, $n * 2, $n, Tak($n * 3, $n * 2, $n);
printf "Fib(%d): %d\n",
3, Fib(3);
printf "Tak(%.1f,%.1f,%.1f): %.1f\n",
3.0,2.0,1.0, Tak(3.0,2.0,1.0);


Thanks,
--
andreas


Summary of my perl5 (revision 5 version 9 subversion 4) configuration:
Platform:
osname=linux, osvers=2.6.16-2-k7, archname=i686-linux-64int
uname='linux k75 2.6.16-2-k7 #2 mon may 22 23:23:54 utc 2006 i686 gnulinux '
config_args='-Dprefix=/home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0 [at] 2876 -Dinstallusrbinperl=n -Uversiononly -Doptimize=-g -des -Duse64bitint -Dusedevel'
hint=recommended, useposix=true, d_sigaction=define
useithreads=undef, usemultiplicity=undef
useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
use64bitint=define, use64bitall=undef, uselongdouble=undef
usemymalloc=n, bincompat5005=undef
Compiler:
cc='cc', ccflags ='-DDEBUGGING -fno-strict-aliasing -pipe -Wdeclaration-after-statement -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
optimize='-g',
cppflags='-DDEBUGGING -fno-strict-aliasing -pipe -Wdeclaration-after-statement -I/usr/local/include'
ccversion='', gccversion='4.0.4 20060507 (prerelease) (Debian 4.0.3-3)', gccosandvers=''
intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=12345678
d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12
ivtype='long long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
alignbytes=4, prototype=define
Linker and Libraries:
ld='cc', ldflags =' -L/usr/local/lib'
libpth=/usr/local/lib /lib /usr/lib
libs=-lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc
perllibs=-lnsl -ldl -lm -lcrypt -lutil -lc
libc=/lib/libc-2.3.6.so, so=so, useshrplib=false, libperl=libperl.a
gnulibc_version='2.3.6'
Dynamic Linking:
dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
cccdlflags='-fpic', lddlflags='-shared -L/usr/local/lib'


Characteristics of this binary (from libperl):
Compile-time options: DEBUGGING PERL_DONT_CREATE_GVSV PERL_MALLOC_WRAP
USE_64_BIT_INT USE_LARGE_FILES USE_PERLIO
Locally applied patches:
patchaperlup: --branch='perl' --upto='28760' --start='17639'
Built under linux
Compiled at Aug 26 2006 05:26:33
@INC:
/home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0 [at] 2876/lib/5.9.4/i686-linux-64int
/home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0 [at] 2876/lib/5.9.4
/home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0 [at] 2876/lib/site_perl/5.9.4/i686-linux-64int
/home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0 [at] 2876/lib/site_perl/5.9.4
.


chromatic at wgz

Aug 28, 2006, 11:35 PM

Post #2 of 4 (259 views)
Permalink
Re: [perl #40243] Interesting variation on 'Out of memory' [In reply to]

On Sunday 27 August 2006 03:21, Andreas J Koenig wrote:

> sub Ack
> {
> my ($x, $y) = @_;
>
> return $y + 1 if $x == 0;
> return Ack($x - 1, 1) if $y == 0;
>
> return Ack($x - 1, Ack($x, $y - 1));
> }

I can't find the message now, but if I recall correctly, Dave Mitchell
explained that using highly-recursive calls like this without explicit
temporary variables means that Perl won't free the temps until much, much
later.

Unfortunately, I didn't document *that* in Perl Hacks #66, but if you want to
suggest memoization to the shootout folks, Perl looks a *lot* better.

-- c


andreas.koenig.gmwojprw at franz

Aug 29, 2006, 11:02 PM

Post #3 of 4 (267 views)
Permalink
Re: [perl #40243] Interesting variation on 'Out of memory' [In reply to]

>>>>> On Mon, 28 Aug 2006 23:35:14 -0700, chromatic <chromatic [at] wgz> said:

> On Sunday 27 August 2006 03:21, Andreas J Koenig wrote:
>> sub Ack
>> {
>> my ($x, $y) = @_;
>>
>> return $y + 1 if $x == 0;
>> return Ack($x - 1, 1) if $y == 0;
>>
>> return Ack($x - 1, Ack($x, $y - 1));
>> }

> I can't find the message now, but if I recall correctly, Dave Mitchell
> explained that using highly-recursive calls like this without explicit
> temporary variables means that Perl won't free the temps until much, much
> later.

Thanks!

> Unfortunately, I didn't document *that* in Perl Hacks #66, but if you want to
> suggest memoization to the shootout folks, Perl looks a *lot* better.

From reading their FAQ I'm sure they will not accept memoization but
maybe they will accept my variant. I'm gonna write them.

Thanks again,
--
andreas


andreas.koenig.7os6VVqR at franz

May 7, 2012, 6:40 PM

Post #4 of 4 (83 views)
Permalink
Re: [perl #40243] Interesting variation on 'Out of memory' [In reply to]

>>>>> On Mon, 07 May 2012 18:12:17 -0700, "James E Keenan via RT" <perlbug-followup [at] perl> said:

> Are there still issues here that warrant keeping this RT open?

No, please close it.

Thanks!
--
andreas

Perl porters RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.