Fast C++ single producer single consumer implementation

Question

I'm looking for a single-producer, single-consumer FIFO implementation that would perform faster than the normal lock-write-unlock-signal / waitForSignal-lock-read-unlock stuff. I'm looking for something supported by most POSIX operating systems (x86 specific is fine) written in either C or C++.

I'm not looking to pass anything larger than a pointer.

I'm not necessarily attached to the lock-free idea, but I do want something fast and correct. One of the papers I read on the subject mentioned a two-queue approach that seemed interesting, but I haven't been able to find much about that since then.

From the research I've done so far, 0mq (which supposedly uses a lock-free structure for its inproc:// scheme) looks like it's the most attractive option. That being said, I'd like to be sure I haven't missed anything before I go down that path.

One other alternative might involve using a POSIX message queue, but this seems like it'd be rather slow for thread <--> thread communication; is this true?

Any single-consumer single-producer lock free queue implementation in C? seems relevant, but the accepted answer there really isn't an enumeration of existing libraries as much as it is "premature optimization is bad".

Answer 1

In addition to the other answers here (and in this highly related question), I'll take this opportunity for a shameless plug of my own super-fast, C++ implementation of a single-consumer single-producer wait-free queue. It:

• 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)
• Is 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!).

A comparable queue is Facebook's Folly queue, which can be ever-so-slightly faster, but does not support growing as needed (it has a fixed size).

Answer 2

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.

Answer 3

Just stumbled on this: CDS (Concurrent Data Structures) tonight.

CDS (Concurrent Data Structures) is a C++ template library of lock-free and fine-grained algorithms. It contains a collection of concurrent data structures: queues, maps, hazard pointer reclamation schema, - and many others

I must say I'm only slightly past the /getting it to build/ stage (it wasn't as straightforward as I'd have liked) but ... you might be interested to take a look for yourself.

Answer 4

The problem is that POSIX doesn't include an API (that I know of) for interlocked operations. In fact, not all platforms support the same operations for lock-free programming (some use compare-and-swap, some use load-linked-store-conditional).

That said, the only difficult part about making a lock-free single-consumer queue (supporting multiple producers is trivial) is handling the ABA problem, and that really shouldn't be a problem.

You need a singly-linked-list for producers to add to (prepend to). The consumer has a local queue, when that's exhausted it grabs the entire producer list and reverses it, creating a new local queue. The Windows SList API is an example.