A high-performance, multi-producer multi-consumer (MPMC) queue implementation utilizing a fine-grained two-mutex strategy and a sentinel-node architecture to minimize contention and maximize throughput.
This implementation prioritizes reduced lock contention by decoupling production and consumption through two key architectural decisions.
Unlike a single-mutex queue that blocks all threads during any operation, this queue uses independent mutexes for the head and tail:
head_mutex: Guards thepopoperations and head pointer updates.tail_mutex: Guards thepushoperations and tail pointer updates.
This allows a producer and a consumer to operate concurrently on the queue as long as it contains more than one element.
The queue is initialized with a "dummy" node. The tail points to this dummy node, which never holds data.
- Why? In a single-element queue, the
headandtailwould normally point to the same node. Without a dummy node, a producer and consumer would contend for the same mutex. - The Invariant:
tailalways points to the next available slot, separating the modification points of producers and consumers.
This design effectively eliminates the "Empty Queue" race condition where a pop and push might collide on the same pointer, without requiring a global lock.
The following diagram illustrates the decoupled access pattern. Notice how Thread A and Thread B can operate on opposite ends of the structure simultaneously.
graph LR
subgraph Queue ["Linked List Structure"]
Head["Head (Node 1)"] --> Node2["Node 2"]
Node2 --> Dummy["Sentinel (Tail)"]
end
subgraph Producers ["tail_mutex"]
T[Thread A] --> Dummy
end
subgraph Consumers ["head_mutex"]
Pop[Thread B] --> Head
end
style Dummy fill:#f9f,stroke:#333,stroke-dasharray: 5 5
| Method | Signature | Behavior | Blocking? |
|---|---|---|---|
| Push | push(T value) |
Moves/Copies value into the queue. | No |
| Emplace | emplace_back(Args&&...) |
Perfect-forwards args to construct T in-place. |
No |
| Pop (Wait) | wait_and_pop(T&) |
Blocks until an item is available. | Yes |
| Pop (Try) | try_pop(T&) |
Returns false immediately if queue is empty. |
No |
| Pop (Timed) | wait_for_and_pop(T&, ms) |
Blocks until item available or timeout. | Timed |
| Pop (Ptr) | wait_and_pop() |
Returns std::shared_ptr<T> (blocking). |
Yes |
| Empty | empty() |
Check if queue is empty (Snapshot). | No |
#include "tsfqueue.hpp"
#include <iostream>
#include <thread>
int main() {
tsfqueue::__impl::blocking_mpmc_unbounded<int> queue;
// Producer Thread
std::jthread producer([&queue]() {
for(int i = 0; i < 10; ++i) {
queue.push(i);
std::cout << "Pushed: " << i << "\n";
}
});
// Consumer Thread
std::jthread consumer([&queue]() {
int val;
while(true) {
queue.wait_and_pop(val);
std::cout << "Consumed: " << val << "\n";
if (val == 9) break;
}
});
return 0;
}