[dmd-concurrency] composability

[Andrei Alexandrescu]

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