efficiency of recursion (stack level too deep)

[Chet Nichols III]

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

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

--
/*
Chet Nichols III
call: 703.310.9174
mail: (e-mail address removed)
aim: chet
*/

 

[Robert Klemme]

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!

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

 

[Rick DeNatale]

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

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

 

[Eric I.]

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.