Is there a production ready lock-free queue or hash implementation in C++ [closed]

As of 1.53, boost provides a set of lock free data structures, including queues, stacks and single-producer/single-consumer queues (i.e. ring buffers).


The starting point would be either of Herb Sutter's DDJ articles for either a single producer and consumer or multiple ones. The code he gives (in-line starting on the second page of each article) uses the C++0x style atomic<T> template type; which you can imitate using the Boost interprocess library.

The boost code is buried in the depths of the interprocess library, but having read through the appropriate header file (atomic.hpp) the implementations for the necessary compare-and-swap operations on the systems I am familiar with look sound.


Facebook's Folly seems to have lock free data structures based on C++11 <atomic>:

  • ProducerConsumerQueue with docs and example code here.

  • AtomicHashMap with docs and example code here

I would dare to say these are currently used in production, so I guess they could safely be used in other projects.

Cheers!


Yes!

I wrote a lock-free queue. It has Features™:

  • Fully wait-free (no CAS loops)
  • Super fast (over a hundred million enqueue/dequeue operations per second)
  • Uses C++11 move semantics
  • Grows as needed (but only if you want it to)
  • Does lock-free memory management for the elements (using pre-allocated contiguous blocks)
  • Stand-alone (two headers plus a license and readme)
  • Compiles under MSVC2010+, Intel ICC 13, and GCC 4.7.2 (and should work under any C++11 fully-compliant compiler)

It's available on GitHub under the simplified BSD license (feel free to fork it!).

Caveats:

  • Only for single-producer single-consumer architecture (i.e. two threads)
  • Thoroughly tested on x86(-64), and should work on ARM, PowerPC, and other CPUs where aligned native-sized integers and pointer loads and stores are naturally atomic, but has not been field tested on non-x86 CPUs (if someone has one to test it on let me know)
  • No idea if any patents are infringed upon (use at your own risk, etc.). Note that I did design and implement it myself from scratch.

There is such a library, but it's in C.

Wrapping to C++ should be straightforward.

liblfds