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