Lock-free lists

Hello Steve,

It all depends on whether you are willing to do single-producer for single-consumer or multiple cases.

Herb (the guy who invented C++) talks about it here:
http://www.ddj.com/cpp/210600279

then he corrects it here:
http://www.ddj.com/cpp/210604448

And finally includes lock-free multiplicity code here:
http://www.ddj.com/cpp/211601363

(I have implemented a slighty different form, I allocate about 25 buffers (1MB each), but due to copyrights, I cannot give the code). It works quite well.

All the best ;-)

Quote:

Original post by ddlox Herb (the guy who invented C++) talks about it here:

Somewhere, a guy called Bjarne is crying.

Quote:

Does anyone know of an implementation of, or describe how I can write a lock-free free list where I can allocate X nodes up-front, and then use lock-free methods to add or remove these nodes from the list?

GPG6 IIRC covers this. It's quite customary to use pre-allocated storage to avoid the need for hazard pointers.

Quote:

Original post by ddlox Hello Steve, [snip]

Thanks, I'll take a look at those links this evening.

Quote:

Original post by Antheus GPG6 IIRC covers this. It's quite customary to use pre-allocated storage to avoid the need for hazard pointers.

Ah ha, I'd forgotten about that - I'll have a look when I get home, thanks

The other alternative is to write your own lock-free pooled allocator, which really isn't too hard; you just use a CAS on the allocation pointer. The only complex bit is tracking when all of the memory in the pool is used so you can release it. I've solved this by keeping an allocation counter which is also incremented/decremented via CAS. Once the counter reaches zero, the allocation pointer is reset to the head of the pool, and things continue as normal.

Of course you also have to handle the case where you fill up the pool and need to allocate a second pool to work from; since this is fairly rare I've left it to use a standard new and don't worry about the lock overhead.

Or you could use two fast forward queues to hand the objects (which are owned by the producer) there and back. The advantage of this is that it doesn't need any atomic operations at all, neither in the pool allocator, nor for passing the objects from thread to thread. For more than one consumer, use a pair of ffd queues per consumer, and do round robim scheduling in your producer.

Normally, I don't recommend anything published on DDJ, as some of the articles there (even the ones written by people who should know) contain so dramatic mistakes that you sometimes really wonder what the authors were thinking.
However, fast forward queues (which were also described on DDJ) work so surprisingly well that one simply can't ignore them. They're fast and don't need any special instructions or operating system support, and nevertheless, they're working perfectly well for single producer / single consumer (which intuitively, you would never believe).

The article in GPG6 seems to be exactly what I need; it shows how to write a lock-free list, queue and freelist, so I can mix and match to use the freelist to allocate the nodes (Or similar).

Thanks for all the replies,
Steve