Having implemented the array append patch to fix stomping, and reading the dmd-concurrency debate, I realized that what I implemented is no good for shared arrays.

In fact, I wonder how shared arrays can support any array operations:

struct S
{
   int x;
   int y;
}

struct T
{
   shared int x;
   int y;
}

shared(S)[] arr;
T[] arr2;


what happens when you call arr.dup or arr ~= shared(S)(1,2)?  What about arr2?

In the current code, the type is just used to figure out the size, and the code calls memcpy to actually copy the data.  My biggest worry is arr2 because shared isn't even in the typeinfo passed, it's buried as a member.

What happens in cases like this:

shared(S)[] arr3;
arr3[] = arr2[];

any ideas of how this can be resolved?  Should shared arrays enjoy all the operations that normal arrays have?

-Steve

Le 2010-01-14 ? 7:10, Steve Schveighoffer a ?crit :

> 
> What happens in cases like this:
> 
> shared(S)[] arr3;
> arr3[] = arr2[];
> 
> any ideas of how this can be resolved?  Should shared arrays enjoy all the operations that normal arrays have?

Well, you need a lock.

Perhaps the runtime could maintain a shared pool of locks for those operations. You'd need to first hash the address of the allocated memory block (which is not necessary the first element, so you'll need the GC to tell you). This hash gives you the index of a mutex in the pool to use, the idea being that it's always the same mutex for a given memory block. Some memory blocks will share the same mutex, but if the pool is big enough two threads wanting the same mutex for a different memory block shouldn't happen too often.

The copy operation can't take any other lock though, or else you risk having deadlocks. This might be a problem when copying a struct.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

----- Original Message ----

> From: Michel Fortin <michel.fortin at michelf.com>
> 
> Le 2010-01-14 ? 7:10, Steve Schveighoffer a ?crit :
> 
> > 
> > What happens in cases like this:
> > 
> > shared(S)[] arr3;
> > arr3[] = arr2[];
> > 
> > any ideas of how this can be resolved?  Should shared arrays enjoy all the
> operations that normal arrays have?
> 
> Well, you need a lock.

Whatever locks that must be taken must also be taken any time an array is accessed.

For instance you'd need to take the same lock when doing:

arr2[3].x = 5;

I don't think this is a workable solution.

This is the same solution I erroneously used when doing a shared append -- I created a global lock for appends to all shared arrays.  This works to synchronize appending, but writes to the array from another thread would compromise the integrity of the data.

> Perhaps the runtime could maintain a shared pool of locks for those operations. You'd need to first hash the address of the allocated memory block (which is not necessary the first element, so you'll need the GC to tell you). This hash gives you the index of a mutex in the pool to use, the idea being that it's always the same mutex for a given memory block. Some memory blocks will share the same mutex, but if the pool is big enough two threads wanting the same mutex for a different memory block shouldn't happen too often.
> 
> The copy operation can't take any other lock though, or else you risk having deadlocks. This might be a problem when copying a struct.

You can ensure the order of locks by sorting them (if you need 2 locks at once).

But again, I'm not sure how this prevents having to take a lock on every access to any array data, which makes the system not really scale well.  I think we may need to find a way to do this without locks (i.e. use shared semantics) or else disallow these kinds of operations on shared arrays.  Just using shared semantics would not prevent all corruption issues, but I think at that point a lock-protected array library type is in order.

The one problem I still have no idea how to solve is the "partially shared" element type as T is:

struct T
{
   shared int x;
   int y;
}

-Steve

On Jan 14, 2010, at 4:10 AM, Steve Schveighoffer wrote:

> Having implemented the array append patch to fix stomping, and reading the dmd-concurrency debate, I realized that what I implemented is no good for shared arrays.
> 
> In fact, I wonder how shared arrays can support any array operations

I sent an email about this a while back.  In short, if we're going to allow array ops on shared arrays at all I think they'll have to use atomic ops to "lock" the array for the length of the update.  Basically, set the 1 bit of the ptr field to indicate the array is locked.  This gets tricky when more than one shared array is involved because the lock has to be acquired on each, and because different ops may try to lock arrays in different orders, if a spinlock acquire times out the code will have to release all the locks it's acquired, wait some random interval, and try again.  Pretty complicated stuff if the goal is just to support shared array ops.

On Jan 14, 2010, at 4:38 AM, Michel Fortin wrote:

> Le 2010-01-14 ? 7:10, Steve Schveighoffer a ?crit :
> 
>> 
>> What happens in cases like this:
>> 
>> shared(S)[] arr3;
>> arr3[] = arr2[];
>> 
>> any ideas of how this can be resolved?  Should shared arrays enjoy all the operations that normal arrays have?
> 
> Well, you need a lock.
> 
> Perhaps the runtime could maintain a shared pool of locks for those operations. You'd need to first hash the address of the allocated memory block (which is not necessary the first element, so you'll need the GC to tell you). This hash gives you the index of a mutex in the pool to use, the idea being that it's always the same mutex for a given memory block. Some memory blocks will share the same mutex, but if the pool is big enough two threads wanting the same mutex for a different memory block shouldn't happen too often.

Yeah, that's the other option.  Probably not too bad, since shared array ops should be fairly uncommon.

On Jan 14, 2010, at 5:04 AM, Steve Schveighoffer wrote:

> ----- Original Message ----
> 
>> From: Michel Fortin <michel.fortin at michelf.com>
>> 
>> Le 2010-01-14 ? 7:10, Steve Schveighoffer a ?crit :
>> 
>>> 
>>> What happens in cases like this:
>>> 
>>> shared(S)[] arr3;
>>> arr3[] = arr2[];
>>> 
>>> any ideas of how this can be resolved?  Should shared arrays enjoy all the
>> operations that normal arrays have?
>> 
>> Well, you need a lock.
> 
> Whatever locks that must be taken must also be taken any time an array is accessed.
> 
> For instance you'd need to take the same lock when doing:
> 
> arr2[3].x = 5;
> 
> I don't think this is a workable solution.

This isn't bad for indexes ops, but taking the address of a shared array element is a huge problem, since information about the underlying array is lost.  This makes C-style array operations totally unfeasible for shared arrays, and this is when the data is simply shared, the atomic ops were only needed when the ref itself was shared.  Darnit.

----- Original Message ----

> From: Sean Kelly <sean at invisibleduck.org>
> On Jan 14, 2010, at 4:10 AM, Steve Schveighoffer wrote:
> 
> > Having implemented the array append patch to fix stomping, and reading the
> dmd-concurrency debate, I realized that what I implemented is no good for shared arrays.
> > 
> > In fact, I wonder how shared arrays can support any array operations
> 
> I sent an email about this a while back.  In short, if we're going to allow array ops on shared arrays at all I think they'll have to use atomic ops to "lock" the array for the length of the update.  Basically, set the 1 bit of the ptr field to indicate the array is locked.  This gets tricky when more than one shared array is involved because the lock has to be acquired on each, and because different ops may try to lock arrays in different orders, if a spinlock acquire times out the code will have to release all the locks it's acquired, wait some random interval, and try again.  Pretty complicated stuff if the goal is just to support shared array ops.

This does not work:

shared(char)[] x;

void foo()
{
   shared(char)[] y = x;
   y[] = "hi"; // how does this now lock the 1 bit in x?
}

You'd need to lock the array data itself.  But in any case, I think it may be too ideal to think we can support atomic array operations without manual synchronization.  I.e., a SynchronizedArray type similar to UniqueArray type may be required for this.

I was thinking more in the case, how to write the runtime so it handles atomic updates of the actual array data, meaning at least word-sized data isn't messed up.  I have no idea if things like this should be possible on shared arrays:

a[] = b[] + 5 + c[];

The simple case of data copying may be acceptable, since you simply want to do a shared read of each data item, and a shared write to the target.

But in any case, I don't know how to handle cases where data is a hybrid -- some data shared and some not shared.

-Steve

On Jan 14, 2010, at 7:27 AM, Steve Schveighoffer wrote:
> 
> This does not work:
> 
> shared(char)[] x;
> 
> void foo()
> {
>   shared(char)[] y = x;
>   y[] = "hi"; // how does this now lock the 1 bit in x?
> }

Yeah, the atomic ops were just for "shared char[]", ie. for updating the reference itself. You're right that the data has to be locked for data-level updates.  And slices, pointers, etc, make this a big problem for automatic locking.

> You'd need to lock the array data itself.  But in any case, I think it may be too ideal to think we can support atomic array operations without manual synchronization.  I.e., a SynchronizedArray type similar to UniqueArray type may be required for this.
> 
> I was thinking more in the case, how to write the runtime so it handles atomic updates of the actual array data, meaning at least word-sized data isn't messed up.  I have no idea if things like this should be possible on shared arrays:
> 
> a[] = b[] + 5 + c[];

I don't know that they can be, sadly.

On Jan 14, 2010, at 7:33 AM, Sean Kelly wrote:

> On Jan 14, 2010, at 7:27 AM, Steve Schveighoffer wrote:
> 
>> You'd need to lock the array data itself.  But in any case, I think it may be too ideal to think we can support atomic array operations without manual synchronization.  I.e., a SynchronizedArray type similar to UniqueArray type may be required for this.
>> 
>> I was thinking more in the case, how to write the runtime so it handles atomic updates of the actual array data, meaning at least word-sized data isn't messed up.  I have no idea if things like this should be possible on shared arrays:
>> 
>> a[] = b[] + 5 + c[];
> 
> I don't know that they can be, sadly.

Regarding my earlier comment, I think I misspoke.  An operation on shared array data could get the base pointer for the block from the GC and use that to obtain a lock.  The compiler could theoretically optimize where locks are acquired for loop operations too, at least in simple cases.  This all smells like a hack though.

(Replying to no message in particular.) I think there's a bit of a conflation of terms. There are two distinct types:

shared(T)[]

and

shared(T[])

The latter is often denoted as "shared T[] value;", i.e. without parens.

The former type is relatively simple: the array itself offers access to references of its elements, which in turn obey normal rules for shared(T). In particular, bulk updates like a[] = b[] are semantically equivalent to foreach loops, and therefore we don't need to worry about defining their semantics.

I think most of the discussion is centered around the latter type. The language does not have two-word atomic assignments and therefore shared(T[]) is basically unusable unless you e.g. use it as a member inside a class with synchronized method, in which case it becomes tail-shared, namely shared(T)[] (wow).


Andrei