On Wed, Jan 6, 2010 at 11:13 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>
</blockquote><div><br>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.<br>
<br>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?).<br>
<br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br></blockquote><div><br>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.<br>
<br>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.)<br>
<br>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.<br>
<br>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.<br>
<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>
<br>
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.<br>
<br>
<br>
Andrei<br></blockquote><div><br>(But by all means, a working CAS is a great thing too, don't let me slow you down!)<br>
<br>Thanks,<br>Kevin<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Kevin Bealer wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div><div></div><div class="h5">
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?<br>
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?<br>
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.<br>
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.<br>
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.)<br>
Kevin<br>
<br>
<br></div></div>
------------------------------------------------------------------------<div class="im"><br>
<br>
_______________________________________________<br>
dmd-concurrency mailing list<br>
<a href="mailto:dmd-concurrency@puremagic.com" target="_blank">dmd-concurrency@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/dmd-concurrency" target="_blank">http://lists.puremagic.com/mailman/listinfo/dmd-concurrency</a><br>
</div></blockquote><div><div></div><div class="h5">
_______________________________________________<br>
dmd-concurrency mailing list<br>
<a href="mailto:dmd-concurrency@puremagic.com" target="_blank">dmd-concurrency@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/dmd-concurrency" target="_blank">http://lists.puremagic.com/mailman/listinfo/dmd-concurrency</a><br>
</div></div></blockquote></div><br>