What about std.lockfree ?

["Øivind"]

On Thursday, 18 October 2012 at 22:01:20 UTC, denizzzka wrote:
> Anyone interested in std.lockfree - lock-free lists, FIFOs, 
> stacks etc?
>
> I spent a few days doing implementations of procs, but has not 
> reached any success.
>
> My plan:
>
> For many of lock-free algorithms it is need a function MCAS 
> (multiple compare-and-swap) also called CASN (cas for n 
> elements). In fact, it is looks very easy to maintain a 
> doubly-linked lists or a trees or graphs if you can at the same 
> time to change (or not change) all links of one or more of its 
> elements. (But do not forget about ABA problem.)
>
> But:
>
> 0. MCAS/CASN and RDCSS algorithms at first seem looks like 
> brain damaging mocking puzzles
>
> 1. It is forbidden to use unproven algorithms - otherwise there 
> is a risk that the algorithm will falls sometimes and find them 
> will be difficult. This simplifies matters: just copy and paste 
> ready procs from articles!
>
> 2 Almost everywhere in these algorithms need a function CAS1
>  - proposed function core.atomic: casw 
> (http://d.puremagic.com/issues/show_bug.cgi?id=8831#c4)
>  - on casw basis CAS1 can be implemented easily (line 136: 
> https://github.com/denizzzka/casn/blob/75b0377aaa1424f3bd3fa3d47eddf4b5fd4e8038/casn.d)
>
> 3. I could not run a well-known algorithm RDCSS: it falls on 
> line 198 (Complete() function):
>
> if(isDescriptor(r)) Complete(r);
>
> I am understand why it falls - at the time of call Complete(r) 
> pointer r can point to garbage because descriptor can be 
> already removed by another thread. But I do not understand why 
> this algorithm works in other places.
>
> RDCSS described in a article "A Practical Multi-Word 
> Compare-and-Swap Operation", explanation also can be found 
> here: 
> http://cstheory.stackexchange.com/questions/7083/a-practical-multi-word-compare-and-swap-operation
>
> But it does not matter, because RDCSS algorithm has one major 
> flaw - it uses two least significant bits as flags (perhaps the 
> number of flags can be reduced to one) that indicate the type 
> of information transmitted. It is bad dirty hack and, as a 
> result, RDCSS can be used only for the exchange of pointers to 
> aligned data, which is not always acceptable.
>
> It is available another procedure called GCAS. 
> (http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf)
> This procedure has semantics similar to that of the RDCSS. But 
> I have not examined closely. I have plan to try it later.
>
> This all is a very complex, right? Someone else interested on 
> it? You see here the error in reasoning? Can someone help or 
> has finished implementation of these algorithms?
>
> It would be great if std.lockfree will be created, because it 
> will reveal many benefits of D associated with shared 
> variables. As I know Java and C# already have this.

I would be very interested in such a library, but unfortunately 
have no time to contribute.