#include <MPMCQueue.h>
Public Member Functions | |
| MPMCQueue (size_t queueCapacity) | |
| MPMCQueue () noexcept | |
Private Types | |
| using | Slot = detail::SingleElementQueue< T, Atom > |
Friends | |
| class | detail::MPMCPipelineStageImpl< T > |
Detailed Description
template<typename T, template< typename > class Atom = std::atomic, bool Dynamic = false>
class folly::MPMCQueue< T, Atom, Dynamic >
MPMCQueue<T> is a high-performance bounded concurrent queue that supports multiple producers, multiple consumers, and optional blocking. The queue has a fixed capacity, for which all memory will be allocated up front. The bulk of the work of enqueuing and dequeuing can be performed in parallel.
MPMCQueue is linearizable. That means that if a call to write(A) returns before a call to write(B) begins, then A will definitely end up in the queue before B, and if a call to read(X) returns before a call to read(Y) is started, that X will be something from earlier in the queue than Y. This also means that if a read call returns a value, you can be sure that all previous elements of the queue have been assigned a reader (that reader might not yet have returned, but it exists).
The underlying implementation uses a ticket dispenser for the head and the tail, spreading accesses across N single-element queues to produce a queue with capacity N. The ticket dispensers use atomic increment, which is more robust to contention than a CAS loop. Each of the single-element queues uses its own CAS to serialize access, with an adaptive spin cutoff. When spinning fails on a single-element queue it uses futex()'s _BITSET operations to reduce unnecessary wakeups even if multiple waiters are present on an individual queue (such as when the MPMCQueue's capacity is smaller than the number of enqueuers or dequeuers).
In benchmarks (contained in tao/queues/ConcurrentQueueTests) it handles 1 to 1, 1 to N, N to 1, and N to M thread counts better than any of the alternatives present in fbcode, for both small (~10) and large capacities. In these benchmarks it is also faster than tbb::concurrent_bounded_queue for all configurations. When there are many more threads than cores, MPMCQueue is much faster than the tbb queue because it uses futex() to block and unblock waiting threads, rather than spinning with sched_yield.
NOEXCEPT INTERACTION: tl;dr; If it compiles you're fine. Ticket-based queues separate the assignment of queue positions from the actual construction of the in-queue elements, which means that the T constructor used during enqueue must not throw an exception. This is enforced at compile time using type traits, which requires that T be adorned with accurate noexcept information. If your type does not use noexcept, you will have to wrap it in something that provides the guarantee. We provide an alternate safe implementation for types that don't use noexcept but that are marked folly::IsRelocatable and std::is_nothrow_constructible, which is common for folly types. In particular, if you can declare FOLLY_ASSUME_FBVECTOR_COMPATIBLE then your type can be put in MPMCQueue.
If you have a pool of N queue consumers that you want to shut down after the queue has drained, one way is to enqueue N sentinel values to the queue. If the producer doesn't know how many consumers there are you can enqueue one sentinel and then have each consumer requeue two sentinels after it receives it (by requeuing 2 the shutdown can complete in O(log P) time instead of O(P)).
Definition at line 106 of file MPMCQueue.h.
Member Typedef Documentation
|
private |
Definition at line 108 of file MPMCQueue.h.
Constructor & Destructor Documentation
|
inlineexplicit |
Definition at line 111 of file MPMCQueue.h.
|
inlinenoexcept |
Definition at line 117 of file MPMCQueue.h.
Friends And Related Function Documentation
|
friend |
Definition at line 107 of file MPMCQueue.h.
The documentation for this class was generated from the following file:
- proxygen/folly/folly/MPMCQueue.h
