Is there a turnkey ready-to-run queue or a hash implementation in C ++

Question

I searched a lot for a free queue in C ++. I found some code and some tests, but nothing that I could compile. A hash lock is also welcome.

SUMMARY: So far I have no positive answer. There is no “production-ready" library, and, surprisingly, not one of the existing libraries complies with the STL container API.

Answer 1

Starting with version 1.53, boost provides a set of locks without data locking , including queues, stacks, and queues of the same producer / consumer (i.e., ring buffers).

Answer 2

The starting point would be either from Herb Sutter DDJ articles, or for a single producer and consumer, or multiple copies . The code that it gives (in a line starting on the second page of each article) uses the atomic <T> type of the template; which you can simulate using the Interprocess Boost library.

The acceleration code is buried in the depths of the interprocess library, but after reading the corresponding header file (atomic.hpp), the implementations for the necessary comparison and swap operations on systems that I know look sound.

Answer 3

Facebook Folly seems to have locked data structures based on C ++ 11 <atomic> :

• ProducerConsumerQueue with documents and sample code here .

• AtomicHashMap with documents and example code here

I would dare to say that they are currently used in production, so I assume that they can be used safely in other projects.

Hurrah!

Answer 4

Yes!

I wrote a free lineup . It has features ™:

• Completely no wait (no CAS loops)
• Super fast (over a hundred million queued / deactivated operations per second)
• Uses C ++ 11 move semantics
• Growing as needed (but only if you want it)
• Memory lock control for items (using pre-allocated adjacent blocks)
• Offline (two headers plus license and read)
• It compiles under MSVC2010 +, Intel ICC 13, and GCC 4.7.2 (and should work under any C ++ 11 compiler)

It is available on GitHub under the BSD Simplified License (feel free to fork it!).

Cautions:

• Only for single-user single-user architecture (i.e. two streams)
• It has been thoroughly tested on x86 (-64) and should work on ARM, PowerPC, and other processors, where aligned root arrays and pointer and storage loads are naturally atomic, but have not been tested locally on processors other than x86 (if anyone has to check it out let me know)
• I don’t know if any patents are violated (use at your own risk, etc.). Please note that I myself designed and implemented it from scratch.

Answer 5

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

C ++ wrapper should be simple.

http://www.liblfds.org

Answer 6

After checking most of the answers, I can only indicate:

The answer is NO .

There is no such right that could be used right out of the box.

Answer 7

boost.lockfree is an attempt to create C ++ implementations without a stack stack and fifo classes.

git public repository

Answer 8

The closest thing I know about is Windows-linked lists with Windows lock . Of course, this is only Windows.

Answer 9

If you have a multi-user / single-user queue / FIFO, you can easily make one LockFree using SLIST or the trivial LIFO Lock Free stack. You have a second "private" stack for the user (which can also be done as SLIST for simplicity or any other stack model you choose). The user pops items from the private stack. Whenever a private LIFO is exhasted, you make Flush, not Pop from a shared SLIST (capturing the entire SLIST chain), and then go through the Flushed list by pushing items on a separate stack.

This works for a single producer / single consumer and for multiple manufacturers / single consumer.

However, it does not work for cases with multiple consumers (with one manufacturer or with multiple manufacturers).

In addition, with regard to hash tables, they are an ideal candidate for “splitting”, which simply divides the hash into segments that are locked into cache segments. This is how the parallel Java library works (using 32 bands). If you have an easy read-write lock, the hash table can be obtained at the same time for simultaneous reading, and you will stop only when the write occurs on the contested stripes (and, possibly, if you allow the hash table to be grown).

If you roll on your own, make sure that you alternate locks with hash elements, and do not put all the locks in an array next to each other, so you are less likely to have false access.

Answer 10

And then Intel Threading Building Blocks appeared . And for a while it was good.

PS: you are looking for concurrent_queue and concurrent_hash_map

Answer 11

I may be a little late.

The lack of solutions (with the question asked) is mainly due to an important problem in C ++ (before C ++ 0x / 11): C ++ does not (parallel memory model).

Now, using std :: atomic, you can manage memory sequencing problems and have the right comparison and swap operations. I wrote myself an implementation of Micheal & Scott lock-free queue (PODC96) using C ++ 11 and Micheal Hazard Pointers (IEEE TPDS 2004) to avoid early free and ABA issues. It works great, but it's quick and dirty, and I'm not satisfied with the actual performances. Code Available on BitBack: LockFreeExperiment

It is also possible to implement blocking without danger pointers using two-word CASs (but 64-bit versions will be available only on x86-64 using cmpxchg16b), I have a blog post about this (with untested code for queue) here: Implementing a joint comparison and double word exchange for x86 / x86-64 (LSE blog.)

My own test shows me that a double-lock queue (also on Micheal & Scott, 1996) works the same way as without a lock (I do not reach the point that locked data structures have performance problems, but my bench is too light), and the parallel queue from Intel TBB seems even better (two times faster) for a relatively small number (depending on the operating system, according to FreeBSD 9, the lowest rating I have found so far, this number is 8 threads on i7 with a 4-inch core and, after well, 8 logical processors) threads and have very strange behavior (the runtime of my simple test moves from seconds to an hour!)

Other restrictions on blocking queues after the STL style: having iterators in an unblocked queue does not make sense.

Answer 12

As far as I know, there is no such public yet. One of the problems that the developer must solve is that you need a non-blocking memory blocker that exists, although I cannot find the link right now.

Answer 13

The following is an article by Herb Sutter on out-of-line concurrent locking http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . I made some changes, such as reordering the compiler. Compiling this code requires GCC v4.4 +.

 #include <atomic> #include <iostream> using namespace std; //compile with g++ setting -std=c++0x #define CACHE_LINE_SIZE 64 template <typename T> struct LowLockQueue { private: struct Node { Node( T* val ) : value(val), next(nullptr) { } T* value; atomic<Node*> next; char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)]; }; char pad0[CACHE_LINE_SIZE]; // for one consumer at a time Node* first; char pad1[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among consumers atomic<bool> consumerLock; char pad2[CACHE_LINE_SIZE - sizeof(atomic<bool>)]; // for one producer at a time Node* last; char pad3[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among producers atomic<bool> producerLock; char pad4[CACHE_LINE_SIZE - sizeof(atomic<bool>)]; public: LowLockQueue() { first = last = new Node( nullptr ); producerLock = consumerLock = false; } ~LowLockQueue() { while( first != nullptr ) { // release the list Node* tmp = first; first = tmp->next; delete tmp->value; // no-op if null delete tmp; } } void Produce( const T& t ) { Node* tmp = new Node( new T(t) ); asm volatile("" ::: "memory"); // prevent compiler reordering while( producerLock.exchange(true) ) { } // acquire exclusivity last->next = tmp; // publish to consumers last = tmp; // swing last forward producerLock = false; // release exclusivity } bool Consume( T& result ) { while( consumerLock.exchange(true) ) { } // acquire exclusivity Node* theFirst = first; Node* theNext = first-> next; if( theNext != nullptr ) { // if queue is nonempty T* val = theNext->value; // take it out asm volatile("" ::: "memory"); // prevent compiler reordering theNext->value = nullptr; // of the Node first = theNext; // swing first forward consumerLock = false; // release exclusivity result = *val; // now copy it back delete val; // clean up the value delete theFirst; // and the old dummy return true; // and report success } consumerLock = false; // release exclusivity return false; // report queue was empty } }; int main(int argc, char* argv[]) { //Instead of this Mambo Jambo one can use pthreads in Linux to test comprehensively LowLockQueue<int> Q; Q.Produce(2); Q.Produce(6); int a; Q.Consume(a); cout<< a << endl; Q.Consume(a); cout<< a << endl; return 0; } 

Answer 14

I found another solution written in c:

http://www.ddj.com/hpc-high-performance-computing/219500200

Answer 15

I wrote this at some point, probably in 2010, I am sure through various links. This is a Single Consumer Multiprocessor.

 template <typename T> class MPSCLockFreeQueue { private: struct Node { Node( T val ) : value(val), next(NULL) { } T value; Node* next; }; Node * Head; __declspec(align(4)) Node * InsertionPoint; //__declspec(align(4)) forces 32bit alignment this must be changed for 64bit when appropriate. public: MPSCLockFreeQueue() { InsertionPoint = new Node( T() ); Head = InsertionPoint; } ~MPSCLockFreeQueue() { // release the list T result; while( Consume(result) ) { //The list should be cleaned up before the destructor is called as there is no way to know whether or not to delete the value. //So we just do our best. } } void Produce( const T& t ) { Node * node = new Node(t); Node * oldInsertionPoint = (Node *) InterLockedxChange((volatile void **)&InsertionPoint,node); oldInsertionPoint->next = node; } bool Consume( T& result ) { if (Head->next) { Node * oldHead = Head; Head = Head->next; delete oldHead; result = Head->value; return true; } return false; // else report empty } };