moodycamel::ConcurrentQueue

Use BlockingConcurrentQueue<T> when consumers should wait for items to become available. Note that you must coordinate the shutdown (e.g., by tracking the number of promised elements) to prevent consumers from calling wait_dequeue and blocking forever after all producers have finished.

BlockingConcurrentQueue<Item> q;
const int ProducerCount = 8;
const int ConsumerCount = 8;
// Track how many items are expected in total
std::atomic<int> promisedElementsRemaining(ProducerCount * 1000);

// Producers
for (int i = 0; i != ProducerCount; ++i) {
	producers[i] = std::thread([&]() {
		for (int j = 0; j != 1000; ++j) {
			q.enqueue(produceItem());
		}
	});
}

// Consumers
for (int i = 0; i != ConsumerCount; ++i) {
	consumers[i] = std::thread([&]() {
		Item item;
		while (promisedElementsRemaining.fetch_sub(1, std::memory_order_relaxed) > 0) {
			q.wait_dequeue(item);
			consumeItem(item);
		}
	});
}

The queue supports both implicit and explicit methods for enqueueing and dequeueing.

Implicit Methods

When using implicit methods (e.g., enqueue(item)), the queue automatically allocates a thread-local producer sub-queue. These sub-queues are marked for reuse once the thread exits, though support for this varies by platform.

Explicit Methods

Explicit methods use user-provided tokens (e.g., enqueue(prod_token, item)).

• Performance: Explicit methods are almost always faster.
• Lifetime: Explicit producers are tied directly to their tokens' lifetimes.
• Short-lived threads: If you are using the queue from many short-lived threads, it is highly recommended to use explicit producer tokens to avoid the overhead and potential issues of managing many implicit sub-queues.

Ordering Note

Because the queue uses independent sub-queues for producers, it is not linearizable. If two producers enqueue at the same time, there is no defined ordering between their elements when dequeued. However, elements from any individual producer will always come out in the order they were put in.

When producers and consumers run concurrently, you must coordinate their shutdown to ensure all items are processed. Using ConcurrentQueue<T> (non-blocking) requires manual coordination (e.g., using atomic counters) to signal when producers are finished so consumers know when to stop calling try_dequeue.

ConcurrentQueue<Item> q;
const int ProducerCount = 8;
const int ConsumerCount = 8;
std::atomic<int> doneProducers(0);
std::atomic<int> doneConsumers(0);

// Producers
for (int i = 0; i != ProducerCount; ++i) {
	producers[i] = std::thread([&]() {
		while (produce) {
			q.enqueue(produceItem());
		}
		doneProducers.fetch_add(1, std::memory_order_release);
	});
}

// Consumers
for (int i = 0; i != ConsumerCount; ++i) {
	consumers[i] = std::thread([&]() {
		Item item;
		bool itemsLeft;
		do {
			// Check if producers are done before attempting final dequeue
			itemsLeft = doneProducers.load(std::memory_order_acquire) != ProducerCount;
			while (q.try_dequeue(item)) {
				itemsLeft = true;
				consumeItem(item);
			}
		} while (itemsLeft || doneConsumers.fetch_add(1, std::memory_order_acq_rel) + 1 == ConsumerCount);
	});
}

The ConcurrentQueue can use per-producer and per-consumer storage to speed up operations via Tokens. Tokens are not thread-safe and should ideally be created once per thread (one ProducerToken and/or one ConsumerToken). While not strictly tied to a specific thread, they must only be used by a single producer or consumer at a time.

Efficiency Hierarchy:

1. Bulk methods with tokens
2. Bulk methods without tokens
3. Single-item methods with tokens
4. Single-item methods without tokens

In single-producer, multi-consumer scenarios, you can use try_dequeue_from_producer with a ProducerToken to reduce overhead.

// Using tokens for faster enqueue/dequeue
moodycamel::ConcurrentQueue<int> q;

// Producer side
moodycamel::ProducerToken ptok(q);
q.enqueue(ptok, 17);

// Consumer side
moodycamel::ConsumerToken ctok(q);
int item;
q.try_dequeue(ctok, item);
assert(item == 17);

The try_enqueue method never allocates memory; it returns false if the queue is full. To use this reliably, you must pre-allocate sufficient space in the constructor.

Because the queue uses blocks (default size 32) and handles producers/consumers in a way that leaves partially filled blocks, simple sizing is insufficient.

Sizing Formulas for $N$ elements:

• Explicit producers (using tokens): (ceil(N / BLOCK_SIZE) + 1) * MAX_NUM_PRODUCERS * BLOCK_SIZE
• Implicit producers (no tokens): (ceil(N / BLOCK_SIZE) - 1 + 2 * MAX_NUM_PRODUCERS) * BLOCK_SIZE
• Mixed producers: ((ceil(N / BLOCK_SIZE) - 1) * (MAX_EXPLICIT_PRODUCERS + 1) + 2 * (MAX_IMPLICIT_PRODUCERS + MAX_EXPLICIT_PRODUCERS)) * BLOCK_SIZE

Note: You can use the constructor overload that accepts $N$, MAX_EXPLICIT_PRODUCERS, and MAX_IMPLICIT_PRODUCERS directly to let the queue calculate the required size for you.

Important: Even with correct sizing, try_enqueue might fail under high contention due to the queue's eventual consistency. Always handle the false return case (e.g., by looping).