So, if I understand correctly, the main thing the shared provides (relative to, say, an implicitely shared global in in gcc) is (relatively) simple memory barriers in the right places as well as compare and swap, which can be used to do lock-free style programming?

One thing that strikes me as potentially tricky with the lock free style -- it seems like it isn't composable at all.  What I mean is that even if you get a really high quality and fast lock-free hash map running, if you need to take something (a struct, say) out of the hash map, do something with it, and then put it back in, you can write shared lock-free logic for the struct, and for the hash map, but you can't easily make the entire operation of take-out, update, put-back lock free in any easy way, right?

On a theoretical level, these are cool structures but it seems like we will still have the problem that Java 1.0 had, which is that it had thread save Vector primitives but there was no way to enforce consistency between them. Consistency only refers to one of the two lists at a time.

Likewise, if you have a struct with one integer you can do CAS.  If you have two integers, you can figure out a 2-word CAS, but then if you have three you are sunk again.  If you come up with a trick for three, you lose with four.

Since D has such great built in containers, doing things like associative arrays as lock-free seems great.  But I'm thinking the majority of the time for ordinary users, this feature would be used either for simple insert, singly linked list, or fall back to a spin lock to surround all your operations (in which case you lose the guarantee that one thread can pause without hanging the app.)

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100106/51edaf5a/attachment.htm>

CAS-based coding is tricky, but that's not our problem - we offer no more and no less than the tools to define CAS-based designs. As a bonus, we disallow values that participate in CAS operations to be handled unwittingly by threads that believe have exclusive access. I think this is a very good setup.

What you say is a general critique addressed to CAS, which is fine, but nothing we can do much about. I think Java 1.0's issues are unrelated to CAS' issues.

To manipulate larger structures using CAS you'd need to use indirection and access via pointer, then CAS the pointer itself. The garbage collector helps there a lot by magically solving the issue of retiring obsoleted pointers.

A correctly defined CAS loop does not hang the application; progress is guaranteed and statistically each and every thread will make progress. Of course, if you use CAS to implement a mutex, then, well, you have the advantages and liabilities of a mutex.


Andrei

Kevin Bealer wrote:
> So, if I understand correctly, the main thing the shared provides
> (relative to, say, an implicitely shared global in in gcc) is
> (relatively) simple memory barriers in the right places as well as
> compare and swap, which can be used to do lock-free style programming?
> 
> One thing that strikes me as potentially tricky with the lock free style
> -- it seems like it isn't composable at all.  What I mean is that even
> if you get a really high quality and fast lock-free hash map running, if
> you need to take something (a struct, say) out of the hash map, do
> something with it, and then put it back in, you can write shared
> lock-free logic for the struct, and for the hash map, but you can't
> easily make the entire operation of take-out, update, put-back lock free
> in any easy way, right?
> 
> On a theoretical level, these are cool structures but it seems like we
> will still have the problem that Java 1.0 had, which is that it had
> thread save Vector primitives but there was no way to enforce
> consistency between them.  Consistency only refers to one of the two
> lists at a time.
> 
> Likewise, if you have a struct with one integer you can do CAS.  If you
> have two integers, you can figure out a 2-word CAS, but then if you have
> three you are sunk again.  If you come up with a trick for three, you
> lose with four.
> 
> Since D has such great built in containers, doing things like
> associative arrays as lock-free seems great.  But I'm thinking the
> majority of the time for ordinary users, this feature would be used
> either for simple insert, singly linked list, or fall back to a spin
> lock to surround all your operations (in which case you lose the
> guarantee that one thread can pause without hanging the app.)
> 
> Kevin
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency

On Wed, Jan 6, 2010 at 11:13 PM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> CAS-based coding is tricky, but that's not our problem - we offer no more and no less than the tools to define CAS-based designs. As a bonus, we disallow values that participate in CAS operations to be handled unwittingly by threads that believe have exclusive access. I think this is a very good setup.
>

There's a lot of good here, I agree.  I think it's admirable and great that CAS is first of all being supported in the language instead of either no support or requiring a gordian knot of #ifdefs and special cases for different architectures as with C/C++.  If power can be found, then power to the people.  And of course proper memory barriers are crucial too.

I guess it feels weird to me for something that is considered so 'expert' by the people who work with it right now, to be made such a general feature of the language, but I guess that is just a matter of getting accustomed to it.  Some beginner's intro to steer the young and restless away from thin ice (e.g. "it's not as easy as you think to get this right") should be available somewhere near where people discover this thing (TDPL?).

What you say is a general critique addressed to CAS, which is fine, but
> nothing we can do much about. I think Java 1.0's issues are unrelated to CAS' issues.
>

Right, I'm just talking about CAS in general and the composability problem. It can't be fixed for CAS or I don't expect it can, anyway.

The connection I was making with Java 1.0's approach is that Containers were troublesome because you can't encapsulate (hide) the locking behavior of anything.  If HashMap<T> has it's own locking scheme then it needs to know and/or make demands about the locking behavior of T.getHash().  CAS based lock-free maps have the same property -- if the action to put an object in an ordered lock-free container accesses a global shared list but the getHash() or opCmp() for that object accesses the same global list (maybe the object contains another list which is lazy initialized), they could potentially bump into each other and live-lock.  (I don't know if HashMap existed in Java 1.0, I'm playing fast and loose with Java history here.)

It should be rare of course, but this means that knowledge of locking behavior is still part of the API and the developer who is assembling these pieces needs to know the locking of every part to combine them safely.  And this safety analysis is not really trivial and gets worse as more pieces exist.

I guess I'm wishing that a conceptual framework without this problem (e.g. message passing doesn't seem to have it AFAIK) could be made both nearly as tight as CAS based designs and still somehow preserve OO or modular composability.


To manipulate larger structures using CAS you'd need to use indirection and
> access via pointer, then CAS the pointer itself. The garbage collector helps there a lot by magically solving the issue of retiring obsoleted pointers.
>
> A correctly defined CAS loop does not hang the application; progress is guaranteed and statistically each and every thread will make progress. Of course, if you use CAS to implement a mutex, then, well, you have the advantages and liabilities of a mutex.
>
>
> Andrei
>

(But by all means, a working CAS is a great thing too, don't let me slow you
down!)

Thanks,
Kevin


> Kevin Bealer wrote:
>
>> So, if I understand correctly, the main thing the shared provides
>> (relative to, say, an implicitely shared global in in gcc) is (relatively)
>> simple memory barriers in the right places as well as compare and swap,
>> which can be used to do lock-free style programming?
>>  One thing that strikes me as potentially tricky with the lock free style
>> -- it seems like it isn't composable at all.  What I mean is that even if
>> you get a really high quality and fast lock-free hash map running, if you
>> need to take something (a struct, say) out of the hash map, do something
>> with it, and then put it back in, you can write shared lock-free logic for
>> the struct, and for the hash map, but you can't easily make the entire
>> operation of take-out, update, put-back lock free in any easy way, right?
>>  On a theoretical level, these are cool structures but it seems like we
>> will still have the problem that Java 1.0 had, which is that it had thread
>> save Vector primitives but there was no way to enforce consistency between
>> them.  Consistency only refers to one of the two lists at a time.
>>  Likewise, if you have a struct with one integer you can do CAS.  If you
>> have two integers, you can figure out a 2-word CAS, but then if you have
>> three you are sunk again.  If you come up with a trick for three, you lose
>> with four.
>>  Since D has such great built in containers, doing things like associative
>> arrays as lock-free seems great.  But I'm thinking the majority of the time
>> for ordinary users, this feature would be used either for simple insert,
>> singly linked list, or fall back to a spin lock to surround all your
>> operations (in which case you lose the guarantee that one thread can pause
>> without hanging the app.)
>>  Kevin
>>
>>
>> ------------------------------------------------------------------------
>>
>>
>> _______________________________________________
>> dmd-concurrency mailing list
>> dmd-concurrency at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>>
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100107/36a6f0db/attachment-0001.htm>

Kevin Bealer wrote:
> So, if I understand correctly, the main thing the shared provides
> (relative to, say, an implicitely shared global in in gcc) is
> (relatively) simple memory barriers in the right places as well as
> compare and swap, which can be used to do lock-free style programming?
> 
> One thing that strikes me as potentially tricky with the lock free
> style -- it seems like it isn't composable at all.  What I mean is
> that even if you get a really high quality and fast lock-free hash map
> running, if you need to take something (a struct, say) out of the hash
> map, do something with it, and then put it back in, you can write
> shared lock-free logic for the struct, and for the hash map, but you
> can't easily make the entire operation of take-out, update, put-back
> lock free in any easy way, right?
If the Hash table is designed with composeability in mind:

With a little hand waving...

struct Ref(T) { T v; T* base; alias v this; }

class CASHashMap(V,K)
{
    private T*[] data; // store stuff as array of pointers to immutable
objects

    Ref!(V) opIndex(K);  // return the value by value with a pointer to
the source
    Ref!(V) opIndexAssign(ref Ref!(T), K); // make copy of new value and
CAS it with the old one, do something* on failure
}

* thrown on failure might work. Another option would be to only allow update of Ref!(T).v via a delegate that gets called again on failure but thats messy.

OTOH that is just another form of the CAS 2 vs CAS 3 problem. The system only works if you have the right abstractions.

-BCS

Benjamin Shropshire wrote:
> OTOH that is just another form of the CAS 2 vs CAS 3 problem. The system only works if you have the right abstractions.

What do you mean by CAS 2 and CAS 3?

Andrei

Andrei Alexandrescu wrote:
> Benjamin Shropshire wrote:
>> OTOH that is just another form of the CAS 2 vs CAS 3 problem. The system only works if you have the right abstractions.
>
> What do you mean by CAS 2 and CAS 3?
>

The problem Kevin cited of their being 1 and 2 word CAS ops, but no 3 word CAS, and if their was a 3 word CAS, then there not being a 4 word CAS. My point being that you will end up always with some case being just out of reach.

> Andrei
>
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>

Benjamin Shropshire wrote:
> Andrei Alexandrescu wrote:
>> Benjamin Shropshire wrote:
>>> OTOH that is just another form of the CAS 2 vs CAS 3 problem. The system only works if you have the right abstractions.
>>
>> What do you mean by CAS 2 and CAS 3?
>>
> 
> The problem Kevin cited of their being 1 and 2 word CAS ops, but no 3 word CAS, and if their was a 3 word CAS, then there not being a 4 word CAS. My point being that you will end up always with some case being just out of reach.

The good news is that CAS is all we need. True, it's not easy...

Andrei

On Thu, Jan 7, 2010 at 11:05 PM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> Benjamin Shropshire wrote:
>
>> Andrei Alexandrescu wrote:
>>
>>> Benjamin Shropshire wrote:
>>>
>>>> OTOH that is just another form of the CAS 2 vs CAS 3 problem. The system only works if you have the right abstractions.
>>>>
>>>
>>> What do you mean by CAS 2 and CAS 3?
>>>
>>>
>> The problem Kevin cited of their being 1 and 2 word CAS ops, but no 3 word CAS, and if their was a 3 word CAS, then there not being a 4 word CAS. My point being that you will end up always with some case being just out of reach.
>>
>
> The good news is that CAS is all we need. True, it's not easy...
>
>
> Andrei
>
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>

I think there are two camps here.  One is the academic / mathematical camp, that loves to tackle the "it's not easy but theory says it's possible."  The second camp is the "what are the best practices?" camp that doesn't own a microscope but looks at trade-offs between known designs.  Sort of the 'scientists' and the 'engineers'.

The scientists usually fall into the role of studying fluid dynamics with an eye toward discovering the trick to making the new and experimental but elusive frictionless pipe.  The Engineers tend to study building codes and grunge through installing plumbing most of the time, with an eye toward becoming inventors or businessmen.  Most of the industry ends up playing the 'engineer' role.

Personally I like tackling the "it's not easy" problems, or at least reading about them and pondering.  But what I'd ideally want to make sure is that both camps have a language they can work with.  That way, when the scientists discover the new breakthrough in fluid dynamics, it's more likely to be compatible with the toilets and dishwashers that everyone already has.

(Okay, I clearly need sleep.)

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100107/92677a19/attachment.htm>

Nice essay, it just doesn't apply to this case; its converse does. There has been a flurry of theoretical papers defining containers and algorithms relying on DCAS and CASN. They died off because no one has been able to implement those efficiently. The work that endured did it all with CAS.

Andrei

Kevin Bealer wrote:
> On Thu, Jan 7, 2010 at 11:05 PM, Andrei Alexandrescu <andrei at erdani.com <mailto:andrei at erdani.com>> wrote:
> 
>     Benjamin Shropshire wrote:
> 
>         Andrei Alexandrescu wrote:
> 
>             Benjamin Shropshire wrote:
> 
>                 OTOH that is just another form of the CAS 2 vs CAS 3
>                 problem. The system only works if you have the right
>                 abstractions.
> 
> 
>             What do you mean by CAS 2 and CAS 3?
> 
> 
>         The problem Kevin cited of their being 1 and 2 word CAS ops, but
>         no 3 word CAS, and if their was a 3 word CAS, then there not
>         being a 4 word CAS. My point being that you will end up always
>         with some case being just out of reach.
> 
> 
>     The good news is that CAS is all we need. True, it's not easy...
> 
> 
>     Andrei
> 
>     _______________________________________________
>     dmd-concurrency mailing list
>     dmd-concurrency at puremagic.com <mailto:dmd-concurrency at puremagic.com>
>     http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
> 
> 
> I think there are two camps here.  One is the academic / mathematical camp, that loves to tackle the "it's not easy but theory says it's possible."  The second camp is the "what are the best practices?" camp that doesn't own a microscope but looks at trade-offs between known designs.  Sort of the 'scientists' and the 'engineers'.
> 
> The scientists usually fall into the role of studying fluid dynamics with an eye toward discovering the trick to making the new and experimental but elusive frictionless pipe.  The Engineers tend to study building codes and grunge through installing plumbing most of the time, with an eye toward becoming inventors or businessmen.  Most of the industry ends up playing the 'engineer' role.
> 
> Personally I like tackling the "it's not easy" problems, or at least reading about them and pondering.  But what I'd ideally want to make sure is that both camps have a language they can work with.  That way, when the scientists discover the new breakthrough in fluid dynamics, it's more likely to be compatible with the toilets and dishwashers that everyone already has.
> 
> (Okay, I clearly need sleep.)
> 
> Kevin
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency

I'm thinking of the engineers here as people who want to build a system and aren't going to understand or safely know how to innovate with something like CAS and are just doing application code, and the scientists as people who are trying to build lock free algorithms and libraries and who do 'get' CAS.

What I'm saying is that it would be great if these two groups didn't end up split into two completely different ways of doing business.  It would be good if the libraries that were created by the scientists were usable by people who were just doing application code.

E.g. I can use my car without understanding the nanotech that triggers the air bags.  I who know little can benefit from the work of geniuses at Ford or Honda who do these incredible things, and they can benefit from having a large market for their product.

In terms of D, it would be great if the concurrency was expressed in such a way that a person writing a billing application could use data structures implemented via the CAS and similar technologies, and the language had the tools to encapsulate or hide the hard mental-model problems at least for people who don't want to cope with them.

The threat (if it can be called that) that I see is that we end up with two container libraries, one that is a highly technical piece of research that you need to understand lock-free and wait-free concepts to use, and the one that is a warmed over copy of the Java or STL libs (don't get me wrong, I like the STL most of the time) that the vast majority of consumers use but which doesn't and probably never will benefit from the CAS work.

Kevin

On Fri, Jan 8, 2010 at 8:03 AM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> Nice essay, it just doesn't apply to this case; its converse does. There has been a flurry of theoretical papers defining containers and algorithms relying on DCAS and CASN. They died off because no one has been able to implement those efficiently. The work that endured did it all with CAS.
>
> Andrei
>
> Kevin Bealer wrote:
>
>> On Thu, Jan 7, 2010 at 11:05 PM, Andrei Alexandrescu <andrei at erdani.com<mailto: andrei at erdani.com>> wrote:
>>
>>    Benjamin Shropshire wrote:
>>
>>        Andrei Alexandrescu wrote:
>>
>>            Benjamin Shropshire wrote:
>>
>>                OTOH that is just another form of the CAS 2 vs CAS 3
>>                problem. The system only works if you have the right
>>                abstractions.
>>
>>
>>            What do you mean by CAS 2 and CAS 3?
>>
>>
>>        The problem Kevin cited of their being 1 and 2 word CAS ops, but
>>        no 3 word CAS, and if their was a 3 word CAS, then there not
>>        being a 4 word CAS. My point being that you will end up always
>>        with some case being just out of reach.
>>
>>
>>    The good news is that CAS is all we need. True, it's not easy...
>>
>>
>>    Andrei
>>
>>    _______________________________________________
>>    dmd-concurrency mailing list
>>    dmd-concurrency at puremagic.com <mailto:dmd-concurrency at puremagic.com>
>>
>>    http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>>
>>
>> I think there are two camps here.  One is the academic / mathematical
>> camp, that loves to tackle the "it's not easy but theory says it's
>> possible."  The second camp is the "what are the best practices?" camp that
>> doesn't own a microscope but looks at trade-offs between known designs.
>>  Sort of the 'scientists' and the 'engineers'.
>>
>> The scientists usually fall into the role of studying fluid dynamics with an eye toward discovering the trick to making the new and experimental but elusive frictionless pipe.  The Engineers tend to study building codes and grunge through installing plumbing most of the time, with an eye toward becoming inventors or businessmen.  Most of the industry ends up playing the 'engineer' role.
>>
>> Personally I like tackling the "it's not easy" problems, or at least reading about them and pondering.  But what I'd ideally want to make sure is that both camps have a language they can work with.  That way, when the scientists discover the new breakthrough in fluid dynamics, it's more likely to be compatible with the toilets and dishwashers that everyone already has.
>>
>> (Okay, I clearly need sleep.)
>>
>> Kevin
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>>
>> _______________________________________________
>> dmd-concurrency mailing list
>> dmd-concurrency at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>>
>  _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100108/7d55146b/attachment-0001.htm>