Re: Ruby and recursion (Ackermann benchmark)

On 6/14/05, Austin Ziegler <[e-mail]> wrote:
> On 6/14/05, Phil Tomson <[e-mail]> 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 * [e-mail]
>                * Alternate: [e-mail]
> 
> 

Ok I realize that this (definitely) probably won't make it any faster
but could some clever hacker use callcc to implement a CPS version? It
would still technically be recursive, but should bypass the stack
(almost) entirely.