Ruby and recursion (Ackermann benchmark)

Discussion in 'Ruby' started by Phil Tomson, Jun 14, 2005.

  1. Phil Tomson

    Phil Tomson Guest

    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
    Phil Tomson, Jun 14, 2005
    #1
    1. Advertising

  2. On 6/14/05, Phil Tomson <> 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

    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) =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 *
    * Alternate:
    Austin Ziegler, Jun 14, 2005
    #2
    1. Advertising

  3. On 6/14/05, Austin Ziegler <> wrote:
    > On 6/14/05, Phil Tomson <> 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).

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

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

    >=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 *
    > * Alternate:
    >=20
    >=20


    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.
    Logan Capaldo, Jun 14, 2005
    #3
  4. Phil Tomson

    Alan Chen Guest

    Austin Ziegler wrote:
    > On 6/14/05, Phil Tomson <> wrote:
    >
    > 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?


    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.
    Alan Chen, Jun 14, 2005
    #4
  5. Phil Tomson

    Isaac Gouy Guest

    Alan Chen wrote:
    -snip-
    > Although I would argue that Python and Perl should be judged on both a "naive"
    > and "optimized" ackermann benchmarks.


    Me too.
    Isaac Gouy, Jun 14, 2005
    #5
  6. Phil Tomson

    Phil Tomson Guest

    In article <>,
    Austin Ziegler <> wrote:
    >On 6/14/05, Phil Tomson <> 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
    Phil Tomson, Jun 14, 2005
    #6
  7. On 6/15/05, Christian Neukirchen <> wrote:

    > Please don't try to copy Forth, that is a bad idea in general. :)


    > Christian Neukirchen <> http://chneukirchen.org
    >=20
    >=20


    you do-whatever-mean?
    ok.

    ;-)
    Logan Capaldo, Jun 15, 2005
    #7
  8. Phil Tomson

    Pit Capitain Guest

    Christian Neukirchen <chneukirchen <at> gmail.com> writes:
    > The real question is why the Ruby interpreter doesn't do tail-call
    > optimization...


    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
    Pit Capitain, Jun 16, 2005
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    435
  2. Michael Gebhart

    Benchmark Mono - Ruby

    Michael Gebhart, Feb 6, 2005, in forum: Ruby
    Replies:
    19
    Views:
    216
    Michael Gebhart
    Feb 8, 2005
  3. \

    python/ruby benchmark.

    \, Jun 9, 2005, in forum: Ruby
    Replies:
    52
    Views:
    521
    Ralph \PJPizza\ Siegler
    Jun 16, 2005
  4. Isaac Gouy
    Replies:
    0
    Views:
    94
    Isaac Gouy
    Nov 30, 2005
  5. Replies:
    8
    Views:
    715
    John Reye
    Apr 26, 2012
Loading...

Share This Page