9 ms·
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11
- CyberDildonics 10y agoI've used this and relied on it, it works very well.
- tomovo 10y agoI have also used this for queuing audio buffers in my game. It works great and the author was nice enough to do a quick adjustment for me. How I used it: http://www.catnapgames.com/2016/01/19/new-sound-mixer/ http://www.catnapgames.com/2016/01/19/new-sound-mixer/
- vvanders 10y agoThere's a reason that there aren't many lock free implementations. If you don't get one from your CPU vendor then there's a high chance that it's not correct.
- wfunction 10y agoAre you saying this one isn't correct? Confused what point you're trying to make.
- vvanders 10y agoThe atomic compare and swap is only one part of getting it right. You also have to deal with memory and instruction fences. Certain architectures have different semantics when it comes to that ordering so something that works on x86 for instance might explode on PPC or ARM. If you want to verify that the algorithms are correct you basically have to do static analysis and the only way you'll do that is if you have access to the microcode and register models(I.E. you make CPUs). [edit] To put this into practical terms I spent some time working with a popular game engine that used a lockfree queue at it's core rendering path. It wasn't until 2 or 3 titles had shipped on this engine that it was discovered that there was a bug in the lockfree algo. We're talking trillions of operations under many different threading and context switching loads and at least 3 different CPU architectures.
- jdright 10y agoCan you cite the name of the tech or any of the games?
- panic 10y agoHow was the bug discovered? Sounds like a fun story.
- jjawssd 10y agoWhat was the solution?
- vvanders 10y agoMore fences :) (and the overhead that came with them)
- trungaczne 10y agoI don't get the point you're trying to make. Aren't std::memory_order's guarantees supposed to work with all support archs? The code in the OP does use memory fences. Are you implying that their implementation are incorrect?
- vvanders 10y agoI'm not implying their implementation is incorrect. Just that these types of things are very easy to get wrong and when you do it's usually the type of bugs that take months to track down after you've eliminated every other subsystem involved. Generally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. Most of the time if you're going lockfree for performance reasons there's usually much large gains to be found in your cache usage or overall architecture.
- sillysaurus3 10y agoGenerally if there's not a huge organization putting their reputation(and $$$) on the line there is going to be bugs. This argument applies to any hard problem, so it doesn't seem valid. Whether there's an important bug in a project depends on someone's skill and on how much time they've dedicated to it, and it's hard to know how skilled or dedicated someone is.
- DSMan195276 10y agoI would agree, but I'd add that it has been made a little bit easier to handle with the addition of `atomic` in C11 and C++11, since it means you can write atomic code without having to drop to inline assembly to ensure you use the right instructions to make it lock-free. That said, that's only one piece of the puzzle, and you really have to know what you're doing to ensure you write it correctly. That said, after looking at this code the author appears to know what they're doing. I'd have to read it a lot closer to really make sure though.
- ape4 10y ago`atomic` may require a lock, depending on the CPU.
- DSMan195276 10y agoTrue. In that event though, there's little other options. Locking those variables individually like that is probably worse then other locking options though, so it is worth keeping in mind. but while it would be slower, it would still be just as 'correct' as using actual atomic variables.
- eloff 10y agoYou wouldn't use this kind of queue on an architecture like that anyway, just use a lock and a regular queue (the lock is not avoidable anyway)
- flamedoge 10y agoAs far as atomic 'types' are concerned, they rely on CPU hardware for atomicity. I wouldn't be surprised if generated code for non-supported width is done using lock. http://en.cppreference.com/w/cpp/atomic/atomic http://en.cppreference.com/w/cpp/atomic/atomic
- gambiting 10y agoI've been to a C++11 presentation on multithreading recently, and x86 CPUs guarantee that all reads/writes on from std::atomic are indeed, atomic and they always happen in order they were called in. Code generated on ARM guarantees that even multi-byte reads/writes happen in one instruction, but there's no guarantee on the order.
- kitsuac 10y agoNot true at all - the core atomic operations are very well understood by now and are supported on any modern CPU.
- dbaupp 10y agoThis is a little optimistic: being able to tractibly reason about atomicity in weak memory models like C11 is still at the cutting edge of CS research. It is really hard to prove nontrivial data structures are correct.
- loeg 10y agoIf you like this, you may also like http://concurrencykit.org/ http://concurrencykit.org/ .
- film42 10y agoFacebook's folly also has a MPMC queue: https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h https://github.com/facebook/folly/blob/master/folly/MPMCQueu...
- pzh 10y agoHere is one more: https://github.com/pzhivkov/SPConcurrency https://github.com/pzhivkov/SPConcurrency (Mostly targeting iOS / macOS).
- drfuchs 10y agoFrom the documentation, it doesn't seem clear that there's any guarantee that a particular queued item will ever eventually be dequeued (in a program that runs forever). Consider the case where each producer thread queues N items, and then waits until at least one of its N items is dequeued before immediately topping back up; while the consuming thread dequeues at a slower rate than the producers are able to produce. Maybe no item from producer number 1 ever gets dequeued? Or did I miss something in the documentation?
- deleted 10y ago[deleted]
- kasey_junk 10y agoThe documentation says it's not serializable or linearizable in some cases, nor does it have preemption or fairness garauntees so you are correct.
- Unklejoe 10y agoAnother useful lockless library - http://liblfds.org http://liblfds.org It's written in C though.
- Blackthorn 10y agoI'd like to raise my hat to some absolutely fabulous documentation. That's one of the best READMEs I've seen in a very long time.
- pzh 10y agoThe README is really good for users of the library. I was looking for a description of the algorithm, though, and I couldn't find any. Does anyone know what algorithm this library implements? (e.g. a literature reference would be helpful). I'm familiar with a couple of PQ implementations based on skip-lists: Sundell & Tsigas and Linden & Jonsson--but this library doesn't seem to be based on any of them.
- colanderman 10y agoMaybe someone can educate me. I've studied them for a while, but I don't get the fascination with lock- or wait-free queues. If you actually care about real-time guarantees enough to look into lock-free solutions, you already ought to have non-preemptive workers (i.e. cooperative multitasking). This then allows you to have only one queue per CPU (since exclusive access is guaranteed), simplifying the problem. With one queue per CPU, multi-producer becomes trivial (atomic doorbell + round robin), and multi-consumer is easy (CAS to acquire a work item). You don't have fairness guarantees for consumers, but who cares, only when they are not saturated can they not be fair and then that's a good thing. Application stalls don't happen (one non-preemptible queue per CPU), application crashes are managed at a higher level, and IRQs can be disabled for the 5 cycles you spend in the critical sections. I assume I'm missing something, since I'm somewhat new at this, and lock-freedom is clearly in vogue, but I don't know what it is.
- kitsuac 10y agoCooperative multi-tasking doesn't always mean a per-worker queue is feasible. Really the only time I could see that being feasible is if the work queue is constantly saturated. Often times you just don't know in advance which worker to queue up with which task.
- colanderman 10y agoI mean to choose a queue by producer, not consumer.
- eloff 10y agoGo is a language exactly like that, but I still use lock free algorithms. The reason is even with a private per thread data structure you don't have atomic higher level operations like enqueue. So you need to disable interrupts around the data structure methods, both for the OS and the Go runtime. That will cost you more than a lock would, and afaik it's not possible from userspace on Linux (if it is I would love to know how!)
- beagle3 10y ago> If you actually care about real-time guarantees enough to look into lock-free solutions, lock free does not give any real time guarantee for any specific task (and neither does wait free, a much stronger and harder to achieve constraint) The reason I use it when I do, is that it guarantees that a problem in one thread/worker/process, e.g. a stall due to a database commit, does not make others stall as well. > (CAS to acquire a work item) Most likely, you've just described a lock free implementation. > I assume I'm missing something, since I'm somewhat new at this, and lock-freedom is clearly in vogue, but I don't know what it is. Lock freedom is the property that, at any instant, at least one thread/worker/process is making some progress independently of the others. It is a useful definitions because it doesn't care whether locks are explicit (e.g. mutex, semaphore, critical section) or implicit (polling or spinning or whatever)
- nathancahill 10y agoCan't wait to see the aphyr teardown.
- marvy 10y agoI though that was for distributed stuff??
- deleted 10y ago[deleted]
- hitlin37 10y agook, i have been also looking into concurrent vectors lately to get something like this running between two threads. Someone know or point here to a header only implementation of vector/queue with locks and really simple code with explanation ? Something written as beautifully as herb sutter's or scott meyers examples, They are easy code to play around and understand :) *An implementation without vendor concurrent library. Looking for an implementation on Linux/ARM. Although i do have access to libpthread threads and locks.
- RossBencina 10y agoNew algorithms are always welcome. But it isn't a general-purpose MPMC queue (nor does it claim to be). The following constraints are listed in the "Reasons not to use" section: - not linearizable wrt multiple producers - not NUMA aware - not sequentially consistent, quote: "things (such as pumping the queue until it's empty) require more thought to get right in all eventualities" These are subtleties (especially the first and the last) that may bite if you don't know what you're doing and just want to "plug in a queue." It's going to depend on how you use the queue. Side note: There are other examples of novel lock-free algorithms that have only been published by blog, powerpoint or github (e.g. Dmitry Vyukov's well-known work, Cliff Click's concurrent hash table, Jeff Preshing's hash table.) However, in general, lock-free algorithms are widely known to be very difficult to get correct (not too dissimilar to getting a Distributed Consensus Algorithm correct). I can't help thinking that we need a higher bar of correctness than the author's claims and some unit tests. Would you use a distributed algorithm that didn't come with a correctness proof? Personally I'd like to see a formal proof, peer review, and a Spin model. Peer-review need not be via academic channels, just something more than self-publication.
- hvidgaard 10y ago> I can't help thinking that we need a higher bar of correctness than the author's claims and some unit tests. Would you use a distributed algorithm that didn't come with a correctness proof? Not any chance. Using any multi party algorithm, without any formal proof of any kind, and you just know that there is something that will not work as expected.
- eternalban 10y ago> Would you use a distributed algorithm that didn't come with a correctness proof? That happens all the time in practice. Prior to Kyle Kingsbury's influential blogs on noSQL darlings, for example, it was not even on the geek-pop radar. And then, quite frankly, there is the gap between implementation and formal description of an algorithm. Incorrect implementation will obviate the guarantees your formal proof is asserting.
- RossBencina 10y ago
- std_throwaway 10y agoCould someone please explain for the uninitiated what lock-free actually means and why it matters. After reading http://www.drdobbs.com/lock-free-data-structures/184401865 http://www.drdobbs.com/lock-free-data-structures/184401865 i got this: * Normal locking means that the process which holds the lock can hold it arbitrarily long thereby locking out all other processes. Also a live-lock and dead-lock can occur if there is a conflict between processes which try to acquire the same set of resources but cannot acquire all of them at once. * Wait-free means that no algorithm working with the data structure will be delayed arbitrarily. This is pretty strong. A simple example would be a ring-buffer with a single reader and writer. * Lock-free means that no process can block the resource for longer than it takes to read/write it. There will always be at least one process that can make progress while the others may have to wait (weaker than wait-free, but stronger than ordinary locked). Normal processes on most operating systems can be interrupted at any instruction. This would make it impossible to carry out a multiple-instruction sequence to lock-modify-unlock the data structure because it could leave the data structure locked. Does this in turn mean that there must be a "commit" instruction that is uninterruptible?
- gpderetta 10y ago> Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, in a way. Some CPUs provide atomic instructions that perform multiple operations in a bounded time. These instructions cannot be interrupted (by other threads, the OS, interrupts) and appear all-or-nothing (i.e. the intermediate effects are not visible. The most common of such instructions is Compare And Exchange (aka CAS); CAS is often used as the 'commit' action in lock-free algorithms. Some other architectures have instead a more general 'transactional' feature (known as Load Linked/Store Conditional or LS/SC) which provides for very limited transactions of a single cacheline. A naive implementation could live-lock, but in practice server class architectures provide stronger guarantees. It can be proven that LL/SC and CAS are equally powerful (i.e. the same set of lock-free/wait-free algorithms can be implemented with both). LL/SC is more natural for RISC machines, while CAS is common in CISC, but there are plenty of counterexamples.
- RossBencina 10y agoLock-freedom and wait-freedom are formal terms in concurrent algorithm theory. Best to check out Herlihy and Shavit, "The Art of Multiprocessor Programming," which I have unfortunately temporarily misplaced. Informally: "Lock-free" means that at each time step, at least one thread that is interacting with a shared object makes progress towards completing the operation (e.g. an enqueue or dequeue operation). Neither deadlock nor livelock (where no thread makes progress) can happen (hence "lock free"). This does not guarantee fairness or starvation-freedom (a fast thread could in-theory DoS a slow thread). "Wait-free" means that at each time step, every thread will make progress. This might e.g. involve an algorithm where fast threads help slow threads complete their operations. Wait-freedom is indeed a stronger condition, but it's usually more expensive to implement (although not always). > Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, lock-free algorithms make use of atomic instructions such as CAS (compare-and-swap). Sometimes it's used as a "commit" but there might be multiple atomic operations depending on the algorithm and the data structure (so I guess, a kind-of multi-phase commit sequence). This is a nice intro paper by one of the giants of the field: Maged M. Michael, "The Balancing Act of Choosing Nonblocking Features" ACM Queue vol. 11, no. 7 http://queue.acm.org/detail.cfm?id=2513575 http://queue.acm.org/detail.cfm?id=2513575 Update: I should add that "lock free" hasn't always been a formally defined technical term, and some people use it informally to mean "doesn't use mutexes," or even "only uses atomic operations." Under such a relaxed definition a hand-coded spin-lock might be considered "lock free," but it really isn't -- if a thread holding the spinlock crashes, the spinlock would never be unlocked; such a situation could not arise with a formally lock-free algorithm.
- martincmartin 10y agoFacebook's folly library contains a general purpose, multi producer multi consumer queue[0]. It's general purpose and linearizeable. It's used extensively inside Facebook. Disclaimer: I work at Facebook. [1] https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h https://github.com/facebook/folly/blob/master/folly/MPMCQueu...
- anti-thought 10y agoFor what its worth, the base algorithm is extremely similar in concept to an Erlang queue implementation I saw recently [1]. But I do like doing these language implementation comparisons. The Erlang one definitely suffers from the base language being copy-on-write though. [1] - https://github.com/dstar4138/libemp/tree/develop/src/buffers/multiq https://github.com/dstar4138/libemp/tree/develop/src/buffers...
- dkersten 10y agoI found this earlier this year and was using it for a little toy game project to communicate between the rendering thread and everything else. Its super easy to use :) I didn't develop the project to the point where I could comment on its performance though and most of my processing was happening in shaders anyway.