Ruby and recursion (Ackermann benchmark)

P

Phil Tomson

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).

Here's the benchmark code:

def ack(m, n)
if m == 0 then
n + 1
elsif n == 0 then
ack(m - 1, 1)
else
ack(m - 1, ack(m, n - 1))
end
end

NUM = Integer(ARGV.shift || 1)
print "Ack(3,", NUM, "): ", ack(3, NUM), "\n"


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.


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).

That brings up the question: why is Ruby so bad at recursion?
Is it possible to improve (and at what are the tradeoffs)?



Phil
 
A

Austin Ziegler

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).
Click to expand...

[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.
Click to expand...

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).
Click to expand...

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) =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?

-austin
--=20
Austin Ziegler * (e-mail address removed)
* Alternate: (e-mail address removed)
 
L

Logan Capaldo

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).
Click to expand...
=20
[snipped benchmark]
=20
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.
Click to expand...
=20
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:
=20
austin@austin:~$ time ack.rb 7
Ack(3,7): 1021
=20
real 0m1.258s
user 0m1.230s
sys 0m0.010s
=20
austin@austin:~$ ulimit -s 16384
austin@austin:~$ time ack.rb 8
Ack(3,8): 2045
=20
real 0m5.306s
user 0m5.250s
sys 0m0.030s
=20
austin@austin:~$ time ack.rb 9
Ack(3,9): 4093
=20
real 0m22.707s
user 0m22.520s
sys 0m0.150s
austin@austin:~$ ruby -v
ruby 1.8.2 (2005-03-10) [i686-linux]
=20
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:
=20
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
=20
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.)
=20
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.
=20
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).
Click to expand...
=20
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.
=20
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:
=20
# 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;
}
=20
All because it's "prettier but slower to do this":
=20
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));
}
=20
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?
=20
-austin
--
Austin Ziegler * (e-mail address removed)
* Alternate: (e-mail address removed)
=20
=20
Click to expand...

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.
 
A

Alan Chen

Austin said:
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?
Click to expand...

I think it depends on the purpose of the ackermann benchmark. If its
there to get a reading on how fast you perform a given algorithm
(ackermann) then eliminating the recursion would be entirely
appropriate. If its there to try to compare how well different
languages recurse, then its not really appropriate. Honestly, I think
its there to benchmark recursion performance by executing a known
complexity recursion algorithm. Although I would argue that Python and
Perl should be judged on both a "naive" and "optimized" ackermann
benchmarks.
 
P

Phil Tomson

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).
Click to expand...

[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.
Click to expand...

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
Click to expand...

Definately doesn't run for me on my laptop.
austin@austin:~$ ulimit -s 16384
austin@austin:~$ time ack.rb 8
Ack(3,8): 2045
Click to expand...

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.
Click to expand...

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).
Click to expand...

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;
}
Click to expand...

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?
Click to expand...

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
 
P

Pit Capitain

Christian Neukirchen said:
The real question is why the Ruby interpreter doesn't do tail-call
optimization...
Click to expand...

The interpreter doesn't do this automatically. You have to tell him :)

class TCOTest

# tail-recursive factorial
def fact( n, acc = 1 )
if n < 2 then acc else fact( n-1, n*acc ) end
end

# length of factorial
def fact_size( n )
fact( n ).size
rescue
$!
end

end

t = TCOTest.new

# normal method
puts t.fact_size( 10000 ) # => stack level too deep

# enable tail-call optimization
class TCOTest
tailcall_optimize :fact
end

# tail-call optimized method
puts t.fact_size( 10000 ) # => 14808


Here's the missing code, based on an idea from Sam Stephenson in
[ruby-talk:113700]

class Class
def tailcall_optimize( *methods )
methods.each do |meth|
org = instance_method( meth )
define_method( meth ) do |*args|
if Thread.current[ meth ]
throw( :recurse, args )
else
Thread.current[ meth ] = org.bind( self )
result = catch( :done ) do
loop do
args = catch( :recurse ) do
throw( :done, Thread.current[ meth ].call( *args ) )
end
end
end
Thread.current[ meth ] = nil
result
end
end
end
end
end

Note that this is just a proof of concept and hasn't been tested thoroughly.

Regards,
Pit
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

va_arg... recursion: changing arguments and the using recursion 8
TIEHANDLE and deep recursion 11
Few clarifications on recursion 9
Symbolic benchmark 83
Maximum stack depth 24
Fibonacci Benchmark Correction 25
Recursion and Ruby 16
efficiency of recursion (stack level too deep) 3

Members online

No members online now.
Total: 40 (members: 0, guests: 40)
Robots: 650

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,057
Latest member
KetoBeezACVGummies

Latest Threads

Top