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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100131/65cae520/attachment.htm>

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.