Feature #1218: New method needed to set and get the current recursion limit

• Status: Rejected
• Assignee: ko1 (Koichi Sasada)
• Target version: 2.0.0

=begin
Hi, I would like to propose the addition of two methods for setting and getting the recursion limit:

recursion_limit(limit)
recursion_limit => returns an Integer value

At this time, I have been experimenting with recursion to compute the nth fibonacci number using ruby 1.9.1 ( i.e ruby 1.9.1p0 (2009-01-30 revision 21907) ). These tests are being ran on a Apple PowerMac G5 2.5 Ghz Quad 4 GB RAM and a MacBook Pro 2.8 GHz Intel Core 2 Duo 4 GB RAM. Also, I was able to successfully produce a result using an iteration which I'm attaching to verify the correctness of the other two algorithms:

action: ./fibonacci-recursive.rb 10000

result:

./fibonacci-recursive.rb:10:in fibonacci': stack level too deep (SystemStackError) from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:10:in fibonacci' from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:10:in fibonacci' from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:10:in fibonacci' from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:10:in fibonacci' ... 8174 levels... from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:10:in fibonacci' from ./fibonacci-recursive.rb:10:in fibonacci'
from ./fibonacci-recursive.rb:18:in `'

action: ./fibonacci-tail-recursive.rb 10000

result:

./fibonacci-tail-recursive.rb:10:in fibonacci_helper': stack level too deep (SystemStackError) from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper'
from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper' from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper'
from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper' from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper'
from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper' from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper'
from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper' ... 7265 levels... from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper'
from ./fibonacci-tail-recursive.rb:10:in fibonacci_helper' from ./fibonacci-tail-recursive.rb:17:in fibonacci'
from ./fibonacci-tail-recursive.rb:24:in `'

action: ./fibonacci-iterative.rb 10000

result:

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
=end

[daz (Dave B)]

=begin
See if this post helps:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/89931
=end

[jredville (Jim Deville)]

=begin

-----Original Message-----
From: Dave B [mailto:[e-mail]]
Sent: Thursday, February 26, 2009 7:33 AM
To: [e-mail]
Subject: [ruby-core:22545] [Feature #1218] New method needed to set and
get the current recursion limit

Issue #1218 has been updated by Dave B.

See if this post helps:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/89931

That wouldn't help for Ruby on Windows. It would also be nice to have something tied to the code, not the system.

JD

=end

=begin
Hi Dave, thanks for responding to the post. However, this doesn't resolve the issue that I'm seeing after increasing the stack size. There should be some class methods for obtaining and setting the recursion limit.

-Conrad

=end

[austin (Austin Ziegler)]

=begin
On Sat, Feb 28, 2009 at 7:26 AM, Conrad Taylor [e-mail] wrote:

Issue #1218 has been updated by Conrad Taylor.

Hi Dave, thanks for responding to the post.  However, this does resolve the issue that I'm seeing after increasing the stack size.  There should be some class methods for obtaining and setting the recursion limit.

You can't change the recursion limit from within the program on all
operating systems.

-austin

Austin Ziegler * [e-mail] * http://www.halostatue.ca/
* [e-mail] * http://www.halostatue.ca/feed/
* [e-mail]

=end

[brent (Brent Roman)]

=begin

setrlimit(RLIMIT_STACK, size_in_bytes)
should do what you want under a POSIX compliant OS.

See the manpage for setrlimit and getrlimit

This could easily be made accessible to Ruby code via a 'C' extension.

I have found that 1.8 Ruby is very inefficient in its use of stack-space
and made some patches that improve this.
With ulimit -s 8192, the attached little script on gives up after:

 1.6.8-mbari8B:   14374 levels
 1.8.6-p287:  7198 levels
 1.8.7-p72:   7197 levels
 1.8.7-p72-mbari8B: 14750 levels
 1.8.6-p287-mbari8B: 14750 levels
 1.9.0 :  7704 levels  (but, see note below)

Ruby 1.9 seems completely unaffected by stack size configured via setrlimit
(via ulimit -s from the bash shell)

Perhaps 1.9 is allocating the stack on the heap.
If this is the case, you will need some support in the 1.9 core for changing
the size
of this allocation.

• brent

Usaku NAKAMURA wrote:

Issue #1218 has been updated by Conrad Taylor.

Hi Dave, thanks for responding to the post. However, this does resolve
the issue that I'm seeing after increasing the stack size. There should
be some class methods for obtaining and setting the recursion limit.

-Conrad

---

http://redmine.ruby-lang.org/issues/show/1218

---

http://redmine.ruby-lang.org

--
View this message in context: http://www.nabble.com/-ruby-core%3A22543---Feature--1218--New-method-needed-to-set-and-get-the-current-recursion-limit-tp22226204p22283425.html
Sent from the ruby-core mailing list archive at Nabble.com.

=end

[nobu (Nobuyoshi Nakada)]

=begin
Hi,

At Mon, 2 Mar 2009 17:41:03 +0900,
Brent Roman wrote in [ruby-core:22619]:

Ruby 1.9 seems completely unaffected by stack size configured via setrlimit
(via ulimit -s from the bash shell)

Perhaps 1.9 is allocating the stack on the heap.

1.9 uses the default of pthread.

--
Nobu Nakada

=end

=begin
@austin (Austin Ziegler) Ziegler - I was able to change these limits within Python using FreeBSD, Linux, and Mac OS X operating systems. The first two are production machines and the last is a development machine.
Otherwise, the Python examples would have crapped out as did the Ruby recursive examples. Thus, I'm sure that it's possible on most modern platforms to change these limits within
the Ruby language.
=end

[brent (Brent Roman)]

=begin

I don't do much pthreads programming.
The call you want seems to be:

int pthread_attr_setstacksize(pthread_attr_t *attr, size_t stacksize)
Set the stack size attribute in a thread attributes
object.
See:
http://developer.apple.com/DOCUMENTATION/Darwin/Reference/ManPages/man3/pthread.3.html
(The prospective 'C' extension would have to get at the relevant
pthread_attr_t)

Here's the little test script I forgot to attach yesterday:

$a=0

def x
$a += 1
x
end

begin
x
rescue SystemStackError
puts "After #{$a} levels"
puts $!
end

Conrad Taylor-3 wrote:

Issue #1218 has been updated by Conrad Taylor.

@austin (Austin Ziegler) Ziegler - I was able to change these limits within Python using
FreeBSD, Linux, and Mac OS X operating systems. The first two are
production machines and the last is a development machine.
Otherwise, the Python examples would have
crapped out as did the Ruby recursive examples. Thus, I'm sure that it's
possible on most modern platforms to change these limits within
the Ruby language.

http://redmine.ruby-lang.org/issues/show/1218

---

http://redmine.ruby-lang.org

--
View this message in context: http://www.nabble.com/-ruby-core%3A22543---Feature--1218--New-method-needed-to-set-and-get-the-current-recursion-limit-tp22226204p22291197.html
Sent from the ruby-core mailing list archive at Nabble.com.

=end

[austin (Austin Ziegler)]

=begin
On Mon, Mar 2, 2009 at 8:07 AM, Conrad Taylor [e-mail] wrote:

Issue #1218 has been updated by Conrad Taylor.

@austin (Austin Ziegler) Ziegler - I was able to change these limits within Python using FreeBSD, Linux, and Mac OS X operating systems.  The first two are production machines and the last is a development machine.
                               Otherwise, the Python examples would have crapped out as did the Ruby recursive examples.  Thus, I'm sure that it's possible on most modern platforms to change these limits within
                               the Ruby language.

Did you try this on Windows?

I'm not sure it's possible on most modern platforms (and despite
what people think and my own personal prejudices, Windows is a modern
platform that Rubyists can't afford to ignore).

-austin

Austin Ziegler * [e-mail] * http://www.halostatue.ca/
* [e-mail] * http://www.halostatue.ca/feed/
* [e-mail]

=end

=begin
Hi, I do not have access to a Windows machine because I do all my development using Unix environments.

-Conrad

=end

[shyouhei (Shyouhei Urabe)]

• Status changed from Open to Assigned

=begin

=end

[mame (Yusuke Endoh)]

• Status changed from Assigned to Rejected

I'm rejecting this feature ticket because no progress has been
made for a long time. See [ruby-core:42391].

I think it is impossible to implement recursion_limit exactly
because we cannot know how much stack each C function consumes.

I expected Python's recursion_limit to fail conservatively
(i.e., it will raise an exception for big limit even when it is
actually possible). But it was worse than I expected. Python
caused SEGV when big limit is specified:

import sys
sys.setrecursionlimit(1000000)
def foo():
foo()
foo() #=> SEGV

I think that this is not a correct way, at least, in Ruby.

--
Yusuke Endoh [e-mail]