On Jan 8, 2010, at 12:36 AM, Walter Bright wrote:
> 
> Sean Kelly wrote:
>> 
>> I feel like I'm not explaining myself very well, but that's the best I can do at the moment.  As a related issue, I have a feeling that the following is a bad idea, but I haven't come up with a good explanation for why yet, maybe simply the principle of least surprise?:
>> 
>> class C
>> {
>>    shared int x;
>> }
>> 
>> auto c = new C;
>> sendRefToAnotherThread( c ); // fails, c is local
>> sendToAnotherThread( &c.x ); // succeeds, c.x is shared
>> 
>> 
> 
> The transitivity of shared doesn't work backwards, only forwards. In other words, you can have a local pointer to shared, but no shared pointers to locals.
> 
> In yet other words, sharing is transitive, locality is not.

So where would the compiler error on the example above?

Sean Kelly wrote:
> On Jan 8, 2010, at 12:36 AM, Walter Bright wrote:
> 
>> Sean Kelly wrote:
>> 
>>> I feel like I'm not explaining myself very well, but that's the best I can do at the moment.  As a related issue, I have a feeling that the following is a bad idea, but I haven't come up with a good explanation for why yet, maybe simply the principle of least surprise?:
>>>
>>> class C
>>> {
>>>    shared int x;
>>> }
>>>
>>> auto c = new C;
>>> sendRefToAnotherThread( c ); // fails, c is local
>>> sendToAnotherThread( &c.x ); // succeeds, c.x is shared
>>>
>>> 
>>> 
>> The transitivity of shared doesn't work backwards, only forwards. In other words, you can have a local pointer to shared, but no shared pointers to locals.
>>
>> In yet other words, sharing is transitive, locality is not.
>> 
>
> So where would the compiler error on the example above?
> 

Assuming the prototypes are:

    void sendRefToAnotherThread(shared Object o);   // fail, c is not shared
    void sendToAnotherThread(shared void* p) ; // success, &c.x points
to shared

----- Original Message ----

> From: Sean Kelly <sean at invisibleduck.org>
> To: Discuss the concurrency model(s) for D <dmd-concurrency at puremagic.com>
> Sent: Fri, January 8, 2010 3:18:12 AM
> Subject: Re: [dmd-concurrency] Smoke test
> 
> On Jan 7, 2010, at 5:28 PM, Walter Bright wrote:
> > 
> > Having a per-thread gc is an optimization, not a fundamental feature of the
> concurrency model. For one thing, it precludes casting data to immutable. For another, it may result in excessive memory consumption as one thread may have a lot of unused data in its pool that is not available for allocation by another thread.
> 
> I agree completely that having a per-thread GC is simply an optimization.  I just brought it up because it's the simplest way I've come up with to think about what "shared" means.  Put another way, I think of shared as controlling the access control pool the data lives in, and the lifetime of that data.  If I see "T v1" then I should be able to infer that v1 is only visible to the current thread and will go away when the thread terminates.  Similarly, if I see "shared T v2" I should be able to infer that v2 is globally visible and may remain until process termination.
> 
> I feel like I'm not explaining myself very well, but that's the best I can do at the moment.  As a related issue, I have a feeling that the following is a bad idea, but I haven't come up with a good explanation for why yet, maybe simply the principle of least surprise?:
> 
> class C
> {
>     shared int x;
> }
> 
> auto c = new C;
> sendRefToAnotherThread( c ); // fails, c is local
> sendToAnotherThread( &c.x ); // succeeds, c.x is shared

For one, it prevents thread-local heaps from being truly thread-local.  For example, in order for this class to be allocated, it must be allocated in the global heap for part of it to be shared.  But c would seem that it should be allocated locally.

A better example is this:

class B
{
}

class C
{
    shared int x;
    B b;
}

C c;
void foo()
{
   c = new C;
   sendToAnotherThread(&c.x)
   c.b = new B;
}

So, now you go to do a thread-local garbage collection.  How does it make the round-trip through the global heap to prevent collection of c.b, since c is allocated in the shared heap?  You'd have to do a mark-sweep on the global heap also.  This means a collection can't truly be thread local, and will be synchronized with all other thread collection cycles.

On the other hand, I can see uses for this, such as if x is some kind of flag or something that you want other threads to be able to read or set.  However, I think it should be fine to require that any memory block be all shared or all local, but no mixed.  In this case, you could implement the same thing with an extra allocation:

class C
{
   private shared(int) *_x;
   B b;
   this() {_x = new shared(int);} // _x is placed on global heap
   @property ref shared(int) x() {return *_x;}
}

(Forgive me for not knowing the required semantics of shared, assume the uses are properly annotated here.)

The bottom line is, we could have a rule that any members of a class or struct could have *references* to shared memory, but could not *contain* shared memory.  I think this is a reasonable rule.  It definitely would sit better with me and be easier to implement/explain.

The only caveat is, we would *need* to change the semantics of shared so that you can have a non-shared reference to a shared class instance easily.  I don't know if a wrapper struct would cut it because the compiler would enforce the same rules on the wrapper struct (maybe you mark it as @system?).  I have a feeling that you almost always want a thread-local reference to a shared class anyway (the exception being a global shared variable).

-Steve

On Fri, 08 Jan 2010 02:03:11 -0500, Walter Bright <walter at digitalmars.com> wrote:
>
>
> Robert Jacques wrote:
>> On Thu, 07 Jan 2010 20:28:23 -0500, Walter Bright <walter at digitalmars.com> wrote:
>>> Having a per-thread gc is an optimization, not a fundamental feature
>>> of the concurrency model. For one thing, it precludes casting data to
>>> immutable. For another, it may result in excessive memory consumption
>>> as one thread may have a lot of unused data in its pool that is not
>>> available for allocation by another thread.
>>> _______________________________________________
>>> dmd-concurrency mailing list
>>> dmd-concurrency at puremagic.com
>>> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>>
>> I would disagree; it's completely possible to allow safe casting to immutable/shared with thread-local GCs. It just requires language support. For example, adding a GC function which is called whenever a shared cast occurs. In the current GC, the function does nothing and everything proceeds as normal. With thread local GC, however, this function would publish the casted object to a list. The local GC could then pin all objects on the list and the shared GC could mark/sweep the list entries instead of the objects themselves.
>
> Sounds like the thread local pool will get peppered with shared islands inside it.

Maybe. Maybe not. It really depends on how much casting one has to do between heap types. And whether or not that 'peppering' out-weighs the other benefits of local GCs. But local GCs worked in Java, where the regions were built dynamically and in Objective-C, where they were specified manually, so I think they'd work for many of D's (multi-core) applications. Yes it's an just an optimization, but it's an important 'use case' of the concurrency system in D, which makes it a good 'smoke test'. And if it's treated as a major 'use case' then we can identify ways around (and the costs) the issues (like peppering) that arise. For example:

Today, I think the major use of casting to immutable is with performance string building. (Non-performance code would use idup) Such code would probably use an ArrayBuilder. Based on that assumption, an iArrayBuilder could be defined to allocate from the shared/immutable memory region but allow fast (i.e. non-atomic) mutation. It would behave like unique and perform a mfence when converted to immutable/shared.

Le 2010-01-08 ? 1:58, Walter Bright a ?crit :

> Michel Fortin wrote:
>> If you want the language to be limited to models where the memory can always be shared between all threads, then that that's fine. It's your prerogative. I'm not so sure it's wise to limit shared semantics to this scenario just to avoid having the shared-immutable combo, but if you're sure that's what you want then I'll stick to it.
> 
> There's another aspect here. Consider all the problems we have getting across the idea of an immutable type. What hope is there for shared? I see mass confusion everywhere. Frankly, I see little hope of any but a handful of programmers ever being able to grok shared and use it correctly for concurrent programs. The notion that one can just slap 'shared' on a data type and have it work correctly across threads without further thought is a pipe dream.
> 
> So what to do?
> 
> I want to pin the mainstream concurrency on message passing. The message passing user never sees shared, never has to deal with locks, never has to deal with memory barriers. It just works. Message passing should be a robust, scalable solution for most users. I believe the Erlang experience validates this. Go and Scala also rely entirely on message passing (but they don't have immutable data, so their models are unsafe and I predict many rude surprises).

I agree that message passing should be the preferred method for concurrency. It's the easiest to understand, and it scales well, even on an internet scale. I also agree that it's much better if shared isn't needed anywhere when using the message passing API. But does this last constrain breaks the idea of thread-local pools? Not at all.

First of all, there will be a mechanism in the message passing system to copy the data when needed, because a pool of memory shared between the sender and the receiver will not always exist (for instance when you're communicating with another computer).

Second, I trust the messaging API will do everything it can to not copy around the memory when not necessary. If the runtime supports changing non-shared to shared -- because there is one global memory pool, or because it can somehow transfer the ownership -- then it won't copy the data: it'll pass the pointer instead. If the data cannot be shared, it'll be because the runtime doesn't offer the feature, or because of other limitations, and the copying mechanism will take on.

So the compiler doesn't need to conflate shared-immutable with immutable to keep the message passing API simple. Whether to copy or to pass the pointer can be decided by the message passing API itself depending on whether the runtime abilities. When you know the runtime doesn't support sharing data previously allocated as not-shared, then it may be more efficient to create your message as a shared object from the start to avoid copying, but 1) that doesn't change anything for the scenario where everything comes from the same memory pool, and 2) if your messages are short you won't care whether they're copied or shared anyway.

So the messaging API can stay simple even if the language itself does not combine shared-immutable and immutable into one. Using a thread-local GC is just a matter of choosing a different tradeoff, and supporting it doesn't affect performance when its not needed.


> So why bother with shared at all?
> 

[[here goes a lot of things I agree with]]

> As for a shared gc vs thread local gc, I just see an awful lot of strange irreproducible bugs when someone passes data from one to the other. I doubt it's worth it, unless it can be done with compiler guarantees, which seem doubtful.

I agree, and I think it can be done with compiler guaranties, as long as shared-immutable is treated differently from immutable by the compiler (and you don't do stupid casts).

That doesn't mean it'll become hard to use immutable. Here are the rules I propose:

* "shared immutable" implicitly converts to "immutable".
* "immutable" can be made "shared immutable" explicitly with a function template in druntime, if supported by the runtime. Otherwise it needs to be copied using APIs of some sort.
* "immutable" global variables can be promoted to "shared immutable" at compile-time because it doesn't break anything and is more efficient.

With that I'm pretty sure the only code that will have to use "shared immutable" is code that needs to deal with "shared" anyway (like inside the message passing system). Any code using just "immutable" will accept "shared immutable" whenever it likes because of the implicit cast.


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

Your proposal requires yet a new type constructor, "shared immutable", with a new set of rules and overloads. I don't think it's worth it. Currently, "shared immutable" == "immutable", i.e. the two are indistinguishable.

Steve Schveighoffer wrote:
> The only caveat is, we would *need* to change the semantics of shared so that you can have a non-shared reference to a shared class instance easily.

That's the so-called "tail-shared" problem. We tried (hard) to make "tail-const" work, where the reference is mutable but the contents were const. It sounds simple, but just does not work in a language with implicit reference semantics.

----- Original Message ----

> From: Walter Bright <walter at digitalmars.com>
> 
> Steve Schveighoffer wrote:
> > The only caveat is, we would *need* to change the semantics of shared so that
> you can have a non-shared reference to a shared class instance easily.
> 
> That's the so-called "tail-shared" problem. We tried (hard) to make "tail-const" work, where the reference is mutable but the contents were const. It sounds simple, but just does not work in a language with implicit reference semantics.

Yes, but this isn't const, it is shared.  You sometimes want const members or const stack variables.  I think you never want the equivalent shared items.

Let's think about how often you actually need to use shared as a storage class:

1) as a global/static variable
2) stack variable? never
3) member variabe? debatable -- you can always create a shared reference to the entire aggregate which seems more logical to me anyway.

What if we make shared *default* to tail-shared for reference and pointer types except for global variables (which will be fully shared), and make it illegal to declare a shared value type on the stack or as a member.

Basically, shared for a global variable means it is a globally shared value, but shared anywhere else means it references either a globally shared value or shared heap data.  Any other usage is illegal.

This makes it impossible to share stack data -- good.
This makes it impossible to have shared and local data in the same heap memory block -- good for thread-local heaps.
This makes it easy to declare a local reference to a shared class -- excellent.
This allows having a thread-local heap -- good.
This makes it neigh impossible to declare a thread-local global or static reference to a shared class -- bad for completeness, but is this anticipated to be a common usage?
This means if you want to share delegates, you have to mark the function as a shared closure, and it will always be heap allocated -- an acceptable tradeoff IMO.

examples:

shared int x; // ok, visible to all threads
shared C c; // ok, visible to all threads, the reference itself is shared.

struct S
{
}

class C
{
   shared int x; // illegal
   shared int *y; // legal, the pointer itself isn't shared -- equivalent to shared(int)* x
   shared int[] a; // legal, the array struct itself isn't shared -- equivalent to shared(int)[] a
   shared C c; // legal, the reference itself isn't shared
   shared S s; // illegal, same as shared int, it's a value type
}

void foo()
{
   shared int x; // illegal
   shared S s; // illegal
   shared C c; // legal, the reference itself isn't shared.
}

void fooShared(shared int* x, immutable int *y) // can only have shareable reference parameters
{
    int fn() shared // flags that the entire fooShared function will always be heap-allocated, even if passed to a scope handler.
    {
        return *x;
    }
}

What do you think about this?

-Steve

Steve Schveighoffer wrote:
> ----- Original Message ----
>
> 
>> From: Walter Bright <walter at digitalmars.com>
>>
>> Steve Schveighoffer wrote:
>> 
>>> The only caveat is, we would *need* to change the semantics of shared so that
>>> 
>> you can have a non-shared reference to a shared class instance easily.
>>
>> That's the so-called "tail-shared" problem. We tried (hard) to make "tail-const"
>> work, where the reference is mutable but the contents were const. It sounds
>> simple, but just does not work in a language with implicit reference semantics.
>> 
>
> Yes, but this isn't const, it is shared.

To the type construction system, they are handled the same. Tail-shared will have the same insurmountable problems that tail-const had.

>
> What do you think about this?
>
>
> 

I tried desperately to make tail-const work. It wasn't going to, and neither is tail-shared for the same reasons.

----- Original Message ----

> From: Walter Bright <walter at digitalmars.com>
> 
> 
> Steve Schveighoffer wrote:
> > ----- Original Message ----
> > 
> > 
> >> From: Walter Bright
> >> 
> >> Steve Schveighoffer wrote:
> >> 
> >>> The only caveat is, we would *need* to change the semantics of shared so
> that
> >> you can have a non-shared reference to a shared class instance easily.
> >> 
> >> That's the so-called "tail-shared" problem. We tried (hard) to make
> "tail-const" work, where the reference is mutable but the contents were const. It sounds simple, but just does not work in a language with implicit reference semantics.
> >> 
> > 
> > Yes, but this isn't const, it is shared.
> 
> To the type construction system, they are handled the same. Tail-shared will have the same insurmountable problems that tail-const had.

They don't have to be handled the same.  Const is completely different from shared with different problems and different solutions.  If shared was the same as const, we wouldn't be discussing it right now, it would be done.

> 
> > 
> > What do you think about this?
> > 
> > 
> > 
> 
> I tried desperately to make tail-const work. It wasn't going to, and neither is tail-shared for the same reasons.

It's too bad that tail-const wouldn't work.  I don't think tail-shared presents the same problems.  Please don't dismiss all the points I wrote just because of past failures.  They are new ideas that don't apply to const at all.

-Steve