From lgautier at gmail.com  Sat Jan  2 21:16:59 2010
From: lgautier at gmail.com (Laurent Gautier)
Date: Sat, 02 Jan 2010 21:16:59 +0100
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: <4B3FA9BB.90302@gmail.com>

On 1/2/10 8:53 PM, 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.)
>
> 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.

Yes, I was referring to RecursiveRelease. Sorry if this was not clear.

What are the chances for a patch to be accepted ? At first sight(*), 
making that tail recursion an iterative function is not a major 
undertaking, and reviewing the patch be fairly straightforward... but I 
can always use that time otherwise if the answer to the question is "nil".


L.



> 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
>>>
>>>
>>
>



[Rd] R-devel Digest, Vol 83, Issue 2
Laurent Gautier