In article <9e7db91105061411595a036a81 / mail.gmail.com>,
Austin Ziegler  <halostatue / gmail.com> wrote:
>On 6/14/05, Phil Tomson <ptkwt / aracnet.com> wrote:
>> Amidst all of the discussion about the alioth benchmarks and how
>> they are (insert disparaging term here) there was a little
>> discussion about the Ackermann benchmark and how Ruby finishes
>> dead last even behind gawk(in fact doesn't finish for values of N
>> larger than 6).
>
>[snipped benchmark]
>
>> Well, that's simple enough. Nothing to improve there and
>> essentially looks like the Python version, except that the python
>> version includes:
>>=20
>> import sys
>> sys.setrecursionlimit(5000000)
>>=20
>> ....kind of handy that they can do that from within their program.
>
>This is a bit of a cheat, IMO, to do this within Python. I suspect
>that it could be done within Ruby, but I think that Matz had
>indicated that this is more appropriately an operating system
>function. Indeed:
>
>  austin@austin:~$ time ack.rb 7
>  Ack(3,7): 1021
>
>  real    0m1.258s
>  user    0m1.230s
>  sys     0m0.010s
>

Definately doesn't run for me on my laptop.

>  austin@austin:~$ ulimit -s 16384
>  austin@austin:~$ time ack.rb 8
>  Ack(3,8): 2045
>

Doesn't work either.

>  real    0m5.306s
>  user    0m5.250s
>  sys     0m0.030s
>
>  austin@austin:~$ time ack.rb 9
>  Ack(3,9): 4093
>
>  real    0m22.707s
>  user    0m22.520s
>  sys     0m0.150s
>  austin@austin:~$ ruby -v
>  ruby 1.8.2 (2005-03-10) [i686-linux]
>
>Thus, by changing ulimit in the user level, I can do the Ackermann
>test. That is a linode, by the way, with 96 Mb of memory. Comparing
>like to like, I get:
>
>            7       8       9
>Python      0.643   3.071   11.519
>Python-s    DNF     DNF     DNF
>Python-u    DNF     DNF     DNF
>Ruby        1.234   DNF     DNF (1933 levels)
>Ruby-u      1.210   5.319   23.275
>Perl        0.835   3.659   20.935
>
>Python-s removes the setrecursion limit; Python-u does the same but
>changes ulimit. IN REALITY, we see that Python -- without this
>setting change -- can't even finish Ack(3,7). (The variance in the
>test table above and my earlier results is that they were run at
>different times.)
>
>Ruby, on the other hand, does finish it with this OS setting.

Again, not on my box.  Ruby 1.8.2, Debian linux, PIII 650 256MB RAM.  It 
would appear to be very sensitive to the kind of machine you're running 
on (not surprising, of course).

On my desktop machine I just tried it and found that it would finish for 
7 without changing the ulimit, but not for 8.  I then set the ulimit as 
you did above and it finished for both 8 and 9.

> I
>suspect that the stack frames (bindings) in Ruby are larger, which
>explains the speed difference to some degree. Could Ruby be faster?
>We're pretty competitive with Perl there. Probably. I wouldn't know
>the first thing about speeding it up -- or if we really need to.
>
>> So the conclusion is that Ruby isn't so great at recursion (not a
>> new conclusion). If you're looking for a language that's good for
>> recursion (because you like that style of programming or whatever)
>> then looking at the results of this benchmark would be
>> informative. You could tell right away that Ruby isn't a good
>> choice for that style of programming. One might dismiss this by
>> saying "well, I never use recursion anyway", but a lot of
>> algorithms are much easier to implement recusively (algorithms
>> which deal with walking trees for example).
>
>But it would be an incorrect assumption -- remember, I changed a
>userspace OS-level value from 8192 (the default stack size in
>kilobytes) to 16384, and was able to do ack(3,9). It blew up on
>ack(3, 10) -- but I can't change the stack any larger. However, we
>went from blowing up around 1500 levels to 4500 levels of recursion.
>
>This is *part* of the reason that I have significant issues with the
>alioth shootout. They don't take any responsibility for these
>numbers or understanding the nature of problems -- and seem to be
>proud of it. They've accepted a Perl version that goes for fast-and-
>ugly:
>
>        # in our quest for speed, we must get ugly:
>        # it helps reduce stack frame size a little bit
>        # from Leif Stensson
>    sub Ack {
>        return $_[0] ? ($_[1] ? Ack($_[0]-1, Ack($_[0], $_[1]-1))
>                : Ack($_[0]-1, 1))
>            : $_[1]+1;
>    }
>

Well, could we do something similar?  If it's allowed, then why not? It's 
still tesing recursion.

>All because it's "prettier but slower to do this":
>
>    sub Ack {
>        my($M, $N) =3D @_;
>        return( $N + 1 )         if ($M =3D=3D 0);
>        return( Ack($M - 1, 1) ) if ($N =3D=3D 0);
>        Ack($M - 1, Ack($M, $N - 1));
>    }
>
>IMO, this is completely inappropriate. If the Perlers are going to
>do things to reduce their stack frames, and the Pythonistas are
>going to muck around with recursion limits that help their code run
>at all ... why can't Rubyists reduce or eliminate the recursion
>entirely?

We could try to submit an iterative version and see if it gets accepted 
;-)

If we could 'muck around with recusion limits' as they do in Python, then 
we should put that in the benchmark code.  But I don't think there is any 
'built-in' way of doing this.


Phil