Professional Web Applications Themes

Bignums and return - Ruby

Hello I was doing some testing with two factorial funtions: def fact1(n) if n == 0 1 else n * fact1(n-1) end end with this one, I can go up to fact1(1970) (or fact1(1191) with '--enable-pthread'). After that, I get a "stack level too deep" error. The second funtion, below, just adds explicit "return"s: def fact2(n) if n == 0 return 1 else return n * fact2(n-1) end end With this one, I can only go up to fact2(1376) (or up to fact2(841) with '--enable-pthread'), getting the same error as above after that. Why does an explicit 'return' or compiling ...

  1. #1

    Default Bignums and return

    Hello

    I was doing some testing with two factorial funtions:

    def fact1(n)
    if n == 0
    1
    else
    n * fact1(n-1)
    end
    end

    with this one, I can go up to fact1(1970) (or fact1(1191) with
    '--enable-pthread'). After that, I get a "stack level too deep" error.

    The second funtion, below, just adds explicit "return"s:

    def fact2(n)
    if n == 0
    return 1
    else
    return n * fact2(n-1)
    end
    end

    With this one, I can only go up to fact2(1376) (or up to fact2(841) with
    '--enable-pthread'), getting the same error as above after that.

    Why does an explicit 'return' or compiling ruby with --enable-pthreads
    changes the behaviour?


    Also, I'm really puzzled by this one: if I put the two functions on the
    *same file*, fact2(1377) (or fact2(842) with '--enable-pthread') will
    give the following error: "Bignum can't be coerced into Fixnum" instead
    of the "stack level too deep" one.

    Why do I get these different errors?

    $ ruby -v
    ruby 1.8.1 (2003-12-25) [i686-linux]

    Best regards,
    Andre



    Andre Guest

  2. #2

    Default Re: Bignums and return

    >>>>> "A" == Andre Nathan <com.br> writes:

    A> Why do I get these different errors?

    the short answer : you don't want to know.

    A> Why does an explicit 'return' or compiling ruby with --enable-pthreads
    A> changes the behaviour?

    Adding an explicit return, add a function call. This is why ruby detect
    quickly the stack overflow. --enable-pthreads modify internally the calls,
    and this explain also the difference.

    A> Also, I'm really puzzled by this one: if I put the two functions on the
    A> *same file*, fact2(1377) (or fact2(842) with '--enable-pthread') will
    A> give the following error: "Bignum can't be coerced into Fixnum" instead
    A> of the "stack level too deep" one.

    When ruby try to convert to a Fixnum it do

    begin
    # try the conversion
    rescue
    raise "Bignum can't be coerced into Fixnum"
    end

    if it detect the stack overflow when it's in the begin..rescue it will
    give the error "Bignum can't be coerced into Fixnum".

    If it detect the stack overflow outside the begin...rescue it give 'stack
    level too deep'

    This is the same error, but ruby give 2 different messages (because it's
    in a begin...rescue)


    Guy Decoux





    ts Guest

  3. #3

    Default Re: Bignums and return

    On Thu, 2004-01-29 at 12:38, ts wrote: 

    Thanks for the explanation, Guy :)

    Are there any plans to implement return as an operator, instead of a
    function?


    Andre



    Andre Guest

  4. #4

    Default Re: Bignums and return

    >>>>> "A" == Andre Nathan <com.br> writes:

    A> Are there any plans to implement return as an operator, instead of a
    A> function?

    Well, this is a *C* function call which is added, return is like an operator
    and not like a ruby method.

    Trying to correct this is like trying to correct the error 'stack level
    too deep', actually ruby has some limits for its stack.


    Guy Decoux





    ts Guest

  5. #5

    Default Re: Bignums and return

    On Thu, 29 Jan 2004 22:41:42 +0900, Andre Nathan <com.br>
    wrote:
     

    Well, I'm guessing that the behaviour without the explicit returns is
    equivalent to:

    return (
    if n == 0
    1
    else
    n * fact1(n-1)
    end
    )

    Wanna try that one, instead?

    --
    Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
    Jason Guest

  6. #6

    Default Re: Bignums and return

    On Fri, 2004-01-30 at 05:20, Jason Hutchens wrote: 

    That gives me the same results the explicit return version gave me.

    Andre



    Andre Guest

  7. #7

    Default Re: Bignums and return

    >>>>> "A" == Andre Nathan <com.br> writes:

    A> That gives me the same results the explicit return version gave me.

    Well, here the explanation

    svg% ruby -rii -e 'dump; def a() return a; end; def b() b; end'
    eval_tree
    BLOCK
    NEWLINE <-e:1>
    VCALL dump
    NEWLINE <-e:1>

    DEFN a
    SCOPE
    BLOCK
    ARGS
    NEWLINE <-e:1>
    RETURN
    VCALL a

    NEWLINE <-e:1>

    DEFN b
    SCOPE
    BLOCK
    ARGS
    NEWLINE <-e:1>
    VCALL b


    svg%


    because there is an explicit return, ruby has added a NODE RETURN (which
    call rb_eval()).

    When ruby call the method #a it will use more stack (there is one more
    call) than when it call the method #b


    Guy Decoux


    ts Guest

  8. #8

    Default Re: Bignums and return

    On Fri, Jan 30, 2004 at 08:05:03PM +0900, ts wrote: 

    Does Ruby not have even a basic peephole optimizer?
    It seems like "def one; return 1 end" and "def one; 1 end;" should
    result in identical bytecode.

    -Mark
    Mark Guest

  9. #9

    Default Re: Bignums and return

    >>>>> "M" == Mark J Reed <com> writes:

    M> It seems like "def one; return 1 end" and "def one; 1 end;" should
    M> result in identical bytecode.

    actually ruby don't use bytecode.


    Guy Decoux




    ts Guest

  10. #10

    Default Re: Bignums and return

    On Sat, Jan 31, 2004 at 10:26:46PM +0900, ts wrote: [/ref]
    >
    > M> It seems like "def one; return 1 end" and "def one; 1 end;" should
    > M> result in identical bytecode.
    >
    > actually ruby don't use bytecode.[/ref]

    previous.gsub('bytecode', 'trees')

    or whatever the internal compiled representation is, then. (But Rite
    will use a byte code, right?)

    Anyway, the point is that any extra code inserted by the "return"
    should be optimized out when the return doesn't do anything.

    -Mark
    Mark Guest

  11. #11

    Default peephole optimization (Re: Bignums and return)

    Hi,

    At Sun, 1 Feb 2004 01:04:52 +0900,
    Mark J. Reed wrote: 

    Not yet.


    * p.y (remove_return): remove tail returns. [ruby-talk:90934]


    Index: p.y
    ================================================== =================
    RCS file: /cvs/ruby/src/ruby/p.y,v
    retrieving revision 1.314
    diff -u -2 -p -r1.314 p.y
    --- p.y 2 Feb 2004 13:06:35 -0000 1.314
    +++ p.y 2 Feb 2004 13:07:19 -0000
    -120,4 +120,5 static NODE *remove_begin();
    #define value_expr(node) value_expr0((node) = remove_begin(node))
    #define void_expr(node) void_expr0((node) = remove_begin(node))
    +static void reduce_nodes();

    static NODE *block_append();
    -365,5 +366,10 bodystmt : compstmt
    }
    if ($4) {
    - $$ = NEW_ENSURE($$, $4);
    + if ($$) {
    + $$ = NEW_ENSURE($$, $4);
    + }
    + else {
    + $$ = block_append($4, NEW_NIL());
    + }
    }
    fixpos($$, $1);
    -1650,5 +1656,7 primary : literal
    kEND
    {
    - $$ = NEW_DEFN($2, $4, $5, NOEX_PRIVATE);
    + NODE *body = remove_begin($5);
    + reduce_nodes(&body);
    + $$ = NEW_DEFN($2, $4, body, NOEX_PRIVATE);
    fixpos($$, $4);
    local_pop();
    -1666,5 +1674,7 primary : literal
    kEND
    {
    - $$ = NEW_DEFS($2, $5, $7, $8);
    + NODE *body = remove_begin($8);
    + reduce_nodes(&body);
    + $$ = NEW_DEFS($2, $5, $7, body);
    fixpos($$, $2);
    local_pop();
    -4498,5 +4513,5 block_append(head, tail)
    NODE *head, *tail;
    {
    - NODE *end, *h = head;
    + NODE *end, *h = head, *nd;

    if (tail == 0) return head;
    -4519,18 +4534,18 block_append(head, tail)
    }

    - if (RTEST(ruby_verbose)) {
    - NODE *nd = end->nd_head;
    - switch (nd_type(nd)) {
    - case NODE_RETURN:
    - case NODE_BREAK:
    - case NODE_NEXT:
    - case NODE_REDO:
    - case NODE_RETRY:
    + nd = end->nd_head;
    + switch (nd_type(nd)) {
    + case NODE_RETURN:
    + case NODE_BREAK:
    + case NODE_NEXT:
    + case NODE_REDO:
    + case NODE_RETRY:
    + if (RTEST(ruby_verbose)) {
    pr_warning(nd, "statement not reached");
    - break;
    -
    - default:
    - break;
    }
    + break;
    +
    + default:
    + break;
    }

    -5103,4 +5118,54 remove_begin(node)
    }
    return node;
    +}
    +
    +static void
    +reduce_nodes(body)
    + NODE **body;
    +{
    + NODE *node = *body;
    +
    +#define subnodes(n1, n2) \
    + ((!node->n1) ? (node->n2 ? (body = &node->n2, 1) : 0) : \
    + (!node->n2) ? (body = &node->n1, 1) : \
    + (reduce_nodes(&node->n1), body = &node->n2, 1))
    +
    + while (node) {
    + switch (nd_type(node)) {
    + end:
    + case NODE_NIL:
    + *body = 0;
    + return;
    + case NODE_RETURN:
    + *body = node = node->nd_stts;
    + continue;
    + case NODE_BEGIN:
    + *body = node = node->nd_body;
    + continue;
    + case NODE_BLOCK:
    + body = &node->nd_end->nd_head;
    + break;
    + case NODE_IF:
    + if (subnodes(nd_body, nd_else)) break;
    + return;
    + case NODE_CASE:
    + body = &node->nd_body;
    + break;
    + case NODE_WHEN:
    + if (!subnodes(nd_body, nd_next)) goto end;
    + break;
    + case NODE_ENSURE:
    + if (!subnodes(nd_head, nd_resq)) goto end;
    + break;
    + case NODE_RESCUE:
    + if (!subnodes(nd_head, nd_resq)) goto end;
    + break;
    + default:
    + return;
    + }
    + node = *body;
    + }
    +
    +#undef subnodes
    }



    --
    Nobu Nakada


    nobu.nokada@softhome.net Guest

  12. #12

    Default Re: peephole optimization (Re: Bignums and return)

    HI,

    In message "peephole optimization (Re: Bignums and return)"
    on 04/02/02, net <net> writes:

    |* p.y (remove_return): remove tail returns. [ruby-talk:90934]

    Interesting. Commit this to the HEAD.

    matz.



    Yukihiro Guest

Similar Threads

  1. CFC Return Value
    By drmaves in forum Coldfusion - Advanced Techniques
    Replies: 2
    Last Post: August 25th, 02:04 PM
  2. return xml
    By Poppy in forum ASP.NET Web Services
    Replies: 3
    Last Post: April 27th, 04:01 PM
  3. goToNetPage, return or not return
    By GONS in forum Macromedia Director Basics
    Replies: 1
    Last Post: January 16th, 08:44 PM
  4. How to return my own XML?
    By Christopher Ambler in forum ASP.NET Web Services
    Replies: 2
    Last Post: September 20th, 03:30 AM
  5. Return to Tab
    By Joe Fallon in forum Microsoft Access
    Replies: 0
    Last Post: July 12th, 04:53 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139