recursion depth limitations

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

recursion depth limitations

Suzen, Mehmet
Hello List,

I am aware that one can set with recursion depth 'options(expressions
= #)', but it has 500K limit. Why do we have a 500K limit on this?
While some algorithms are only "solvable"  feasibility with recursion
and 500K sounds not too much i.e. graph algorithms
for example dependency trees with large nodes easily reach to that number.

Best,
-m

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Simon Urbanek
On Dec 13, 2012, at 10:45 AM, Suzen, Mehmet wrote:

> Hello List,
>
> I am aware that one can set with recursion depth 'options(expressions
> = #)', but it has 500K limit. Why do we have a 500K limit on this?

Because it's far beyond what you can handle without changing a lot of other things. 500k expressions will require at least about 320Mb of stack (!) in the eval() chain alone -- compare that to the 8Mb stack size which is default in most OSes, so you'll hit the wall way before that limit is reached.


> While some algorithms are only "solvable"  feasibility with recursion
> and 500K sounds not too much i.e. graph algorithms
> for example dependency trees with large nodes easily reach to that number.
>

I don't see how "large nodes" have anything to do with this since we are talking about expression depth, not about sizes of any kind. Again, in any realistic example you'll hit other limits first anyway.

Cheers,
Simon

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Suzen, Mehmet
On 13 December 2012 17:52, Simon Urbanek <[hidden email]> wrote:
> Because it's far beyond what you can handle without changing a lot of other things. 500k expressions will require at least about 320Mb of stack (!) in the eval() chain alone -- compare that to the 8Mb stack size which is default in most OSes, so you'll hit the wall way before that limit is reached.
>

Thank you for the explanation. Sorry to be dummy on this but why one
need a stack? I thought pointing to itself
has no memory cost for a function. Is it about how compilers designed
or about R being dynamic language?

>
>> While some algorithms are only "solvable"  feasibility with recursion
>> and 500K sounds not too much i.e. graph algorithms
>> for example dependency trees with large nodes easily reach to that number.
>>
>
> I don't see how "large nodes" have anything to do with this since we are talking about expression depth, not about sizes of any kind.
> Again, in any realistic example you'll hit other limits first anyway.

I was thinking about very big tree with large depth, so each recursion
step may correspond to one leaf. Well not sure what
would be the application that has million depth, maybe a genetic algorithm.

Cheers,
Mehmet

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Rui Barradas
Hello.

Inline.
Em 13-12-2012 21:31, Suzen, Mehmet escreveu:
> On 13 December 2012 17:52, Simon Urbanek <[hidden email]> wrote:
>> Because it's far beyond what you can handle without changing a lot of other things. 500k expressions will require at least about 320Mb of stack (!) in the eval() chain alone -- compare that to the 8Mb stack size which is default in most OSes, so you'll hit the wall way before that limit is reached.
>>
> Thank you for the explanation. Sorry to be dummy on this but why one
> need a stack? I thought pointing to itself
> has no memory cost for a function.

But it does, each recursive call will load another copy of the function,
and another copy of the variables used.
In fact, the cost can become quite large since everything is loaded in
memory again.

Hope this helps,

Rui Barradas

>   Is it about how compilers designed
> or about R being dynamic language?
>
>>> While some algorithms are only "solvable"  feasibility with recursion
>>> and 500K sounds not too much i.e. graph algorithms
>>> for example dependency trees with large nodes easily reach to that number.
>>>
>> I don't see how "large nodes" have anything to do with this since we are talking about expression depth, not about sizes of any kind.
>> Again, in any realistic example you'll hit other limits first anyway.
> I was thinking about very big tree with large depth, so each recursion
> step may correspond to one leaf. Well not sure what
> would be the application that has million depth, maybe a genetic algorithm.
>
> Cheers,
> Mehmet
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Suzen, Mehmet-2
On 13 December 2012 23:21, Rui Barradas <[hidden email]> wrote:
> But it does, each recursive call will load another copy of the function, and
> another copy of the variables used.
> In fact, the cost can become quite large since everything is loaded in
> memory again.
>
> Hope this helps,
>

Many thanks for the replies.

What about tail-recursion?  I have seen that there were discussions
about this:

https://stat.ethz.ch/pipermail/r-help/2006-April/102873.html

Since it was 6 years ago, maybe now things are little different.

Best
-m



Mehmet

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Suzen, Mehmet
On 14 December 2012 12:13, Suzen, Mehmet <[hidden email]> wrote:

> On 13 December 2012 23:21, Rui Barradas <[hidden email]> wrote:
>> But it does, each recursive call will load another copy of the function, and
>> another copy of the variables used.
>> In fact, the cost can become quite large since everything is loaded in
>> memory again.
>>
>> Hope this helps,
>>
>
> Many thanks for the replies.
>
> What about tail-recursion?  I have seen that there were discussions
> about this:
>
> https://stat.ethz.ch/pipermail/r-help/2006-April/102873.html
>
> Since it was 6 years ago, maybe now things are little different.


Isn't it logical to translate any recursive function to tail-recursive
internally? While tail-recursive
version returns a value but the operation is essentially the same. I don't know
how difficult to do it generically but maybe there is an advantage of
keeping recursion
as it is. What would that advantage be?

For example, tail recursion would run but not the recursive version:

> options(expressions=500000)
>  f <- function(x) if(x >0) f(x-1);
> system.time(f(10000000))
Error: C stack usage is too close to the limit
Error: C stack usage is too close to the limit
> f1<-function(x) x-1
> f <- function(x) f1(x);
> system.time(f(10000000))
   user  system elapsed
      0       0       0

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Simon Urbanek

On Dec 14, 2012, at 6:25 AM, Suzen, Mehmet wrote:

> On 14 December 2012 12:13, Suzen, Mehmet <[hidden email]> wrote:
>> On 13 December 2012 23:21, Rui Barradas <[hidden email]> wrote:
>>> But it does, each recursive call will load another copy of the function, and
>>> another copy of the variables used.
>>> In fact, the cost can become quite large since everything is loaded in
>>> memory again.
>>>
>>> Hope this helps,
>>>
>>
>> Many thanks for the replies.
>>
>> What about tail-recursion?  I have seen that there were discussions
>> about this:
>>
>> https://stat.ethz.ch/pipermail/r-help/2006-April/102873.html
>>
>> Since it was 6 years ago, maybe now things are little different.
>
>
> Isn't it logical to translate any recursive function to tail-recursive
> internally? While tail-recursive
> version returns a value but the operation is essentially the same. I don't know
> how difficult to do it generically but maybe there is an advantage of
> keeping recursion
> as it is. What would that advantage be?
>
> For example, tail recursion would run but not the recursive version:
>
>> options(expressions=500000)
>> f <- function(x) if(x >0) f(x-1);
>> system.time(f(10000000))
> Error: C stack usage is too close to the limit
> Error: C stack usage is too close to the limit
>> f1<-function(x) x-1
>> f <- function(x) f1(x);
>> system.time(f(10000000))
>   user  system elapsed
>      0       0       0
>
>

You may be a bit misinformed about with tail recursion means - it still needs to evaluate the function for each recursion step, the only difference is that in such special case there is no additional information that needs to be stored -- and you have also proven why it's not as simple as you think:

> f <- function(x) if(x >0) f(x-1)
> (f(100))
NULL

> f1<-function(x) x-1
> f <- function(x) f1(x);
> (f(100))
[1] 99

Your latter version doesn't actually do anything anywhere close to the recursion you defined. R doesn't have tail recursion elimination and as Thomas pointed out in the cited post it would break some existing things if it did (call frame introspection etc.). [Whether it would be ok to break it for the sake of optimization is another question]

Note that in all such cases you can easily write the problem in an iterative fashion (admittedly it is less elegant -- but if you are dealing with such deep structures chances are that you probably care about efficiency and to go native code anyway).

Cheers,
Simon

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: [R-sig-hpc] recursion depth limitations

Suzen, Mehmet
On 14 December 2012 13:46, Simon Urbanek <[hidden email]> wrote:
> You may be a bit misinformed about with tail recursion means - it still needs to evaluate the function for each recursion step, the only difference is that in
> such special case there is no additional information that needs to be stored -- and you have also proven why it's not as simple as you think:

Thank you Simon for your time and patient reply. I was thinking
calling another function over again is called indirect recursion.

> f <- function(x) if(x >0) f(x-1)
> (f(100))
NULL

> f1<-function(x) x-1
> f <- function(x) f1(x);
> (f(100))
[1] 99

>> Your latter version doesn't actually do anything anywhere close to the recursion you defined.

I see what you mean. I was confused. My intention was having 100 calls
in the second one with f1 as well.
Maybe I can make the point with using another example via mutual
recursion, 'fibRping/pong' below.
But I was thinking 'fibRping' version would need less memory then the
plain recursion, which I now understand
that I was mistaken. Every call counts then. Even though I had an
impression that  calling the same
function more then once like fibRping/pong would not create additional
memory requirement ... (Probably the issue is noting to do with
Rs internals though..

Using Dirk's blog entry (http://dirk.eddelbuettel.com/blog/2011/09/08/) :
## R implementation of recursive Fibonacci sequence
fibR <- function(n) {
    if (n == 0) return(0)
    if (n == 1) return(1)
    return (fibR(n - 1) + fibR(n - 2))
}


# Now Mutual recursion
fibRping  <- function(n) {
    if (n == 0) return(0)
    if (n == 1) return(1)
    return (fibRpong(n - 1) + fibRpong(n - 2))
}
fibRpong  <- function(n) {
    if (n == 0) return(0)
    if (n == 1) return(1)
    return (fibRping(n - 1) + fibRping(n - 2))
}

options(expressions=500000)
fibR(50000)> options(expressions=500000)
> fibR(50000)
Error: C stack usage is too close to the limit
> fibRping(50000)
Error: C stack usage is too close to the limit

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.