draft proposal for ref counting in D

[Rainer Schuetze]

On 14.10.2013 19:50, John Colvin wrote:
> On Monday, 14 October 2013 at 17:43:33 UTC, Rainer Schuetze wrote:
>>
>>
>> On 13.10.2013 19:05, Sönke Ludwig wrote:
>>> Am 13.10.2013 17:15, schrieb Sean Kelly:
>>>> On Sunday, 13 October 2013 at 07:03:39 UTC, Rainer Schuetze wrote:
>>>>>
>>>>> According to the "Handbook of Garbage Collection" by Richard Jones
>>>>> eager lock-free reference counting can only be done with a cas2
>>>>> operation modifying two seperate locations atomically (algorithm 18.2
>>>>> "Eager reference counting with CompareAndSwap is broken"). This might
>>>>> be the quoted paper:
>>>>> http://scholr.ly/paper/2199608/lock-free-reference-counting
>>>>>
>>>>> Unfortunately the CAS2 operation does not exist in most processors.
>>>>
>>>> I suppose it's worth noting that Boost (and now standard C++) has a
>>>> shared_ptr that works across threads and the implementation I've seen
>>>> doesn't use a mutex.  In fact, I think the Boost one doesn't even use
>>>> CAS on x86, though it's been quite a few years so my memory could be
>>>> wrong on that last detail.
>>>
>>> I didn't read the paper, but I'd suspect that the paper refers to the
>>> case where both, the reference count _and_ the reference is thread-safe,
>>> since the boost/c++ shared_ptr only has a thread-safe reference count
>>> after all.
>>
>> I haven't read it either, but AFAICT the cas2 operation is used two
>> modify the pointer and the reference count at the same time atomically.
>>
>> I just checked boost::shared_ptr, it uses cas operations on the
>> reference counts. It has the same problem as described in my example,
>> see the read/write example 3 here:
>> http://www.boost.org/doc/libs/1_54_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety
>>
>>
>> boost::shared_ptr is also unsafe with respect to calling member
>> functions through "->" as it doesn't increment the reference count.
>
> I'm totally out of my depth here but can't you store the reference count
> adjacent to the pointer and use CMPXCHG16B

This might work for a single pointer, but not if you have multiple 
pointers to the same object.