Is There a Production Ready Lock-Free Queue or Hash Implementation in C++

C++ Lock free producer/consumer queue

You'll need to make several of the pointers std::atomic, as you note, and you'll need to use compare_exchange_weak in a loop to update them atomically. Otherwise, multiple consumers might consume the same node and multiple producers might corrupt the list.

How do I build a lockless queue?

You could probably implement a limited-size queue with least difficulty... I was thinking about it lately and came up with this design, but you can probably find many other interesting ideas: (WARNING: it might have some issues!)

• the queue is an array of pointers to items
• you have to manage 2 pointers (head, tail) which work over the queue in the same way as a circular buffer
• if head == tail, there are no items
• if you want to enqueue(ptr), Interlocked-Swap tail with NULL (prev_tail is the swapped value)
  
  
  • if prev_tail == NULL, try again
  • if prev_tail + 1 (with wraparound) == head, your queue is full
  • otherwise put your ptr in *prev_tail and assign prev_tail+1 to tail (watch out for buffer wrap-around)
• for dequeue() make a copy tmp_head=head and check tmp_head == tail
  
  • if it's true, return because the queue is empty
  • if it's false
    
    
    • save *tmp_head as ptr
    • do a CAS: compare head with tmp_head swap head with head+1
    • if CAS failed -- start the whole function over
    • if it succeeded -- return ptr

You can wait on both head and tail CAS operations, but if the queue is not contended, you should succeed the first time, without unnecessary locks.

Unlimited-size queues are "a bit" harder ;) But you should be able to create a big-enough queue for most needs.

What is the reason why high level abstractions that use lock free programming deep down aren't popular?

There are few people who are familiar enough with the field to implement easy-to-use lock-free libraries. Of those few, even fewer publish work for free and of those almost none do the vital additional work to make the library useable - e.g. publish full API docs, etc. They tend to just release a zip file with code in, which is almost useless. Then of course you also need to find a library which is written in the language you want to use, compiles on the platform you're using and finally, word of the library has to get out, so people know it exists.

Patents are an issue, in that they limit what can be offered. There is, for example, to my knowledge no unpatented singly-linked list. All the skip list stuff is heavily patented, too.

A hero in this field is Cliff Click, who came up with a lock-free hash, which he has more-or-less placed in the public domain.

You can find my lock-free library here;

http://www.liblfds.org

Another is Samy Bahra's Concurrency Kit;

http://www.concurrencykit.org

Lock-free algorithm library

See Practical lock-free data structures from the University of Cambridge

Fast C++ single producer single consumer implementation

You will want to look at Intel's Thread Building Blocks. They build on the primitives provided by x86's user-mode atomic operations, and pthreads or Win32 threads, and provide fast, efficient, templated data structures. A concurrent queue is among many.

Is there a concurrent container library for C++

Have a look at the container classes of Intel TBB. The reference says:

The container classes permit multiple
threads to simultaneously invoke
certain methods on the same container.

STL containers thread-safeness for producer/consumer pattern

Another option would be to have 2 deques, one for read another for write. The main thread reads, and the other writes. When the read deque is empty, switch the deques (just move 2 pointers), which would involve a lock, but only occasionally.

The consumer thread would drive the switch so it would only need to do a lock when switching. The producer thread would need to lock per write in case the switch happens in the middle of a write, but as you mention the consumer is less performance-critical, so no worries there.

What you're suggesting regarding no locks is indeed dangerous as others mention.

---

Related Topics