Escaping the Tyranny of the GC: std.rcstring, first blood

[Rainer Schuetze via Digitalmars-d]

On 16.09.2014 00:44, Andrei Alexandrescu wrote:
> On 9/15/14, 10:22 PM, Rainer Schuetze wrote:
>>
>>
>> On 15.09.2014 21:49, Andrei Alexandrescu wrote:
>>> On 9/15/14, 12:43 PM, po wrote:
>>>>
>>>>> As I understand the issue it works if you make sure to transfer
>>>>> ownership explicitly before the other thread gains access?
>>>>>
>>>>> Maybe this is more clear:
>>>>>
>>>>> http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>   Ah, I think I follow.
>>>>
>>>> So in C++ terms:
>>>>   It basically requires either a global shared_ptr, or that you passed
>>>> one around by reference between threads. And that you then killed it in
>>>> one thread at the exact moment the control block was read in another
>>>> thread. That blog post discusses a solution, I wonder if that is
>>>> implemented in C++'s shared_ptr?
>>>
>>> No, and it neeedn't. The article is not that good. In C++, if a thread
>>> must increment a reference counter while it's going to zero due to
>>> another thread, that's 100% a programming error, not a concurrency
>>> error. That's a well known and well studied problem. As an aside,
>>> searching the net for differential reference counting yields pretty much
>>> only this article.

Here is a link with a discussion, links and code:

https://groups.google.com/forum/#!topic/comp.programming.threads/6mXgQEiAOW8

It seems there were multiple patents claiming invention of that technique.

>>
>> Huuh? So you must not read a reference to a ref-counted object that
>> might get changed in another thread?
>
> I didn't say that.
>
>> Maybe you mean destruction of the
>> shared pointer?
>
> I meant: by the time the smart pointer got to the thread, its reference
> count has increased already.
>

This works if you use message passing. The issue exists for 
"shared(shared_ptr!T)". It might be bad style, but that is a convention 
not enforced by the language.

Incidentally, Herb Sutter used "shared_ptr<T>" as a means to implement 
lock-free linked lists in his talk at the CppCon. To avoid issues, the 
list head has to be "atomic<shared_ptr<T>>". Which currently needs a 
lock to do an assignment for similar reasons. ;-o He said there might be 
ways around that...

>> Please note that the scenario is also described by Richard Jones in his
>> 2nd edition of the "Handbook of Garbage Collection" (see algorithm 18.2
>> "Eager reference counting with CompareAndSwap is broken").
>
> I agree such a problem may occur in code generated automatically under
> the wraps for high-level languages, but not with shared_ptr (or COM
> objects etc).

I agree it is worse if the mechanism is hidden by the system, pretending 
you are dealing with a single pointer. I'm not yet ready to  accept it 
doesn't exist elsewhere.

Coming back to RCString, immutable(RCString) does not have this problem, 
because it must not be modified by any thread. Working with 
shared(RCString) isn't supported without a lot of overloads, so you'll 
have to synchronize externally and cast away shared.