Project

General

Profile

Actions

Feature #1218

closed

New method needed to set and get the current recursion limit

Added by Anonymous over 15 years ago. Updated over 12 years ago.

Status:
Rejected
Target version:
[ruby-core:22543]

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

fibonacci-iterative.rb (373 Bytes) fibonacci-iterative.rb This file computes the nth Fibonacci number using iteration. Anonymous, 02/27/2009 12:13 AM
fibonacci-recursive.rb (408 Bytes) fibonacci-recursive.rb This file computes the nth Fibonacci number using recursion. Anonymous, 02/27/2009 12:13 AM
fibonacci-tail-recursive.rb (478 Bytes) fibonacci-tail-recursive.rb This file computes the nth Fibonacci number using tail recursion. Anonymous, 02/27/2009 12:13 AM
Actions #2

Updated by jredville (Jim Deville) over 15 years ago

=begin

-----Original Message-----
From: Dave B []
Sent: Thursday, February 26, 2009 7:33 AM
To:
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

Actions #3

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

Actions #4

Updated by austin (Austin Ziegler) over 15 years ago

=begin
On Sat, Feb 28, 2009 at 7:26 AM, Conrad Taylor 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 * * http://www.halostatue.ca/
* * http://www.halostatue.ca/feed/
*

=end

Actions #5

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


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

Actions #6

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

Actions #7

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

Actions #8

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


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

Actions #9

Updated by austin (Austin Ziegler) over 15 years ago

=begin
On Mon, Mar 2, 2009 at 8:07 AM, Conrad Taylor 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 * * http://www.halostatue.ca/
* * http://www.halostatue.ca/feed/
*

=end

Actions #10

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

Actions #11

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

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0