[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Maximum stack depth

Glenn Parker

3/17/2005 2:20:00 PM

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...

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...
25 Answers

Robert Klemme

3/17/2005 2:59:00 PM

0


"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.

Kind regards

robert

Yukihiro Matsumoto

3/17/2005 3:05:00 PM

0

Hi,

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.

matz.

Glenn Parker

3/17/2005 3:10:00 PM

0

Robert Klemme wrote:
>
> 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.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

vruz

3/17/2005 3:22:00 PM

0

> 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)

3/17/2005 3:44:00 PM

0

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.

This is what Smalltalk (VisualWorks) says about it:

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

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

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


Cheers,
--binkley

Yukihiro Matsumoto

3/17/2005 3:56:00 PM

0

Hi,

In message "Re: Maximum stack depth"
on Fri, 18 Mar 2005 00:44:01 +0900, "B. K. Oxley (binkley)" <binkley@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

3/17/2005 4:18:00 PM

0

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.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoi...

Paul Hanchett

3/17/2005 6:36:00 PM

0

(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.
>

vruz

3/17/2005 7:22:00 PM

0

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.

Stealing from:
http://www.cswl.com/whiteppr/white/multithre...

............
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

3/17/2005 7:31:00 PM

0

From: "vruz" <horacio.lopez@gmail.com>
>
> 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.
>
> Stealing from:
> http://www.cswl.com/whiteppr/white/multithre...
>
> 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_stac...

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


Regards,

Bill