This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:

class A {
     void foo() synchronized;
     void bar() shared;
     void baz();
}

If we have an object of type A, all three methods are callable. If we have an object of type shared(A), baz() is not callable. There is a remaining problem with foo() and bar(): the first uses lock-based synchronization, the second uses a sort of free threading (e.g. lock-free) that the compiler is unable to control. It follows that calls to foo() and bar() from different threads may easily create race conditions.

I think the compiler should enforce that a class either defines synchronized methods, shared methods, but not both. So the class writer must decide upfront whether they use lock-based or lock-free threading with a given class. Does this make sense? Is it too restrictive?

Walter asked - what if we take this one step further and force a class to define _all_ methods either synchronized, shared, or neither? In that case the keyword could be moved to the top:

shared class A { ... all methods shared ... }
synchronized class B { ... all methods synchronized ... }
class C { ... shared/synchronized not allowed ... }

Has experience with Java shown that it's best to design classes for concurrency in separation from single-threaded classes? Effective Java doesn't mention that. But then there are all these methods synchronizedCollection, synchronizedList etc. that wrap the corresponding collections (which probably don't have synchronized methods). I'm reading this up, but if there's someone on this list who could save us all some time, please chime in.


Thanks,

Andrei

On Jan 4, 2010, at 9:46 AM, Andrei Alexandrescu <andrei at erdani.com> wrote:

> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
>
> class A {
>    void foo() synchronized;
>    void bar() shared;
>    void baz();
> }
>
> If we have an object of type A, all three methods are callable.

In dmd 2.037, that was not true. Bugzilla 3642 (on diagnostic message) shows sample code where calling A.bar fails on objects of type A.

On Jan 4, 2010, at 6:46 AM, Andrei Alexandrescu wrote:

> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
> 
> class A {
>    void foo() synchronized;
>    void bar() shared;
>    void baz();
> }
> 
> If we have an object of type A, all three methods are callable. If we have an object of type shared(A), baz() is not callable. There is a remaining problem with foo() and bar(): the first uses lock-based synchronization, the second uses a sort of free threading (e.g. lock-free) that the compiler is unable to control. It follows that calls to foo() and bar() from different threads may easily create race conditions.

I'll admit that I'm leery of having shared methods in general.  Operations occurring in order can still easily produce unexpected results when multiple threads are interleaving execution.  Consider increment, for example: if "x++" is executed as "x = x + 1" (ie. a load, add, and a store).  I know that lock-free variables are somewhat of a separate topic, but I wanted to mention this now anyway.

> I think the compiler should enforce that a class either defines synchronized methods, shared methods, but not both. So the class writer must decide upfront whether they use lock-based or lock-free threading with a given class. Does this make sense? Is it too restrictive?

See above.  This would certainly be the easiest for the compiler to verify though, since it wouldn't have to reason about the interaction between lock-free operations and synchronized operations.  But perhaps this is time for a rather large set of questions: can someone define a shared non-class variable?  If so, how would such a variable work within shared and synchronized methods in these classes?  Would shared methods only allow operations on shared variables?  Or perhaps make all operations on data inside them shared regardless of how they're labeled?

> Walter asked - what if we take this one step further and force a class to define _all_ methods either synchronized, shared, or neither? In that case the keyword could be moved to the top:
> 
> shared class A { ... all methods shared ... }
> synchronized class B { ... all methods synchronized ... }
> class C { ... shared/synchronized not allowed ... }
> 
> Has experience with Java shown that it's best to design classes for concurrency in separation from single-threaded classes?

Tricky question.  In general I'd say yes, but that it stinks to have two classes for the same thing that only differ by synchronization.  Consider a container class for example.  Standard operations (insert, remove, etc) can have a "synchronized" label slapped on them and work perfectly, but iterators are a different story entirely.

> Effective Java doesn't mention that. But then there are all these methods synchronizedCollection, synchronizedList etc. that wrap the corresponding collections (which probably don't have synchronized methods). I'm reading this up, but if there's someone on this list who could save us all some time, please chime in.

With D's metaprogramming capabilities, this is a reasonable option in some cases.  Though see my comment about iterators above (foreach is obviously fine though).

Sean Kelly wrote:
> I'll admit that I'm leery of having shared methods in general. Operations occurring in order can still easily produce unexpected results when multiple threads are interleaving execution.  Consider increment, for example: if "x++" is executed as "x = x + 1" (ie. a load, add, and a store).  I know that lock-free variables are somewhat of a separate topic, but I wanted to mention this now anyway.

Shared methods are necessary for enabling lock-free structures. For example a lock-free singly-linked list (a very useful structure) would have all of its methods shared.

Read-modify-write operations a la x++ do not work for shared objects. I was surprised to find out just now that dmd does not enforce that so I just added http://d.puremagic.com/issues/show_bug.cgi?id=3672.

The only things that work on shared objects are:

* calls to synchronized or shared methods, if any;

* reading if the object is word-size or less;

* writing if the object is word-size or less.

>> I think the compiler should enforce that a class either defines synchronized methods, shared methods, but not both. So the class writer must decide upfront whether they use lock-based or lock-free threading with a given class. Does this make sense? Is it too restrictive?
> 
> See above.  This would certainly be the easiest for the compiler to verify though, since it wouldn't have to reason about the interaction between lock-free operations and synchronized operations.  But perhaps this is time for a rather large set of questions: can someone define a shared non-class variable?

Absolutely. A global shared int or a global shared pointer are typical examples.

> If so, how would such a variable
> work within shared and synchronized methods in these classes?

It would obey the regular shared rules. In case you're thinking about a field, shared or synchronized methods don't change the type of an object, subject to the "tail-shared" exemption that I'll discuss at a later point.

> Would
> shared methods only allow operations on shared variables?  Or perhaps
> make all operations on data inside them shared regardless of how
> they're labeled?

If a method is shared, it must assume "this" is shared. The fact that "this" was not shared upon invoking the method is an information that's lost.

By the way - you should be able to call shared methods against a non-shared object.

>> Walter asked - what if we take this one step further and force a class to define _all_ methods either synchronized, shared, or neither? In that case the keyword could be moved to the top:
>> 
>> shared class A { ... all methods shared ... } synchronized class B { ... all methods synchronized ... } class C { ... shared/synchronized not allowed ... }
>> 
>> Has experience with Java shown that it's best to design classes for concurrency in separation from single-threaded classes?
> 
> Tricky question.  In general I'd say yes, but that it stinks to have two classes for the same thing that only differ by synchronization.

In the meantime, according to what I've read, that's exactly what Java containers do. Java containers stink already, are you adding some intensity to the stench?

> Consider a container class for example.  Standard operations (insert, remove, etc) can have a "synchronized" label slapped on them and work perfectly, but iterators are a different story entirely.

This supports Walter's idea that at best a class is designed from the get-go to be synchronized or not. Is that correct?

>> Effective Java doesn't mention that. But then there are all these methods synchronizedCollection, synchronizedList etc. that wrap the corresponding collections (which probably don't have synchronized methods). I'm reading this up, but if there's someone on this list who could save us all some time, please chime in.
> 
> With D's metaprogramming capabilities, this is a reasonable option in some cases.  Though see my comment about iterators above (foreach is obviously fine though).

You mean foreach defined as synchronized opApply?


Andrei

Le 2010-01-04 ? 11:21, Jason House a ?crit :

> On Jan 4, 2010, at 9:46 AM, Andrei Alexandrescu <andrei at erdani.com> wrote:
> 
>> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
>> 
>> class A {
>>   void foo() synchronized;
>>   void bar() shared;
>>   void baz();
>> }
>> 
>> If we have an object of type A, all three methods are callable.
> 
> In dmd 2.037, that was not true. Bugzilla 3642 (on diagnostic message) shows sample code where calling A.bar fails on objects of type A.

And also, if the object is not shared, calling the shared method bar could leak a reference to the thread-local object in a variable shared with other threads. So I think the compiler is correct in rejecting a call to a shared method on a non-shared object. That is, unless it can prove the reference doesn't escape the function's scope.

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

Michel Fortin wrote:
> Le 2010-01-04 ? 11:21, Jason House a ?crit :
> 
>> On Jan 4, 2010, at 9:46 AM, Andrei Alexandrescu <andrei at erdani.com> wrote:
>> 
>>> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
>>> 
>>> class A { void foo() synchronized; void bar() shared; void baz();
>>>  }
>>> 
>>> If we have an object of type A, all three methods are callable.
>> In dmd 2.037, that was not true. Bugzilla 3642 (on diagnostic message) shows sample code where calling A.bar fails on objects of type A.
> 
> And also, if the object is not shared, calling the shared method bar could leak a reference to the thread-local object in a variable shared with other threads. So I think the compiler is correct in rejecting a call to a shared method on a non-shared object. That is, unless it can prove the reference doesn't escape the function's scope.

You're right, sorry. We've been back and forth on this a couple of times. The knee-jerk reaction is that shared is strictly more restrictive than non-shared, so it's fine to convert from non-shared to shared. But in reality shared and non-shared are in no subtyping relationship; a lot of parallels could be drawn with immutable: immutable is like shared, const would be like mayormaynotbeshared.

At some point we thought we'd need to add something to the effect of mayormaynotbeshared, which would be a supertype of both mutable and shared, just like const is a supertype of mutable and shared. We hope to get away without it.


Andrei

On Jan 4, 2010, at 9:00 AM, Andrei Alexandrescu wrote:

> Sean Kelly wrote:
>> I'll admit that I'm leery of having shared methods in general. Operations occurring in order can still easily produce unexpected results when multiple threads are interleaving execution.  Consider increment, for example: if "x++" is executed as "x = x + 1" (ie. a load, add, and a store).  I know that lock-free variables are somewhat of a separate topic, but I wanted to mention this now anyway.
> 
> Shared methods are necessary for enabling lock-free structures. For example a lock-free singly-linked list (a very useful structure) would have all of its methods shared.

My mistake.  I forgot that the shared label on methods is for visibility, since unlabeled methods won't be accessible from a shared reference.

> Read-modify-write operations a la x++ do not work for shared objects. I was surprised to find out just now that dmd does not enforce that so I just added http://d.puremagic.com/issues/show_bug.cgi?id=3672.
> 
> The only things that work on shared objects are:
> 
> * calls to synchronized or shared methods, if any;
> 
> * reading if the object is word-size or less;
> 
> * writing if the object is word-size or less.

Cool!  It's perhaps a minor issue right now, but it would be nice if RMW operations could be performed via library functions.  Hopefully all that's required is to accept a "ref shared T" and then write ASM for the machinery from there?  ie. Is there any need for compiler changes to support this?

>>> I think the compiler should enforce that a class either defines synchronized methods, shared methods, but not both. So the class writer must decide upfront whether they use lock-based or lock-free threading with a given class. Does this make sense? Is it too restrictive?
>> See above.  This would certainly be the easiest for the compiler to verify though, since it wouldn't have to reason about the interaction between lock-free operations and synchronized operations.  But perhaps this is time for a rather large set of questions: can someone define a shared non-class variable?
> 
> Absolutely. A global shared int or a global shared pointer are typical examples.
> 
>> If so, how would such a variable
>> work within shared and synchronized methods in these classes?
> 
> It would obey the regular shared rules. In case you're thinking about a field, shared or synchronized methods don't change the type of an object, subject to the "tail-shared" exemption that I'll discuss at a later point.

So if I have:

    class A
    {
        void fn() shared { x = 5; }
        int x;
    }

Is this legal?  If the type of the object doesn't change then I'd guess that I won't be allowed to access non-shared fields inside a shared function?

>> Would
>> shared methods only allow operations on shared variables?  Or perhaps
>> make all operations on data inside them shared regardless of how
>> they're labeled?
> 
> If a method is shared, it must assume "this" is shared. The fact that "this" was not shared upon invoking the method is an information that's lost.
> 
> By the way - you should be able to call shared methods against a non-shared object.
> 
>>> Walter asked - what if we take this one step further and force a
>>> class to define _all_ methods either synchronized, shared, or
>>> neither? In that case the keyword could be moved to the top:
>>> shared class A { ... all methods shared ... } synchronized class B
>>> { ... all methods synchronized ... } class C { ...
>>> shared/synchronized not allowed ... }
>>> Has experience with Java shown that it's best to design classes for
>>> concurrency in separation from single-threaded classes?
>> Tricky question.  In general I'd say yes, but that it stinks to have two classes for the same thing that only differ by synchronization.
> 
> In the meantime, according to what I've read, that's exactly what Java containers do. Java containers stink already, are you adding some intensity to the stench?

I really don't know Java containers very well so I can't accurately quantify the stench, but it seems like a horrible duplication of code to do this, particularly in a language that doesn't have the facilities to wrap an arbitrary class automatically.

>> Consider a container class for example.  Standard operations (insert, remove, etc) can have a "synchronized" label slapped on them and work perfectly, but iterators are a different story entirely.
> 
> This supports Walter's idea that at best a class is designed from the get-go to be synchronized or not. Is that correct?

Yes I think so.

>>> Effective Java doesn't mention that. But then there are all these methods synchronizedCollection, synchronizedList etc. that wrap the corresponding collections (which probably don't have synchronized methods). I'm reading this up, but if there's someone on this list who could save us all some time, please chime in.
>> With D's metaprogramming capabilities, this is a reasonable option in some cases.  Though see my comment about iterators above (foreach is obviously fine though).
> 
> You mean foreach defined as synchronized opApply?

Yes exactly.

On Jan 4, 2010, at 12:00 PM, Andrei Alexandrescu <andrei at erdani.com> wrote:

>
> ... subject to the "tail-shared" exemption that I'll discuss at a later point.

I wish you'd stop giving teasers like that. It feels like we can't have a discussion because a) you haven't tried to share your perspective b) you're too busy to have the conversation anyway

I'm probably way off with my impression...


> By the way - you should be able to call shared methods against a non- shared object.

Assuming reduced efficiency is acceptable, there's another issue: verification of type safety must be dine differently for shared and non-shared objects. There is no equivalent of const or inout...
>

On Jan 4, 2010, at 11:31 AM, Sean Kelly <sean at invisibleduck.org> wrote:

> On Jan 4, 2010, at 6:46 AM, Andrei Alexandrescu wrote:
>
>> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
>>
>> class A {
>>   void foo() synchronized;
>>   void bar() shared;
>>   void baz();
>> }
>>
>> If we have an object of type A, all three methods are callable. If we have an object of type shared(A), baz() is not callable. There is a remaining problem with foo() and bar(): the first uses lock- based synchronization, the second uses a sort of free threading (e.g. lock-free) that the compiler is unable to control. It follows that calls to foo() and bar() from different threads may easily create race conditions.
>
> I'll admit that I'm leery of having shared methods in general. Operations occurring in order can still easily produce unexpected results when multiple threads are interleaving execution.  Consider increment, for example: if "x++" is executed as "x = x + 1" (ie. a load, add, and a store).  I know that lock-free variables are somewhat of a separate topic, but I wanted to mention this now anyway.

Sadly, this is a side effect of a simplistic handling of shared. Shared is more like "here be dragons, here's an ice cube in case one breaths fire on you". Nearly all protection / correctness verification are missing and left for D3 or beyond. Message passing lets shared aware code remain in the trusted code base...

What is the plan to stop "shared" from spreading through all of an application's code?

My own preference is to adopt an approach that severely limits the number of shared objects, perhaps by using a keyword like "shareable that means: "this object is shared, but it is completely ok to call its synchronized methods from non-shared methods/objects".

This approach facilitates message-passing, and can very simply handle plenty of multi-threaded use-cases. A shareable object whose externally accessible methods are all synchronized and DO NOT accept or return any references to mutable data should be callable from any thread with complete safety, WITHOUT polluting the calling code with "shared".

Within such a shareable object, we can use low-level stuff like mutexes, semaphores and conditions to build the desired behaviour, wrapping it up and presenting a clean interface.

Re synchronized containers - I don't like the idea at all. That is going down the path of having many shared objects, which is notoriously difficult to get right, especially for non-experts. IMO, shared objects should be small in number, and serve as boundaries between threads, which otherwise play in their own separate sand-pits.

Dare I say it - go's emphasis on channels is very appealing to me, and should be something that is easy to do in D - even though it is too limiting to have it as the only tool in the box.

Thanks,
Graham.

Andrei Alexandrescu wrote:
> This may be easiest to answer for people with extensive experience with Java's threading model. Consider the following D code:
>
> class A {
>     void foo() synchronized;
>     void bar() shared;
>     void baz();
> }
>
> If we have an object of type A, all three methods are callable. If we have an object of type shared(A), baz() is not callable. There is a remaining problem with foo() and bar(): the first uses lock-based synchronization, the second uses a sort of free threading (e.g. lock-free) that the compiler is unable to control. It follows that calls to foo() and bar() from different threads may easily create race conditions.
>
> I think the compiler should enforce that a class either defines synchronized methods, shared methods, but not both. So the class writer must decide upfront whether they use lock-based or lock-free threading with a given class. Does this make sense? Is it too restrictive?
>
> Walter asked - what if we take this one step further and force a class to define _all_ methods either synchronized, shared, or neither? In that case the keyword could be moved to the top:
>
> shared class A { ... all methods shared ... }
> synchronized class B { ... all methods synchronized ... }
> class C { ... shared/synchronized not allowed ... }
>
> Has experience with Java shown that it's best to design classes for concurrency in separation from single-threaded classes? Effective Java doesn't mention that. But then there are all these methods synchronizedCollection, synchronizedList etc. that wrap the corresponding collections (which probably don't have synchronized methods). I'm reading this up, but if there's someone on this list who could save us all some time, please chime in.
>
>
> Thanks,
>
> Andrei
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency