[dmd-concurrency] synchronized, shared, and regular methods inside the same class

[Sean Kelly]

On Jan 6, 2010, at 9:54 AM, Michel Fortin wrote:

> Le 2010-01-06 à 11:42, Sean Kelly a écrit :
> 
>> So how about a quick summary to figure out where we are?  From memory, I think it's pretty well established that:
>> 
>> 1. shared denotes visibility.  A global shared variable is visible from all threads, an unlabeled variable is thread-local.
>> 2. Attaching the shared property to a class instance affects method visibility.  shared and synchronized methods are visible, unlabeled ones are not.
>> 3. Attaching the shared property to a value makes that value effectively atomic.  All access and mutation is accomplished via library calls.
>> 
>> I think there was some concern about the shared property of a class instance automatically extending to all of its fields.  Were there other concerns as well?  I know that Jason had mentioned issues with non-statically verifiable shared semantics in general, but that's another ball of wax entirely.
> 
> Given all the examples I've seen, I'm a little concerned that synchronization will only work with class members. What about structs and shared globals? Is there going to be a safe way to keep them synchronized? Or is that irrelevant?

I think we've already discussed how language-defined value types will work in the discussion regarding class fields, but there are probably a few things worth mentioning:

shared int x; // 1
shared MyClass y; // 2
shared(MyClass) z; // 3

In case 1, the value is visible across all threads and must be operated on using the atomic() routines.  In case 3, the reference is local but the class instance is shared, so only shared or synchronized methods may be called, etc.  In case 2, the reference is shared and the instance is shared as well, so only shared and synchronized methods may be called on the instance, but obtaining the reference must be done via the atomic() routines.  ie. "atomic(y).doSomething()."  In this case it may be worth having the compiler make the atomic() bit implicit if the only thing being done is calling a member function, but that raises questions about what happens with operator overloading, etc.  I'm inclined to say that the atomic() must be present, since it's consistent with how everything else works and better communicates what's actually happening.

For structs I was inclined to say that the compiler could inject a monitor pointer like it does with nested structs, but I think the problems outweigh the benefits--memory layout is affected, things get weird with copying, etc.  So I think Andrei has the right of it in that synchronization is left up to the user.  And since we have a Mutex class in druntime, hopefully this won't be too onerous.

For built-in fancy types, since associative arrays are referenced via a plain old pointer just like classes I think they can work essentially the same way.  A "shared int[string]" can lock and unlock an internal mutex on accesses, and modifying the reference itself could be done using atomic().

For delegates, I'm not sure what's done today.  I guess there are two cases:

class MyClass {
    void fnA() synchronized {}
    void fnB() shared {}
}

auto x = new MyClass;
auto y = &x.fnA;
auto z = &x.fnB;

I'd guess that the type of y is "delegate() synchronized" and the type of z is "delegate() shared"?  Assuming this is right, then it seems like the mutex would be locked when y is called, and the appropriate thing would happen when z is called as well.

That leaves arrays, which are a tad more complicated because they have both a length and a pointer field.  Let's see:

shared int[] x;
x ~= 42; // 1
x = x[1 .. 2]; // 2
x = [1, 2] ~ x; // 3

Case 1 may require a reallocation with the append, so both the pointer and length will be modified as well as the assignment of 42.  I imagine this could be done lock-free, but it won't be trivial.  Case 2 means both a pointer and length reassignment as well, and case 3 is just a disaster.  The easiest thing would just be to synchronize all shared array operations on the same mutex and document that weird things could still occur in complex expressions.  This would be abysmal in terms of concurrency, but it's about as safe as such things can be.  Hm... let's see if immutable arrays are any better:

shared string x;
shared string y;
x = x ~ 'a'; // 1
x = 'a' ~ x; // 2
x = y;

In cases 1 and 2, all we really need to worry about is the assignment to x.  On recent x86 we should be able to use 8 byte CAS to do it in one shot, but on other architectures the algorithm seems more complicated.  I'd need to poke around to see if there's a published algorithm for updating two values together, but here's a shot at it that uses a special value assigned to the array pointer as a sentinel:

struct Array { size_t len; byte* ptr; }

/**
 * string is a value type so "shared string" is effectively "shared(Array)"
 * y is a new array created from the expression "'a' ~ x" so there's no contention to worry about,
 * perhaps this makes it safe to eliminate the "shared" from the y parameter?  let's assume so,
 * since it makes the code easier to write.
 */
void assignUnique( ref shared(Array) x, ref Array y ) {
    byte* p_old;
    // use p_old.max as a sentinel to indicate that another atomic assignment
    // is in progress, since we'll likely never see this value in practice (?)
    do {
         p_old = atomicLoad( x.ptr );
    } while( p_old == p_old.max || !atomicStoreIf( x.ptr, p_old.max, p_old ) );
    atomicStore( x.len, y.len );
    atomicStore( x.ptr, y.ptr );
}

In case 3 you have to worry about a consistent read from y as well as a consistent write to x.  A double-wide CAS comes to the rescue again for both the read and write, but without it... I dunno.  I guess you could use the same sentinel approach for both the read of y and the write to x, but again, maybe there's something better.  I really don't do much "real" lock-free programming so I'm not up on all the latest algorithms, I just grok the mechanics.