I can't believe it's not butter! Draft 8 is the first that completely covers the topics I'd planned. For a good time download:

http://erdani.com/d/fragment.preview.pdf

It took me an all-nighter but I think it was well worth it. I most surely got a few details of the lock-free singly-linked list wrong, but then what are the good friends on this list for? :o)

Let me know how it all sits.

I need to make one full pass through the book and operate the changes I'd already scribbled on a draft manuscript; then I'll go through the 105 emails containing feedback; then (or probably concurrently with that) I'll operate changes to this chapter prompted by you guys; and if I survive all that, the manuscript will be ready for publication.


Thanks,

Andrei

Le 2010-02-10 ? 10:05, Andrei Alexandrescu a ?crit :

> I can't believe it's not butter! Draft 8 is the first that completely covers the topics I'd planned. For a good time download:

:-)

I know we already talked about this subject from the last draft, but why do we need atomicOp!"+=" at all? Why not bind += to an atomic operation directly like we do for read and writes? (I'm not asking for the answer to be in the book, I'm just curious about this decision.)


About synchronized classes:

> ? Array fields declared declared with type T[] receive type shared(T)[], i.e. the head (the slice limits) is not shared and the tail (the contents of the array) remains shared;
> ? Pointer fields declared with type T* receive type shared(T)*, i.e. the head (the pointer itself ) is not shared and the tail (the pointed-to data) remains shared;

As I and other said before, this is totally unhelpful. When I want the referenced to be protected by the lock, assuming it shared will allow it to escape which is *not* safe.

I think it'd be safer to make the referenced value of those fields completely inaccessible. That may sound rash, but it's better than to assume you can do something that should't be allowed. As usual, you can use a cast to bypass the safeties. And if you really want a shared(T)[], you can still write it as shared(T)[].


> To tap into cas-based lock-free goodness, use the shared attribute with a class or struct definition:
> 
> struct LockFreeStruct {
> 	...
> }
> struct LockFreeClass {
> 	...
> }

I think your example lacks 2 'shared', 1 'class' and -1 'struct'.

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

Michel Fortin wrote:
> Le 2010-02-10 ? 10:05, Andrei Alexandrescu a ?crit :
> 
>> I can't believe it's not butter! Draft 8 is the first that completely covers the topics I'd planned. For a good time download:
>> 
> 
> :-)
> 
> I know we already talked about this subject from the last draft, but why do we need atomicOp!"+=" at all? Why not bind += to an atomic operation directly like we do for read and writes? (I'm not asking for the answer to be in the book, I'm just curious about this decision.)

I have no strong opinion. I think it doesn't harm to see that the operation is atomic, but then it could be all automated. Others, please weigh in.

> About synchronized classes:
> 
>> ? Array fields declared declared with type T[] receive type
>> shared(T)[], i.e. the head (the slice limits) is not shared and the
>> tail (the contents of the array) remains shared; ? Pointer fields
>> declared with type T* receive type shared(T)*, i.e. the head (the
>> pointer itself ) is not shared and the tail (the pointed-to data)
>> remains shared;
> 
> As I and other said before, this is totally unhelpful. When I want the referenced to be protected by the lock, assuming it shared will allow it to escape which is *not* safe.
> 
> I think it'd be safer to make the referenced value of those fields completely inaccessible. That may sound rash, but it's better than to assume you can do something that should't be allowed. As usual, you can use a cast to bypass the safeties. And if you really want a shared(T)[], you can still write it as shared(T)[].

Nonono. What should happen is no escape of *field* addresses because those are exposed to races when accessed naively. Synchronized methods do NOT assumes that the *indirections* starting from fields are locked/protected/non-shared.

If I have a pointer to int as a field:

- inside the sychronized method, the pointer itself is protected by the lock and can be considered not shared. Escaping THE ADDRESS OF that pointer would create races because it breaks the assumption that only the method messes with it

- the int pointed to by that field is STILL considered shared by the method AND by the rest of the world so there's never the risk of an undue race. The method can escape it all it wants.

>> To tap into cas-based lock-free goodness, use the shared attribute with a class or struct definition:
>> 
>> struct LockFreeStruct { ... } struct LockFreeClass { ... }
> 
> I think your example lacks 2 'shared', 1 'class' and -1 'struct'.

Ew! Thanks.


Andrei

Le 2010-02-10 ? 14:08, Andrei Alexandrescu a ?crit :

> Nonono. What should happen is no escape of *field* addresses because those are exposed to races when accessed naively. Synchronized methods do NOT assumes that the *indirections* starting from fields are locked/protected/non-shared.
> 
> If I have a pointer to int as a field:
> 
> - inside the sychronized method, the pointer itself is protected by the lock and can be considered not shared. Escaping THE ADDRESS OF that pointer would create races because it breaks the assumption that only the method messes with it
> 
> - the int pointed to by that field is STILL considered shared by the method AND by the rest of the world so there's never the risk of an undue race. The method can escape it all it wants.

I understand quite well your intent. I just disagree with it.

My point is that it will happen quite often that the compiler's assumption (that synchronization does not apply beyond indirections) isn't adequate: when you need to use an internal array as a buffer, or when you need some other hidden data structure. I understand that in those cases you need to cast your way around, fine. It looks crippled, but let's say that's okay.

What is much less shiny is that in those cases where you need a cast to do the right thing, the compiler will also let you do the wrong thing (let a value escape) without a cast. For instance, in your example of "casting away shared" with a 'List!double' member, nothing prevents a function from escaping a reference to the list as a shared(List!double), but doing so will lead to races.

Instead of having T* members implicitly converted to shared(T)*, the compiler could just prevent any access to non-shared data through an indirection. So you'd still need a cast to do the right thing, but the compiler won't let you do the wrong thing by accident.

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

On Wednesday 10 February 2010 16:05 Andrei Alexandrescu wrote:
> I can't believe it's not butter! Draft 8 is the first that completely covers the topics I'd planned. For a good time download:
> 
> http://erdani.com/d/fragment.preview.pdf

Interesting read!

* The first message passing example uses tid.send(thisTid, i) to send a Tid
and an int. Then you describe the pattern matching in receive and explain that
receive( (string) {} ); matches send(tid, "hello");. I guess that should be
tid.send("hello") or the former ought to have been send(tid, thisTid, i)? If
there are two versions of send - or if the uniform call syntax made it into D2
- I think switching between them at this point hurts clarity.

* The synchronized version of BankAccount is missing a @property on balance. And one of the not-really-D versions has it, the other doesn't.

* The collection of apostrophes in ?we?re done, let?s ?nish and go home.? looks odd.

* The parts of the text I read looked great. I'd drop the "legally-acquired" and move the "Best Form-Follows-Function" explanation to the section on immutable if it precedes this one.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100210/b174227a/attachment.pgp>

Michel Fortin wrote:
> Le 2010-02-10 ? 14:08, Andrei Alexandrescu a ?crit :
> 
>> Nonono. What should happen is no escape of *field* addresses because those are exposed to races when accessed naively. Synchronized methods do NOT assumes that the *indirections* starting from fields are locked/protected/non-shared.
>> 
>> If I have a pointer to int as a field:
>> 
>> - inside the sychronized method, the pointer itself is protected by the lock and can be considered not shared. Escaping THE ADDRESS OF that pointer would create races because it breaks the assumption that only the method messes with it
>> 
>> - the int pointed to by that field is STILL considered shared by the method AND by the rest of the world so there's never the risk of an undue race. The method can escape it all it wants.
> 
> I understand quite well your intent. I just disagree with it.
> 
> My point is that it will happen quite often that the compiler's assumption (that synchronization does not apply beyond indirections) isn't adequate: when you need to use an internal array as a buffer, or when you need some other hidden data structure. I understand that in those cases you need to cast your way around, fine. It looks crippled, but let's say that's okay.
> 
> What is much less shiny is that in those cases where you need a cast to do the right thing, the compiler will also let you do the wrong thing (let a value escape) without a cast. For instance, in your example of "casting away shared" with a 'List!double' member, nothing prevents a function from escaping a reference to the list as a shared(List!double), but doing so will lead to races.

There are no races because the List!double type is either thread-unaware in which case there is next to nothing you can do with, or is thread-aware in which case it knows how to fend for itself.

> Instead of having T* members implicitly converted to shared(T)*, the compiler could just prevent any access to non-shared data through an indirection. So you'd still need a cast to do the right thing, but the compiler won't let you do the wrong thing by accident.

With the no escape rule you cripple people who rent; without it I cripple people who own. Most importantly, I allow escaping of members of class type which I think is an important case.


Andrei

Thanks, noted.

Andrei

Christian Kamm wrote:
> On Wednesday 10 February 2010 16:05 Andrei Alexandrescu wrote:
>> I can't believe it's not butter! Draft 8 is the first that completely covers the topics I'd planned. For a good time download:
>>
>> http://erdani.com/d/fragment.preview.pdf
> 
> Interesting read!
> 
> * The first message passing example uses tid.send(thisTid, i) to send a Tid
> and an int. Then you describe the pattern matching in receive and explain that
> receive( (string) {} ); matches send(tid, "hello");. I guess that should be
> tid.send("hello") or the former ought to have been send(tid, thisTid, i)? If
> there are two versions of send - or if the uniform call syntax made it into D2
> - I think switching between them at this point hurts clarity.
> 
> * The synchronized version of BankAccount is missing a @property on balance. And one of the not-really-D versions has it, the other doesn't.
> 
> * The collection of apostrophes in ?we?re done, let?s ?nish and go home.? looks odd.
> 
> * The parts of the text I read looked great. I'd drop the "legally-acquired" and move the "Best Form-Follows-Function" explanation to the section on immutable if it precedes this one.
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency

Le 2010-02-10 ? 15:29, Andrei Alexandrescu a ?crit :

> Michel Fortin wrote:
>> Le 2010-02-10 ? 14:08, Andrei Alexandrescu a ?crit :
>>> Nonono. What should happen is no escape of *field* addresses
>>> because those are exposed to races when accessed naively.
>>> Synchronized methods do NOT assumes that the *indirections*
>>> starting from fields are locked/protected/non-shared.
>>> If I have a pointer to int as a field:
>>> - inside the sychronized method, the pointer itself is protected by
>>> the lock and can be considered not shared. Escaping THE ADDRESS OF
>>> that pointer would create races because it breaks the assumption
>>> that only the method messes with it
>>> - the int pointed to by that field is STILL considered shared by
>>> the method AND by the rest of the world so there's never the risk
>>> of an undue race. The method can escape it all it wants.
>> I understand quite well your intent. I just disagree with it.
>> My point is that it will happen quite often that the compiler's
>> assumption (that synchronization does not apply beyond indirections)
>> isn't adequate: when you need to use an internal array as a buffer,
>> or when you need some other hidden data structure. I understand that
>> in those cases you need to cast your way around, fine. It looks
>> crippled, but let's say that's okay.
>> What is much less shiny is that in those cases where you need a cast
>> to do the right thing, the compiler will also let you do the wrong
>> thing (let a value escape) without a cast. For instance, in your
>> example of "casting away shared" with a 'List!double' member, nothing
>> prevents a function from escaping a reference to the list as a
>> shared(List!double), but doing so will lead to races.
> 
> There are no races because the List!double type is either thread-unaware in which case there is next to nothing you can do with, or is thread-aware in which case it knows how to fend for itself.

Are you saying you cannot access public members of a thread-unware object? This would lead to a race in this situation. Same with a struct, or any primitive type. As soon as you read or write a variable from outside the lock you have a race.


>> Instead of having T* members implicitly converted to shared(T)*, the compiler could just prevent any access to non-shared data through an indirection. So you'd still need a cast to do the right thing, but the compiler won't let you do the wrong thing by accident.
> 
> With the no escape rule you cripple people who rent; without it I cripple people who own. Most importantly, I allow escaping of members of class type which I think is an important case.

Not at all. All you have to do is enforce the no-escpae rule for T* but not for shared(T)*. The 'shared' qualifier in a synchronized class context has the implicit meaning of 'not-owned'. If you want to give a reference to someone, all you have to do is declare your members explicitly as shared(T)*, and then give a reference to the shared part. Done. Implicitly changing T* to shared(T)* is what is breaking the safeties.


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

Michel Fortin wrote:
> Le 2010-02-10 ? 15:29, Andrei Alexandrescu a ?crit :
> 
>> Michel Fortin wrote:
>>> Le 2010-02-10 ? 14:08, Andrei Alexandrescu a ?crit :
>>>> Nonono. What should happen is no escape of *field* addresses because those are exposed to races when accessed naively. Synchronized methods do NOT assumes that the *indirections* starting from fields are locked/protected/non-shared. If I have a pointer to int as a field: - inside the sychronized method, the pointer itself is protected by the lock and can be considered not shared. Escaping THE ADDRESS OF that pointer would create races because it breaks the assumption that only the method messes with it - the int pointed to by that field is STILL considered shared by the method AND by the rest of the world so there's never the risk of an undue race. The method can escape it all it wants.
>>> I understand quite well your intent. I just disagree with it. My point is that it will happen quite often that the compiler's assumption (that synchronization does not apply beyond indirections) isn't adequate: when you need to use an internal array as a buffer, or when you need some other hidden data structure. I understand that in those cases you need to cast your way around, fine. It looks crippled, but let's say that's okay. What is much less shiny is that in those cases where you need a cast to do the right thing, the compiler will also let you do the wrong thing (let a value escape) without a cast. For instance, in your example of "casting away shared" with a 'List!double' member, nothing prevents a function from escaping a reference to the list as a shared(List!double), but doing so will lead to races.
>> There are no races because the List!double type is either thread-unaware in which case there is next to nothing you can do with, or is thread-aware in which case it knows how to fend for itself.
> 
> Are you saying you cannot access public members of a thread-unware object? This would lead to a race in this situation.

You can, but they're qualified with shared, just the same way the synchronized method sees them. There is no race. I'm sure there is a misunderstanding somewhere.

> Same with a
> struct, or any primitive type. As soon as you read or write a
> variable from outside the lock you have a race.

Clearly there is a misunderstanding somewhere, so I need to improve on the explanations. A struct is stored in situ within the object. Locking the object protects the fields of the struct. The indirections of those fields remain shared. There is no race. Please provide an example that you believe exposes a race.

(By the way I'm talking about low-level races, the kind you get when you share data that's not qualified with "shared".)

>>> Instead of having T* members implicitly converted to shared(T)*, the compiler could just prevent any access to non-shared data through an indirection. So you'd still need a cast to do the right thing, but the compiler won't let you do the wrong thing by accident.
>> With the no escape rule you cripple people who rent; without it I cripple people who own. Most importantly, I allow escaping of members of class type which I think is an important case.
> 
> Not at all. All you have to do is enforce the no-escpae rule for T* but not for shared(T)*. The 'shared' qualifier in a synchronized class context has the implicit meaning of 'not-owned'. If you want to give a reference to someone, all you have to do is declare your members explicitly as shared(T)*, and then give a reference to the shared part. Done. Implicitly changing T* to shared(T)* is what is breaking the safeties.

I strongly believe there is no breakage of safety at all. Again, an example should be of help here.


Andrei

Le 2010-02-10 ? 16:54, Andrei Alexandrescu a ?crit :

>> Are you saying you cannot access public members of a thread-unware object? This would lead to a race in this situation.
> 
> You can, but they're qualified with shared, just the same way the synchronized method sees them. There is no race. I'm sure there is a misunderstanding somewhere.

I agree there is no race as long as you don't put a cast in there. If you go back a few emails, you'll note that I was talking about the context where you want to have something owned beyond an indirection. In this situation the compiler is more than unhelpful since not only you need a cast (but I digest), it also allows you to escape your "owned beyond an indirection" data without a cast.

I'm saying that this will be a common enough case that it should be better. If it wasn't a common enough case you wouldn't have that "cast away shared" chapter. So in that common enough case that require a cast you'll not only need a cast, but you'll also need to be extra cautious about what escapes even in functions that do not have a cast.

So I was simply suggesting that the compiler helps by knowing up to what level of indirection the data is "owned". For instance, by my suggestion, this:

	synchronized class A {
		int[] x;
		shared(int)[] y;
	}

has member x is owned entirely (including the referenced data) by the object while for member y only the head (or tail? I'm always mixing those terms) is owned. This means you can't take the address of x's content (just like you can't take the address of x or y). Well, you can, but you need a cast.


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