I started implementing some of lock-free data structures planned for 0.7. However I run into problem with garbage collection (namely the lock-free reference counting[1]). I started implementing instead fine-grained locks (i.e. one where CAS is implemented using locks). The implementation can be improved by use of for example hazard pointers. I will look into it soon. 1. Assuming locking will turn out to be faster and/or simpler for smaller amount of threads on Linux x86 do we need lock-free algorithm or does the concurrent access will be sufficient? 2. It seems that the only operations not possible to implement in lock-free list are prev/has_prev. I'd like to propose decoupling the ListIterator from BidirIterator and possibly introduce BidirList and BidirListIterator (the latter extending both ListIterator and BidirIterator). Regards PS. Implementation based on Mikhail Fomitchev & Eric Ruppert 2004[2] paper is present on http://gitorious.org/~uzytkownik/libgee/mpiechotkas-libgee/commits/slist [1] It requires either LL/DC or DCAS. Many architectures support LL/DC but not x86 and x86-64 which have only CAS and some for of DCAS which nonetheless seems to be a bit too weak for ref counting. [2] www.cse.yorku.ca/~ruppert/papers/lfll.pdf
Attachment:
signature.asc
Description: This is a digitally signed message part