draft proposal for ref counting in D

[John Colvin]

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