Efficiency of recursion (stack level too deep)

Ruby
1

hi there-

so i started running into a problem using recursion with ruby- it seemed
a
little too soon for me to be getting a stack overflow (‘stack level too
deep
(SystemStackError)’), so i wrote up a quick simple script to do some
recursion:

#!/usr/local/bin/ruby

def print_depth num
puts num
print_depth(num+1)
end

print_depth 0

and sure enough, once im at a recursive depth of about 4,360, it errors
out.
i tried making num a global $num instead so it wasnt allocating memory
on
the stack each time for building a new ‘num’ object, but that only got
me to
about 4,500 until the overflow. to me, it seems a little low, especially
for
something this simple. my stack size is 10240. and, of course, when i up
it
to something like 20480, i get about double the recursive depth… but
when i
try the same thing in C:

#include <stdio.h>

void print_depth(int num);

int main() {
print_depth(0);
}

void print_depth(int num) {
printf("%d\n",num);
print_depth(++num);
}

i get a recursive depth of about 350,000 before it bombs out (which is
what
i’d expect more or less). i know C is super efficient and all, and ruby
is
truly object oriented, so each thing pushed on the stack is an object
with
its own set of methods, etc, so its by design going to take up more
space,
but i was wondering if there are any plans to do anything to help the
efficiency of this at all?

to be honest, i’ve only been using ruby for about a week now, and i
totally
love it. so, this e-mail really isn’t a complaint at all, just more of a
question. if there’s already an answer (which there probably is), feel
free
to shout it out- i love everything i’ve seen and done so far with the
language, so the more i know about it, the better! hope to hear from
someone
soon- thanks!

chet

2

2007/11/14, Chet Nichols III [email protected]:

def print_depth num
about 4,500 until the overflow. to me, it seems a little low, especially for
print_depth(0);
truly object oriented, so each thing pushed on the stack is an object with
its own set of methods, etc, so its by design going to take up more space,
but i was wondering if there are any plans to do anything to help the
efficiency of this at all?

to be honest, i’ve only been using ruby for about a week now, and i totally
love it. so, this e-mail really isn’t a complaint at all, just more of a
question. if there’s already an answer (which there probably is), feel free
to shout it out- i love everything i’ve seen and done so far with the
language, so the more i know about it, the better! hope to hear from someone
soon- thanks!

You’ll find it in the archives. This issue comes up frequently.
Basically Ruby is not good at recursion for exactly the reason you
discovered.

Cheers

robert

3

On Nov 14, 2007 10:33 AM, Robert K. [email protected]
wrote:

2007/11/14, Chet Nichols III [email protected]:

print_depth(num+1)
to something like 20480, i get about double the recursive depth… but when i
try the same thing in C:
…

i get a recursive depth of about 350,000 before it bombs out (which is what
i’d expect more or less). i know C is super efficient and all, and ruby is
truly object oriented, so each thing pushed on the stack is an object with
its own set of methods, etc, so its by design going to take up more space,
but i was wondering if there are any plans to do anything to help the
efficiency of this at all?

You’ll find it in the archives. This issue comes up frequently.
Basically Ruby is not good at recursion for exactly the reason you
discovered.

Actually this is a problem with ruby, the implementation, rather than
Ruby the language.

Two comments.

  1. Just this morning I listened to a podcast interview with Evan
    Phoenix and the differences between the invocation stacks in MRI and
    rubinius was discussed. Evan brought up something I hadn’t thought
    about. Because of the way MRI is implemented each Ruby method call
    will result in multiple C stack frames, so you need to multiply the
    recursion depth of that ruby program by some number to get the
    equivalent C stack depth.

  2. There’s no good reason why a Ruby implementation couldn’t do
    tail-recursion optimization on the program in question, which would
    make that program much closer to an IDEAL infinite loop (i.e. one
    which would run out of non-cpu cycle resources much more slowly )

–
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

4

On Nov 13, 10:49 pm, Chet Nichols III [email protected] wrote:

i get a recursive depth of about 350,000 before it bombs out (which is what
i’d expect more or less). i know C is super efficient and all, and ruby is
truly object oriented, so each thing pushed on the stack is an object with
its own set of methods, etc, so its by design going to take up more space,
but i was wondering if there are any plans to do anything to help the
efficiency of this at all?

Your wording seems to imply that you believe that each object has its
own copy of all of its class’ methods. Although Ruby does allows you
to add a method to a specific instance (the so-called “singleton
method”), in general all instances of a class share one “copy” of the
method. Each instance only needs to maintain its instance variables.

Furthermore, objects, in general, tend to be stored on the heap, not
the stack. References to the object may be stored on the stack. Ruby
has some optimizations, such that Fixnums are handled in a special way
and do appear on the stack. But they take the same amount of space as
a reference anyway.

So as far as the Ruby call stack is concerned. Rich DeNatale’s post
in this thread is probably more accurate at describing why MRI (Matz’s
Ruby implementation) has this problem. Other Ruby implementations,
such as Rubinius, likely will not.

Eric

====

Interested in hands-on, on-site Ruby training? See http://LearnRuby.com
for information about a well-reviewed class.