On Feb 9, 2012, at 2:17 PM, Sean Kelly wrote: > On Feb 9, 2012, at 11:57 AM, Martin Nowak wrote: >> >> I didn't yet got around to polish my lock-free SList/DList implementations, >> but mutexes should only become a problem with high contention when you need >> to block. >> You'd also would need some kind of blocking for lock-free lists. > > No blocking should be necessary for the lock-free list. Just try to steal a > node with a CAS. If the result was null (i.e. if the list ended up being > empty), allocate a node via malloc/GC.
I just realized that the free-list is actually a stack, so doing this lock-free runs into the ABA problem. There goes the idea of this being an easy optimization.
