Bignums and return

Andre_Nathan · 29 January 2004 13:41

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

ts1 · 29 January 2004 14:38

Why do I get these different errors?

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

Why does an explicit 'return' or compiling ruby with --enable-pthreads
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.

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.

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

Jason_Hutchens · 30 January 2004 07:20

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?

···

On Thu, 29 Jan 2004 22:41:42 +0900, Andre Nathan andre@digirati.com.br wrote:

I was doing some testing with two factorial funtions:

–
Using M2, Opera’s revolutionary e-mail client: http://www.opera.com/m2/

Andre_Nathan · 29 January 2004 16:52

Thanks for the explanation, Guy

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

Andre

···

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

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

Andre_Nathan · 30 January 2004 10:59

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

Andre

···

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

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

Wanna try that one, instead?

ts1 · 29 January 2004 17:18

Are there any plans to implement return as an operator, instead of 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

ts1 · 30 January 2004 11:05

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

Mark_J_Reed · 30 January 2004 19:49

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

···

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

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

ts1 · 31 January 2004 13:26

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

actually ruby don't use bytecode.

Guy Decoux

Mark_J_Reed · 31 January 2004 16:04

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

···

On Sat, Jan 31, 2004 at 10:26:46PM +0900, ts wrote:

It seems like “def one; return 1 end” and “def one; 1 end;” should
result in identical bytecode.

actually ruby don’t use bytecode.

Nobuyoshi_Nakada · 2 February 2004 13:08

Hi,

···

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

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
}

–
Nobu Nakada

Yukihiro_Matsumoto2 · 2 February 2004 23:59

HI,

···

In message “peephole optimization (Re: Bignums and return)” on 04/02/02, nobu.nokada@softhome.net nobu.nokada@softhome.net writes:

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

Interesting. Commit this to the HEAD.

						matz.

Topic		Replies	Views
Recursion and Ruby ruby-talk	32	154	14 July 2006
SystemStackError: stack level too deep > how make it deeper? ruby-talk	14	146	1 October 2009
"stack level too deep" error when trying to multithread in win32 using dbi ruby-talk	4	123	5 November 2002
Newbie question ruby-talk	11	78	3 August 2011
Efficiency of recursion (stack level too deep) ruby-talk	3	116	14 November 2007

Bignums and return

Index: parse.y

Related topics