Feature #1218

New method needed to set and get the current recursion limit

Added by Conrad Taylor about 6 years ago. Updated about 3 years ago.

[ruby-core:22543]
Status:Rejected
Priority:Normal
Assignee:Koichi Sasada

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

fibonacci-iterative.rb Magnifier - This file computes the nth Fibonacci number using iteration. (373 Bytes) Conrad Taylor, 02/27/2009 12:13 AM

fibonacci-recursive.rb Magnifier - This file computes the nth Fibonacci number using recursion. (408 Bytes) Conrad Taylor, 02/27/2009 12:13 AM

fibonacci-tail-recursive.rb Magnifier - This file computes the nth Fibonacci number using tail recursion. (478 Bytes) Conrad Taylor, 02/27/2009 12:13 AM

History

#2 Updated by Jim Deville about 6 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: [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

#3 Updated by Conrad Taylor about 6 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

#4 Updated by Austin Ziegler about 6 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

#5 Updated by Brent Roman about 6 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


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

#6 Updated by Nobuyoshi Nakada about 6 years ago

=begin
Hi,

At Mon, 2 Mar 2009 17:41:03 +0900,
Brent Roman wrote in :

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

#7 Updated by Conrad Taylor about 6 years ago

=begin
@Austin 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

#8 Updated by Brent Roman about 6 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 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

#9 Updated by Austin Ziegler about 6 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 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

#10 Updated by Conrad Taylor about 6 years ago

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

-Conrad

=end

#11 Updated by Shyouhei Urabe over 4 years ago

  • Status changed from Open to Assigned

=begin

=end

#12 Updated by Yusuke Endoh about 3 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 .

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

Also available in: Atom PDF