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:
> 
> import sys
> sys.setrecursionlimit(5000000)
> 
> ....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

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

  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. 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;
    }

All because it's "prettier but slower to do this":

    sub Ack {
        my($M, $N) = @_;
        return( $N + 1 )         if ($M == 0);
        return( Ack($M - 1, 1) ) if ($N == 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?

-austin
-- 
Austin Ziegler * halostatue / gmail.com
               * Alternate: austin / halostatue.ca