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.
"Glenn Parker" <glenn.parker@comcast.net> schrieb im Newsbeitrag
news:42399214.4030404@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.
In message "Re: Maximum stack depth" on Thu, 17 Mar 2005 23:20:23 +0900, Glenn Parker <glenn.parker@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.
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:
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.
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.
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
(Showing my ignorance:) I thought windows apps had an automatically expanding stack.
Glenn Parker wrote:
···
Yukihiro Matsumoto wrote:
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.
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.
Sorta off-topic now, but FYI, you can't do this.
The ulimit can't be arbitrarily increased. If the
soft limit allows it, you can but if there is a
hard limit set then you're screwed (and in reality
it doesn't make a difference). You can always
make it smaller but you can't make it bigger.
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.
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?
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
···
On 2005-03-18, Robert Klemme <bob.news@gmx.net> wrote:
"vruz" <horacio.lopez@gmail.com> schrieb im Newsbeitrag
news:6b809bd8050317072128a96c1f@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'
............
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.
...........
···
On Fri, 18 Mar 2005 04:11:18 +0900, Paul Hanchett <paulha@aracnet.com> wrote:
(Showing my ignorance:) I thought windows apps had an automatically
expanding stack.
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.
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.
