Maximum stack depth

[Glenn Parker]

It would be useful to have a Ruby command-line option to specify a
larger limit on stack depth. I can't find any obvious way, short of
manipulating the source, to do this.

This came up while I was looking at some of the Ruby snippets at the
"Great Computer Language Shootout". The Ackermann benchmark requires
very deep recursion, which causes (valid) Ruby code to fail:

def ack(m, n)
if m == 0 then
n + 1
elsif n == 0 then
ack(m - 1, 1)
else
ack(m - 1, ack(m, n - 1))
end
end

puts ack(3, 10)

The "10" in the call to ack(3, 10) is the killer. Actually, anything
past ack(3, 6) produces "stack level too deep (SystemStackError)" with
726 levels on WinXP. Other languages handle ack(3, 10) successfully,
including interpreters like Python, Perl, and Tcl.

Is it just me, or does a stack limited to less than 1000 levels of
recursion seem... crippled?

Note: rewriting this code to avoid deep recursion (even if you could) is
not the point. The benchmark is intended to probe performance related
to recursion and function-calling overhead.

More details at:
http://shootout.alioth.debian.org/benchmark.php?test=ackermann

 

[Robert Klemme]

It would be useful to have a Ruby command-line option to specify a
larger limit on stack depth. I can't find any obvious way, short of
manipulating the source, to do this.

<snip/>

I had this problem a while ago. But since the ruby stack is the C stack
you can only increase stack size during compilation with a compiler /
linker flag.

Kind regards

robert

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Maximum stack depth"

|It would be useful to have a Ruby command-line option to specify a
|larger limit on stack depth. I can't find any obvious way, short of
|manipulating the source, to do this.

Ruby uses C stack, so that you need to use ulimit to specify a limit
on stack depth.

matz.

 

[Glenn Parker]

I had this problem a while ago. But since the ruby stack is the C stack
you can only increase stack size during compilation with a compiler /
linker flag.

On the Solaris platform (and probably other pthreads-friendly
environments), it might be possible to implement this as a command-line
option by spawning a (real) thread configured to use a larger stack size.

 

[vruz]

Is it just me, or does a stack limited to less than 1000 levels of

recursion seem... crippled?

1891 levels in my old redhat linux 7.3 box, ruby 1.8.2 built from source

 

[B. K. Oxley (binkley)]

It would be useful to have a Ruby command-line option to specify a
larger limit on stack depth. I can't find any obvious way, short of
manipulating the source, to do this.

Does Ruby not do tail recursion optimization? That would remove any
limit to the stack depth for functions such as Ackerman.

This is what Smalltalk (VisualWorks) says about it:

http://wiki.cs.uiuc.edu/VisualWorks/Tail+Recursion

And the C2 wiki talks about it as well as some of the drawbacks:

http://c2.com/cgi/wiki?TailCallOptimization


Cheers,
--binkley

 

[Yukihiro Matsumoto]

Hi,

In message "Re: Maximum stack depth"

|Does Ruby not do tail recursion optimization? That would remove any
|limit to the stack depth for functions such as Ackerman.

Not yet, but planned.

matz.

 

[Glenn Parker]

Ruby uses C stack, so that you need to use ulimit to specify a limit
on stack depth.

Thank you for the tip, but I'm afraid ulimit is not an option under
WinXP, and I have no idea what the corresponding tweak would be.

I will suggest to the Shootout folks that they try boosting the stack
size with ulimit for the Ackerman test.

Does anybody know the stack "overhead" for method invokation in Ruby?
If vruz gets (only) 1891 levels on a linux box, and typical default
stack size limit is 1 MB, then I calculate a little over 500 bytes for
each level of recursion, but the stack size limit is just a guess.

 

[Paul Hanchett]

(Showing my ignorance I thought windows apps had an automatically
expanding stack.

 

[vruz]

(Showing my ignorance I thought windows apps had an automatically
expanding stack.

Stealing from:
http://www.cswl.com/whiteppr/white/multithreading.html

............
The Birth of a Thread: CreateThread
An inevitable part of a thread is some code to execute. Under Windows
NT, the address of a function is passed as a parameter to CreateThread
to execute in the thread. The thread executes as long as it does not
return from it. The thread can be terminated using TerminateThread.
Each thread runs on a separate stack. To be more precise, each thread
runs on either of two dedicated stacks—the kernel stack or the
application stack—depending on whether system or application code
executes in it, respectively, but the kernel stack is nothing that is
ever visible in any form. Windows NT will dynamically grow the stack
if necessary, but it will never grow it past 1 MB. This is to prevent
infinitely recursive function calls from blowing up your process.
...........

 

[Bill Kelly]

Stealing from:
http://www.cswl.com/whiteppr/white/multithreading.html

Windows NT will dynamically grow the stack
if necessary, but it will never grow it past 1 MB.

That doesn't seem to be the whole story. More info:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/thread_stack_size.asp

There must be tools out there that will tweak the .exe header to increase
the default stacksize...


Regards,

Bill

 

[Robert Klemme]

1891 levels in my old redhat linux 7.3 box, ruby 1.8.2 built from source

Just to add another number:

09:49:43 [source]: ruby -e 'def t(i) p i;t(i+1) end;t 0'
....
13280
13281
13282
13283
-e:1:in `p': stack level too deep (SystemStackError)
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
... 13274 levels...
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1
09:49:48 [source]: uname -a
CYGWIN_NT-5.0 bond 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown unknown
Cygwin
09:51:46 [source]: ruby -v
ruby 1.8.1 (2003-12-25) [i386-cygwin]
09:51:49 [source]: ulimit
unlimited
09:51:59 [source]:

Kind regards

robert

 

[gabriele renzi]

B. K. Oxley (binkley) ha scritto:

Does Ruby not do tail recursion optimization? That would remove any
limit to the stack depth for functions such as Ackerman.

notice that yarv handles this just fine:
C:\yarv>ruby19 -rite ack.rb
8189

and it should support TCO (koichi said he wants to run scheme on yarv,
so this would be mandatory), but I think it does not do this yet.
So, if yarv becomes the ruby2 vm this would be yes

 

[Glenn Parker]

09:49:48 [source]: uname -a
CYGWIN_NT-5.0 bond 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown unknown
Cygwin
09:51:46 [source]: ruby -v
ruby 1.8.1 (2003-12-25) [i386-cygwin]
09:51:49 [source]: ulimit
unlimited

For the simple test, my system stops at 1299 levels while yours goes all
the way to 13283. It is very interesting that you get literally ten
times the amount of stack space with the cygwin version of Ruby that I
get using the one-click installer version of Ruby.

$ uname -a
CYGWIN_NT-5.1 Zounds 1.5.10(0.116/4/2) 2004-05-25 22:07 i686 unknown
unknown Cygwin

$ ruby -v
ruby 1.8.2 (2004-11-06) [i386-mswin32]

$ ulimit -a
core file size (blocks, -c) unlimited
data seg size (kbytes, -d) unlimited
file size (blocks, -f) unlimited
open files (-n) 256
pipe size (512 bytes, -p) 8
stack size (kbytes, -s) 2043
cpu time (seconds, -t) unlimited
max user processes (-u) 63
virtual memory (kbytes, -v) 2097152

What does "ulimit -a" report in your environment?

 

[Glenn Parker]

notice that yarv handles this just fine:
C:\yarv>ruby19 -rite ack.rb
8189

and it should support TCO (koichi said he wants to run scheme on yarv,
so this would be mandatory), but I think it does not do this yet.
So, if yarv becomes the ruby2 vm this would be yes

YARV certainly does sound terrific. I wish we could do something more
to speed its completion. From what I've read, I think the combination
of significantly faster execution and other advanced features will
radically alter the perception of Ruby. Will we have to wait until XMas
2005 (or longer) for YARV to become the standard?

 

[Robert Klemme]

09:49:48 [source]: uname -a
CYGWIN_NT-5.0 bond 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown unknown
Cygwin
09:51:46 [source]: ruby -v
ruby 1.8.1 (2003-12-25) [i386-cygwin]
09:51:49 [source]: ulimit
unlimited

For the simple test, my system stops at 1299 levels while yours goes all
the way to 13283. It is very interesting that you get literally ten
times the amount of stack space with the cygwin version of Ruby that I
get using the one-click installer version of Ruby.

$ uname -a
CYGWIN_NT-5.1 Zounds 1.5.10(0.116/4/2) 2004-05-25 22:07 i686 unknown
unknown Cygwin

$ ruby -v
ruby 1.8.2 (2004-11-06) [i386-mswin32]

$ ulimit -a
core file size (blocks, -c) unlimited
data seg size (kbytes, -d) unlimited
file size (blocks, -f) unlimited
open files (-n) 256
pipe size (512 bytes, -p) 8
stack size (kbytes, -s) 2043
cpu time (seconds, -t) unlimited
max user processes (-u) 63
virtual memory (kbytes, -v) 2097152

What does "ulimit -a" report in your environment?

Looks quite similar:

13:48:38 [source]: ulimit -a
core file size (blocks, -c) unlimited
data seg size (kbytes, -d) unlimited
file size (blocks, -f) unlimited
open files (-n) 256
pipe size (512 bytes, -p) 8
stack size (kbytes, -s) 2043
cpu time (seconds, -t) unlimited
max user processes (-u) 63
virtual memory (kbytes, -v) 2097152

Kind regards

robert

 

[ES]

09:49:48 [source]: uname -a
CYGWIN_NT-5.0 bond 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown
unknown
Cygwin
09:51:46 [source]: ruby -v
ruby 1.8.1 (2003-12-25) [i386-cygwin]
09:51:49 [source]: ulimit
unlimited

For the simple test, my system stops at 1299 levels while yours goes all
the way to 13283. It is very interesting that you get literally ten
times the amount of stack space with the cygwin version of Ruby that I
get using the one-click installer version of Ruby.

I think you may be able to use EDITBIN to change the stack size on
'native' Windows binaries. It's probably a part of VS or something,
though.

Or you could update to Win98 and edit CONFIG.SYS

$ uname -a
CYGWIN_NT-5.1 Zounds 1.5.10(0.116/4/2) 2004-05-25 22:07 i686 unknown
unknown Cygwin

$ ruby -v
ruby 1.8.2 (2004-11-06) [i386-mswin32]

$ ulimit -a
core file size (blocks, -c) unlimited
data seg size (kbytes, -d) unlimited
file size (blocks, -f) unlimited
open files (-n) 256
pipe size (512 bytes, -p) 8
stack size (kbytes, -s) 2043
cpu time (seconds, -t) unlimited
max user processes (-u) 63
virtual memory (kbytes, -v) 2097152

What does "ulimit -a" report in your environment?

E

 

[Csaba Henk]

1891 levels in my old redhat linux 7.3 box, ruby 1.8.2 built from source

Just to add another number:

09:49:43 [source]: ruby -e 'def t(i) p i;t(i+1) end;t 0'
...
13280
13281
13282
13283
-e:1:in `p': stack level too deep (SystemStackError)
from -e:1:in `t'
from -e:1:in `t'

In my ruby installations under gentoo, there is no "stack level too
deep", ruby just eats up all memory and then the OS gracefully kills
it (it happens when I don't link it against pthread).

It seems that function data is stored on the heap. Is it possible? Under
what circumstances can this phenomenon -- ie., that ruby doesn't runs
out of stack upon a deep recursion -- occur (OS, kernel (OS, compilation
options, compilation options, ...) ?

Csaba

 

[Tim Bates]

In my ruby installations under gentoo, there is no "stack level too
deep", ruby just eats up all memory and then the OS gracefully kills
it (it happens when I don't link it against pthread).

I get the same thing (also on Gentoo), except with 1GB of RAM and 2GB of
swap my system slows to a crawl long before the operating system kills
it and my patience runs out. It can take some minutes to kill the
program once I realise this is happening - which is generally when my
swap space usage goes above 0%. I think I might actually prefer a stack
level too deep error. Usually by the time my system starts swapping, the
stack is over 200,000 levels deep.

It seems that function data is stored on the heap. Is it possible? Under
what circumstances can this phenomenon -- ie., that ruby doesn't runs
out of stack upon a deep recursion -- occur (OS, kernel (OS, compilation
options, compilation options, ...) ?

After a bit of research, I've discovered that Gentoo by default doesn't
have a stack size limit. Watch: (using the bash builtin `ulimit`)

$ ulimit -a
<snip>
stack size (kbytes, -s) unlimited
<snip>

$ ulimit -s 1024
$ ruby -e 'def t(i) t(i+1) end;t 0'
-e:1:in `t': stack level too deep (SystemStackError)
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
... 401 levels...
from -e:1:in `t'
from -e:1:in `t'
from -e:1:in `t'
from -e:1

Tim.

 

[Thomas Hurst]

1891 levels in my old redhat linux 7.3 box, ruby 1.8.2 built from source

09:49:43 [source]: ruby -e 'def t(i) p i;t(i+1) end;t 0'
13283
-e:1:in `p': stack level too deep (SystemStackError)
09:49:48 [source]: uname -a
CYGWIN_NT-5.0 bond 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown unknown

On FreeBSD 5:

49165
-e:1:in `inspect': stack level too deep (SystemStackError)

I think I can live with that. Solaris 9 fares somewhat worse:

3921
-e:1:in `t': stack level too deep (SystemStackError)

But not as badly as Linux 2.6.8.1:

2091
-e:1:in `p': stack level too deep (SystemStackError)

Or WinXP:

1330
-e:1:in `p': stack level too deep (SystemStackError)

I wonder, is it safe to rescue SystemStackError? It seems to work, but
can the interpreter be trusted after this?