Bignums and return

[Andre Nathan]

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

 

[ts]

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

 

[Andre Nathan]

Adding an explicit return, add a function call. This is why ruby detect
quickly the stack overflow

Thanks for the explanation, Guy

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


Andre

 

[ts]

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

 

[Jason Hutchens]

I was doing some testing with two factorial funtions:

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?

 

[Andre Nathan]

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

Wanna try that one, instead?

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

Andre

 

[ts]

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]

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

 

[nobu.nokada]

Hi,

At Sun, 1 Feb 2004 01:04:52 +0900,

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

Not yet.


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


Index: parse.y
===================================================================
RCS file: /cvs/ruby/src/ruby/parse.y,v
retrieving revision 1.314
diff -u -2 -p -r1.314 parse.y
--- parse.y 2 Feb 2004 13:06:35 -0000 1.314
+++ parse.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)) {
parser_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
}

 

[Yukihiro Matsumoto]

HI,

In message "peephole optimization (Re: Bignums and return)"

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

Interesting. Commit this to the HEAD.

matz.