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