Feature #1218
closedNew method needed to set and get the current recursion limit
Description
=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
Files
Updated by daz (Dave B) over 15 years ago
=begin
See if this post helps:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/89931
=end
Updated by jredville (Jim Deville) over 15 years ago
=begin
-----Original Message-----
From: Dave B [mailto:redmine@ruby-lang.org]
Sent: Thursday, February 26, 2009 7:33 AM
To: ruby-core@ruby-lang.org
Subject: [ruby-core:22545] [Feature #1218] New method needed to set and
get the current recursion limitIssue #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
Updated by Anonymous over 15 years ago
=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
Updated by austin (Austin Ziegler) over 15 years ago
=begin
On Sat, Feb 28, 2009 at 7:26 AM, Conrad Taylor redmine@ruby-lang.org 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 * halostatue@gmail.com * http://www.halostatue.ca/
* austin@halostatue.ca * http://www.halostatue.ca/feed/
* austin@zieglers.ca
=end
Updated by brent (Brent Roman) over 15 years ago
=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
--
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
Updated by nobu (Nobuyoshi Nakada) over 15 years ago
=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
Updated by Anonymous over 15 years ago
=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
Updated by brent (Brent Roman) over 15 years ago
=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
--
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
Updated by austin (Austin Ziegler) over 15 years ago
=begin
On Mon, Mar 2, 2009 at 8:07 AM, Conrad Taylor redmine@ruby-lang.org 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 * halostatue@gmail.com * http://www.halostatue.ca/
* austin@halostatue.ca * http://www.halostatue.ca/feed/
* austin@zieglers.ca
=end
Updated by Anonymous over 15 years ago
=begin
Hi, I do not have access to a Windows machine because I do all my development using Unix environments.
-Conrad
=end
Updated by shyouhei (Shyouhei Urabe) about 14 years ago
- Status changed from Open to Assigned
=begin
=end
Updated by mame (Yusuke Endoh) over 12 years ago
- 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 mame@tsg.ne.jp