From luke at stat.uiowa.edu  Sat Jan  2 21:05:20 2010
From: luke at stat.uiowa.edu (luke at stat.uiowa.edu)
Date: Sat, 2 Jan 2010 14:05:20 -0600 (CST)
Subject: [Rd] R-devel Digest, Vol 83, Issue 2
In-Reply-To: <4B3FA43B.1070707@stats.uwo.ca>
References: <mailman.11.1262430004.8711.r-devel@r-project.org>
	<4B3F7625.1080806@gmail.com> <4B3F7ACD.2050106@stats.uwo.ca>
	<4B3F7F8D.8060701@gmail.com>
	<B38057DF-8452-41FC-9D46-B67FBD58E01C@r-project.org>
	<4B3FA43B.1070707@stats.uwo.ca>
Message-ID: <alpine.DEB.1.00.1001021359270.6403@luke-inspiron>

On Sat, 2 Jan 2010, Duncan Murdoch wrote:

> Simon Urbanek wrote:
>> On Jan 2, 2010, at 12:17 PM, Laurent Gautier wrote:
>>
>> 
>>> On 1/2/10 5:56 PM, Duncan Murdoch wrote:
>>> 
>>>> On 02/01/2010 11:36 AM, Laurent Gautier wrote:
>>>> 
>>>>> [Disclaimer: what is below reflects my understanding from reading the
>>>>> R source, others will correct where deemed necessary]
>>>>> 
>>>>> On 1/2/10 12:00 PM, r-devel-request at r-project.org wrote:
>>>>> 
>>> (...)
>>>
>>> 
>>>>>> I'd also be interested if there is some ideas on the relative 
>>>>>> efficiency
>>>>>> of the preserve/release mechanism compared to PROTECT/UNPROTECT.
>>>>>> 
>>>>> PROTECT/UNPROTECT is trading granularity for speed. It is a stack with
>>>>> only tow operations possible:
>>>>> - push 1 object into the stack
>>>>> - pull (unprotect) N last objects from the stack
>>>>> 
>>>> UNPROTECT_PTR is also possible, which does a linear search through the
>>>> stack and unprotects something possibly deep within it. There is also
>>>> REPROTECT which allows you to replace an entry within the stack.
>>>> 
>>>> I would guess that UNPROTECT_PTR is more efficient than RecursiveRelease
>>>> because it doesn't use so much stack space when it needs to go deep into
>>>> the stack to release, but it is possible the compiler recognizes the
>>>> tail recursion and RecursiveRelease is implemented efficiently. In that
>>>> case it could be more efficient than UNPROTECT_PTR, which has to move
>>>> all the other entries down to fill the newly vacated space. Really the
>>>> only reliable way to answer efficiency questions like this is to try
>>>> both ways and see which works better in your application.
>>>> 
>>> Thanks. I did not know about UNPROTECT_PTR.
>>> I had concerns over the stack usage, but so far it did not prove too much 
>>> of a problem. Still, why isn't the tail recursion explicitly made an 
>>> iteration then ? This would take the "may be the compiler figures it out, 
>>> may be not" variable out of the equation.
>>>
>>> 
>> 
>> Careful - the protection stack (bookkeeping by R) has nothing to do with 
>> the C function call stack hence it has nothing to do with the compiler. The 
>> protection stack is global so usually you don't run out of it unless 
>> something goes horribly wrong (=infinite loop).
>> 
>
> I think Laurent was referring to RecursiveRelease, which could use a lot of C 
> stack if you choose to release something that is deep in the list, since it 
> checks the head, and if that doesn't match, calls itself again on the rest of 
> the list.  (I checked, and at least one version of gcc doesn't recognize the 
> tail recursion:  it really does generate a recursive call.)

I believe current gcc -O2 does optimize tail recursive calls (more
generally sibling calls) but RecursiveRelease isn't written as a tail
recursion -- the return vaule is used in an assignment.  In any case
it would probably make more sense to rewrite RecursiveRelease to not
use recursion at all, but I'm not motivated to do that at this point.

luke

>
> Laurent asked why it isn't optimized to avoid the recursion:  I think the 
> answer is simply because it is so rarely used that nobody has bothered.
>
> Duncan Murdoch
>>
>> 
>>>> Another possibility is to maintain your own list or environment of
>>>> objects, and just protect/preserve the list as a whole.
>>>> 
>>> Interesting idea, this would let one perform his/her own bookkeeping on 
>>> the list/environment. How is R garbage collection checking contained 
>>> objects ? (I am thinking performances here, and may be cyclic references).
>>>
>>> 
>> 
>> You don't really want to care because the GC is global for all objects (and 
>> cycles are supported by the GC in R) - so whether you keep it yourself or 
>> Preserve/Release is practically irrelevant (the protection stack is handled 
>> separately).
>> 
>> As for keeping your own list -- if you really care about performance that 
>> much (to be honest in vast majority of cases it doesn't matter) you have to 
>> be careful how you implement it. Technically the fastest way is 
>> preallocated generic vector but it really depends on how you deal with the 
>> access so you can easily perform worse than Preserve/Release if you're not 
>> careful.
>> 
>> As a side note - the best way (IMHO) to deal with all those issues is to 
>> use external pointers because a) you get very efficient C finalizers b) you 
>> can directly (and very efficiently) tie lifespan of other objects to the 
>> same SEXP and c) as guardians they can nicely track other objects that hold 
>> them.
>> 
>> Cheers,
>> Simon
>> 
>> 
>>
>> 
>>> L.
>>> 
>>>
>>> 
>>>> Duncan Murdoch
>>>>
>>>> 
>>>>> HTH,
>>>>> 
>>>>> 
>>>>> L.
>>>>> 
>>>>> 
>>>>> 
>>>>>
>>>>> 
>>>>>> Thanks,
>>>>>> 
>>>>>> Romain
>>>>>> 
>>>>>> [1]http://lists.r-forge.r-project.org/pipermail/rcpp-devel/
>>>>>> [2]
>>>>>> http://r-forge.r-project.org/plugins/scmsvn/viewcvs.php/pkg/src/RObject.cpp?rev=255&root=rcpp&view=markup
>>>>>> 
>>>>>> 
>>>>>> -- Romain Francois Professional R Enthusiast +33(0) 6 28 91 30 30
>>>>>> http://romainfrancois.blog.free.fr |- http://tr.im/IW9B : C++ 
>>>>>> exceptions
>>>>>> at the R level |- http://tr.im/IlMh : CPP package: exposing C++ objects
>>>>>> `- http://tr.im/HlX9 : new package : bibtex
>>>>>> 
>>>>> ______________________________________________
>>>>> R-devel at r-project.org mailing list
>>>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>>>> 
>>> ______________________________________________
>>> R-devel at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>> 
>>>
>>> 
>> 
>> 
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>

-- 
Luke Tierney
Chair, Statistics and Actuarial Science
Ralph E. Wareham Professor of Mathematical Sciences
University of Iowa                  Phone:             319-335-3386
Department of Statistics and        Fax:               319-335-3017
    Actuarial Science
241 Schaeffer Hall                  email:      luke at stat.uiowa.edu
Iowa City, IA 52242                 WWW:  http://www.stat.uiowa.edu



[Rd] R-devel Digest, Vol 83, Issue 2
luke at stat.uiowa.edu