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. |
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. |
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. |
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. |
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. |
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. |
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. |
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. |
Free forum by Nabble | Edit this page |