## digitalmars.D - What about std.lockfree ?

- "denizzzka" <4denizzz gmail.com> Oct 18 2012
- "denizzzka" <4denizzz gmail.com> Oct 18 2012
- "denizzzka" <4denizzz gmail.com> Oct 18 2012
- =?UTF-8?B?IsOYaXZpbmQi?= <oivind.loe gmail.com> Nov 16 2012

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.

Oct 18 2012

"falls"? I mean fails, of course :-) sorry for my English

Oct 18 2012

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.

Nov 16 2012