[dmd-concurrency] composability

[Benjamin Shropshire]

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