www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What about std.lockfree ?

reply "denizzzka" <4denizzz gmail.com> writes:
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.
Oct 18 2012
next sibling parent reply "denizzzka" <4denizzz gmail.com> writes:
(RDCSS is a part of MCAS)
Oct 18 2012
parent "denizzzka" <4denizzz gmail.com> writes:
"falls"? I mean fails, of course :-) sorry for my English
Oct 18 2012
prev sibling parent =?UTF-8?B?IsOYaXZpbmQi?= <oivind.loe gmail.com> writes:
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 



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