[dmd-concurrency] shared arrays

[Kevin Bealer]

On Thu, Jan 14, 2010 at 10:20 PM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> Michel Fortin wrote:
>
>> Le 2010-01-14 à 22:01, Andrei Alexandrescu a écrit :
>>
>>  Michel Fortin wrote:
>>>
>>>> Le 2010-01-14 à 18:07, Andrei Alexandrescu a écrit :
>>>>
>>>>> Unfortunately, this(this) is called after the bits have been
>>>>> copied, so if there was any tearing, it already happened. I don't
>>>>> know how we can solve this.
>>>>>
>>>> Where is the copy-constructor when we need one? :-)
>>>>
>>> I realized that fortunately that's not a problem: during memcpy, the
>>> target is not yet shared. Whew. So it all holds water.
>>>
>>> this(this) shared { ... }
>>>
>>> should work.
>>>
>>
>> But the source is shared. Couldn't it be updated while memcpy does its
>> work, creating an incoherent state? Something like: memcpy copies half of
>> it, context switch, other thread update first and last bytes, context
>> switch, memcpy finishes its work. Result, last byte of the copy doesn't
>> match first byte.
>>
>
> I just meant that we're not constrained by the memcpy prior to this(this).
>
> I don't know whether we should disallow such copies. Probably we should,
> but I don't have a strong case. If we disable it, cowboys will be unhappy.
> If we enable it, others will.
>
> The problem is, if we disable even "this(this) shared" there's no chance to
> copy a shared object, even if you're willing to fix the inconsistencies.
>
>
>  Now, the really tricky question is should this one be copyable when
>>>> shared:
>>>> struct D { immutable string a; long b; }
>>>> Since 'a' is immutable, you don't need to copy it atomically, only
>>>> 'b' requires an atomic copy. So copying the struct "atomically" is
>>>> possible by copying 'a' normally and 'b' atomically. Now, is that
>>>> going to be supported?
>>>>
>>> But long isn't atomically copyable. Did you mean int?
>>>
>>
>> Well, that depends on the architecture. I meant a type which is atomically
>> copyable yes.
>>
>
> Speaking of which: is it reasonable to assume that all 32-bit modern
> architectures have a 64-bit atomic assign? How about 64-bit atomic CAS?
>
>
> Andrei
>
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>

Could you create a global array of something like 256 spinlocks, and then
hash the pointer to what you are trying to modify to find the right lock?
The shared operation (read or write) will consist of getting the lock,
accessing the object in question, then releasing the lock.  This requires
two CAS like operations to lock any sized object rather than one CAS for
four bytes.  With 256 such locks, we should be able to keep a lot of threads
busy even with the occasional accidental contention.

The first tricky thing is how to deal with thread death during a shared
operation.  If you use the thread number as what is swapped into the
spinlock, you can clean up when threads die.

The second tricky thing is nested objects, e.g. how can you tell if the
object you are fiddling with is locked at a higher level? I think you can do
so by dividing memory into non-overlapping regions (say,. cache line sized,
which I think is 64 bytes) and locking all of those that the object overlaps
with instead of locking by object.  This multiplies the number of CAS steps
for larger objects, and you need to be tricky with the hashing of the
pointer (you need a hash function such that a 256 byte object can't deadlock
to itself due to colliding hashes) but I think it could still work.

The final bit of the design is that if your architecture can do atomic ops
on objects of 8 or 16 bytes, then you can just use a normal CAS, for that
specific object.  Since normal lock free designs tend to fall into the case
where the compiler knows this integer

Note that some parts of the above rely on knowing the object size.  This
might be tricky in some special cases but usually, I would think it is
available to the compiler and when it isn't you could use the GC to find it
as with dynamic array expansion.

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100115/dc3f6d72/attachment.htm>