efficiency of recursion (stack level too deep)

Discussion in 'Ruby' started by Chet Nichols III, Nov 14, 2007.

  1. 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:
    aim: chet
    */
     
    Chet Nichols III, Nov 14, 2007
    #1
    1. Advertising

  2. 2007/11/14, Chet Nichols III <>:
    > 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

    --
    use.inject do |as, often| as.you_can - without end
     
    Robert Klemme, Nov 14, 2007
    #2
    1. Advertising

  3. On Nov 14, 2007 10:33 AM, Robert Klemme <> wrote:
    > 2007/11/14, Chet Nichols III <>:


    > > 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:

    ...

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


    --
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
     
    Rick DeNatale, Nov 14, 2007
    #3
  4. Chet Nichols III

    Eric I. Guest

    On Nov 13, 10:49 pm, Chet Nichols III <> 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.
     
    Eric I., Nov 14, 2007
    #4
    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. Eric Schwartz

    stack level too deep on ia64

    Eric Schwartz, Nov 10, 2003, in forum: Ruby
    Replies:
    3
    Views:
    158
    Eric Schwartz
    Nov 11, 2003
  2. Jesper Olsen
    Replies:
    7
    Views:
    575
    Van Jacques
    Jan 16, 2004
  3. Jean-Hugues ROBERT

    yaml, level too deep, stack error

    Jean-Hugues ROBERT, Apr 27, 2004, in forum: Ruby
    Replies:
    1
    Views:
    129
    why the lucky stiff
    Apr 27, 2004
  4. E.-R. Bruecklmeier

    [Q] YAML Error: stack level too deep

    E.-R. Bruecklmeier, Jul 6, 2004, in forum: Ruby
    Replies:
    4
    Views:
    203
    haldane
    Jul 6, 2004
  5. Sam Roberts
    Replies:
    1
    Views:
    227
    Yukihiro Matsumoto
    Feb 11, 2005
Loading...

Share This Page