Maximum stack depth
Glenn Parker
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
--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>
Robert Klemme
"Glenn Parker" <glenn....@comcast.net> schrieb im Newsbeitrag
news:42399214...@comcast.net...
> 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
In message "Re: Maximum stack depth"
on Thu, 17 Mar 2005 23:20:23 +0900, Glenn Parker <glenn....@comcast.net> writes:
|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
> 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
In message "Re: Maximum stack depth"
on Fri, 18 Mar 2005 00:44:01 +0900, "B. K. Oxley (binkley)" <bin...@alumni.rice.edu> writes:
|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
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
>
> On Fri, 18 Mar 2005 04:11:18 +0900, Paul Hanchett <pau...@aracnet.com> wrote:
> > (Showing my ignorance:) I thought windows apps had an automatically
> > expanding stack.
>
> Stealing from:
> http://www.cswl.com/whiteppr/white/multithreading.html
>
> 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
"vruz" <horaci...@gmail.com> schrieb im Newsbeitrag
news:6b809bd805031...@mail.gmail.com...
> > 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
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
> Glenn Parker wrote:
>
>> 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.
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?
Christian Neukirchen
+1 *very* good idea. :-)
--
Christian Neukirchen <chneuk...@gmail.com> http://chneukirchen.org
Robert Klemme
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
> Robert Klemme wrote:
>
>> 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
>
> "vruz" <horaci...@gmail.com> schrieb im Newsbeitrag
> news:6b809bd805031...@mail.gmail.com...
>> > 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
>
> 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.
--
Tim Bates
t...@bates.id.au
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?
--
Thomas 'Freaky' Hurst
http://hur.st/
Gavin Kistner
> * Robert Klemme (bob....@gmx.net) wrote:
>>> 1891 levels in my old redhat linux 7.3 box, ruby 1.8.2 built from
>>> source
> 49165
> I think I can live with that. Solaris 9 fares somewhat worse:
> 3921
Man, you are all awesome compared to MacOS X :|
[Slim:~] gavinkis% uname -a
Darwin Slim.local 7.8.0 Darwin Kernel Version 7.8.0: Wed Dec 22
14:26:17 PST 2004; root:xnu/xnu-517.11.1.obj~1/RELEASE_PPC Power
Macintosh powerpc
[Slim:~] gavinkis% ruby --version
ruby 1.8.2 (2004-11-06) [powerpc-darwin7.6.0]
[Slim:~] gavinkis% ruby tmp.rb
tmp.rb:9:in `ack': stack level too deep (SystemStackError)
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
... 600 levels...
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:9:in `ack'
from tmp.rb:14
--
(-, /\ \/ / /\/
Eric Anderson
> 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>
I'm on gentoo and here is the output of my system. I haven't changed any
defaults:
$ ulimit -a
<snip>
stack size (kbytes, -s) 8192
<snip>
Eric
Luke Graham
> Tim Bates wrote:
> > 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`)
I used to run gentoo (and will again), and I always turned
swap off for the reason mentioned... runaway
processes are hard to kill when the machine is
thrashing. It might not be an option if you have less than
say, 0.5 gig of ram, but I never once had trouble with
a legit process because of it.
--
spooq
Yukihiro Matsumoto
In message "Re: Maximum stack depth"
on Sat, 19 Mar 2005 10:15:56 +0900, Thomas Hurst <tom....@clara.net> writes:
|I wonder, is it safe to rescue SystemStackError? It seems to work, but
|can the interpreter be trusted after this?
It should be safe, since exception rewinds C stack using longjmp(3).
matz.
Premshree Pillai
>
> 49165
> -e:1:in `inspect': stack level too deep (SystemStackError)
FreeBSD 4.10 (Yahoo customized):
from -e:1:in `t'
... 56581 levels...
--
Premshree Pillai
http://www.livejournal.com/users/premshree/