From @andk

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@​28760 -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@​28760/lib/5.9.4/i686-linux-64int
  /home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0@​28760/lib/5.9.4
  /home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0@​28760/lib/site_perl/5.9.4/i686-linux-64int
  /home/src/perl/repoperls/installed-perls/perl/pUBNkHZ/perl-5.8.0@​28760/lib/site_perl/5.9.4
  .

From chromatic@wgz.org

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

The RT System itself - Status changed from 'new' to 'open'

From @davidnicol

Based on my understanding "tail recursion" from studying scheme in
computer science class, the way it could be implemented in Perl would
be to change the call convention from the way it is now, which as I
understand it is that the returned value(s) are put on the stack at the
same co-ordinates where the parameters arrived, to a convention in
which the L-value that is to receive the result is passed as an argument,
not as an argument accessible in @​_ but as a behind-the-scenes argument,
so instead of C<return> copying its args to the stack, replacing all the
aliases in @​_, C<return> would copy its args to the destination l-value.

Big question​: how to introduce tail recursion without completely breaking
all current XS code that uses the current calling convention?

sub Ack

imagine rewriting C<$res=Ack($ping)> as C<TRdispatch($res, \&Ack, $ping)>

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

      return $y \+ 1         if $x == 0\{

;

determine the result of ($y+1), roll back the stack, then assign that
result to $res

      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

--
David L Nicol
Dickenson on the flag
http​://cronos.advenge.com/pc/EmilyDickenson/SecondBook/p39.html

From @davidnicol

stupid gmail keyboard shortcuts...

imagining what would be involved in implementing tail recursion, continued

  sub Ack

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

  if ($x == 0){
  return $y + 1 # make a new scratchpad with $y and 1 on it,
  # roll back the stack,
  # call the plus routine with the
arguments from
  # the scratchpad, and the l-value, and the
  # next op after we return, so the return is
  # directly from the plus
  };
  if ($y = 0){
  return Ack($x - 1, 1) # this is the case where
tail-recursion means we
  # don't have to burn up
stack. Instead of
  # extending the stack and
copying the results
  # as it finally rewinds after
we're done, the slot
  # for the result and the
return point are passed
  # to the called functions as
behind-the-scenes
  # parameters.
  };

  return Ack($x - 1, Ack($x, $y - 1));
  # this case is not helped as much by TR. Although the first
  # Ack function can be passed the extended function
call context
  # info and tail-recurse, the second one must complete before
  # the first one can launch. with a TR call convention, the
  # second one would be launched by specifying a temporary
  # in the new scratch pad (the "launch pad" if you will) as
  # the result slot, and an op within the sequence of
lining up the first
  # call as its return point.
  }

This concludes my discussion of how implementing tail recursion would help
the situation of mucho memory use in deeply recursive operations.

From @iabyn

On Tue, Aug 29, 2006 at 02​:00​:28PM -0500, David Nicol wrote​:

This concludes my discussion of how implementing tail recursion would help
the situation of mucho memory use in deeply recursive operations.

David, I'm going to blunt...

I get the impression that most of your postings on ways to improve upon
perl's internals go along the lines of​:

1) make up some fantasy scheme of how perl's internals *might* work in
some universe
2) don't check the src to see if your fantasy bears any relation to
reality
3) propose in a vague hand-wavy way how this fantasy model might be
improved upon
4) Sit back and wait for someone else to produce a patch
5) no patch is forthcoming
6) goto 1

A far as I can see, this wastes everyone's time for little if any
productive gain.

--
Red sky at night - gerroff my land!
Red sky at morning - gerroff my land!
  -- old farmers' sayings #14

From @andk

On Mon, 28 Aug 2006 23​:35​:14 -0700, chromatic <chromatic@​wgz.org> 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

From @jkeenan

On Tue Aug 29 23​:02​:54 2006, andreas.koenig.gmwojprw@​franz.ak.mind.de wrote​:

On Mon, 28 Aug 2006 23​:35​:14 -0700, chromatic
<chromatic@​wgz.org> 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.

Andreas​:

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

Thank you very much.
Jim Keenan

From @andk

On Mon, 07 May 2012 18​:12​:17 -0700, "James E Keenan via RT" <perlbug-followup@​perl.org> said​:

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

No, please close it.

Thanks!
--
andreas

@cpansprout - Status changed from 'open' to 'resolved'