[dmd-concurrency] composability

[Kevin Bealer]

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>