[dmd-concurrency] What is protected by synchronization?

[Robert Jacques]

On Sun, 31 Jan 2010 16:33:12 -0500, Kevin Bealer <kevinbealer at gmail.com>  
wrote:

> On Sun, Jan 31, 2010 at 4:09 PM, Robert Jacques <sandford at jhu.edu> wrote:
>
>> On Sun, 31 Jan 2010 13:52:59 -0500, Kevin Bealer <kevinbealer at gmail.com>
>> wrote:
>>
>>> On Sun, Jan 31, 2010 at 7:51 AM, Michel Fortin  
>>> <michel.fortin at michelf.com
>>> >wrote:
>>> ...
>>>
>>>
>>>> Something 'unique' is accessible through only one reference in the  
>>>> whole
>>>> program, it is guarantied to have no aliasing. With 'lent' you can  
>>>> lend a
>>>> unique reference to a function: you know once it returns your  
>>>> reference
>>>> is
>>>> still unique. As long as this 'unique' property holds, you can safely
>>>> *move*
>>>> the reference between threads. As long as the unique reference is kept
>>>> thread-local you can access it without atomic operations or locks.
>>>> 'unique'
>>>> can be seen as a temporary state as you can safely move it to  
>>>> immutable,
>>>> mutable, shared, etc.
>>>>
>>>> Andrei wants to implement unique as a template, but it'll be very  
>>>> limited
>>>> without 'lent'. If I remember well, there's no general Unique  
>>>> template,
>>>> just
>>>> a UniqueArray for arrays of primitive types. Arrays of structs would
>>>> allow
>>>> taking the address of struct members and create aliasing.
>>>>
>>>>
>>> I want to point out that this is only true if there is a memory  
>>> barrier at
>>> the point of lending.  If object X belongs uniquely to thread 1, and it
>>> gets
>>> lent to thread 2, a memory barrier should happen at this point.  There  
>>> are
>>> several cases where you can get hurt if this is not done:
>>>
>>> 1. The object might have been owned by thread 2, then given to thread  
>>> 1,
>>> which modified it, then returned to thread 2.  In this case, the second
>>> transfer is problematic because there might be a cached copy of the
>>> original
>>> in thread 2's L1 or L2 cache.
>>>
>>> 2. The object might have been in the same cache line with another  
>>> object
>>> that was modified, causing unintentional caching, and thus  
>>> snapshotting a
>>> previous version of the object's state.
>>>
>>> 3. Some other code might have fiddled with the object even though it is
>>> 'unique' -- for example, the global garbage collector might have been  
>>> run
>>> by
>>> thread 2, causing thread 2 to "see" a bunch of things that thread 1  
>>> thinks
>>> it uniquely owns.  This is going to be garbage collector design  
>>> dependent,
>>> e.g. the GC might always do a memory barrier just before returning  
>>> control
>>> to the user, in which case, no problem.
>>>
>>> The unique concept is a good thing but care must be taken -- I think
>>> Andrei's template version of the unique concept should be perfectly  
>>> safe
>>> due
>>> to the fact that it does a copy.  It would be more efficient if a  
>>> memory
>>> barrier could be used but that doesn't help with the analytical problem
>>> (making sure the old thread doesn't have a pointer stuck somewhere.)
>>>
>>> I just wanted to knock down what I think is a dangerous idea that some
>>> people might have inferred from the discussion on 'unique' -- that  
>>> thread
>>> X
>>> cannot have cached something if it was never 'seen' by thread X before.
>>>  For
>>> that matter, I'm not sure but without hard thread affinity, the CPU  
>>> might
>>> have a cached version of something even if it the 'thread' never saw it
>>> because the last thread to run there saw it.  (Or does thread switching
>>> always incur a memory barrier -- I don't know much about how that is
>>> usually
>>> done.)
>>>
>>> Kevin
>>>
>>
>> This is a good point, but this has already been discussed and resolved  
>> in
>> previous discussions. In essence, the all the ways for a unique object  
>> to
>> move between threads involve memory barriers of their own which in turn
>> protects the publication safety of both unique and immutable objects.  
>> As for
>> the cache line issues, these are generally know as false sharing, and  
>> while
>> they can be a major performance issue, they do not effect program
>> correctness. Also, the problem with Andrei's library type is that it's
>> shallow and not transitive. Lastly, lent doesn't refer to passing things
>> between threads. It is like const, a super-type which allows a function  
>> to
>> take a shared, local, owned or unique object in an agnostic manner, by
>> providing the guarantee that it won't squirrel away (escape) it  
>> somewhere.
>>
>>
> Okay, I guess I missed or skimmed those discussions.  Thanks for the
> details.
>
> Kevin

No problem. Those discussions were on the regular newsgroup a while ago  
and on Bartosz's blog.