SPSCQueue.h
A single producer single consumer wait-free and lock-free fixed size queue written in C++11.
Example
SPSCQueue<int> q(2);
auto t = std::thread([&] {
while (!q.front());
std::cout << *q.front() << std::endl;
q.pop();
});
q.push(1);
t.join();
See src/SPSCQueueExample.cpp for the full example.
Usage
-
SPSCQueue<T>(size_t capacity);Create a
SPSCqueueholding items of typeTwith capacitycapacity. Capacity need to be greater than 2. -
void emplace(Args &&... args);Enqueue an item using inplace construction. Blocks if queue is full.
-
bool try_emplace(Args &&... args);Try to enqueue an item using inplace construction. Returns
trueon success andfalseif queue is full. -
void push(const T &v);Enqueue an item using copy construction. Blocks if queue is full.
-
template <typename P> void push(P &&v);Enqueue an item using move construction. Participates in overload resolution only if
std::is_constructible<T, P&&>::value == true. Blocks if queue is full. -
bool try_push(const T &v);Try to enqueue an item using copy construction. Returns
trueon success andfalseif queue is full. -
template <typename P> void try_push(P &&v);Try to enqueue an item using move construction. Returns
trueon success andfalseif queue is full. Participates in overload resolution only ifstd::is_constructible<T, P&&>::value == true. -
T *front();Return pointer to front of queue. Returns
nullptrif queue is empty. -
pop();Dequeue first elment of queue. Invalid to call if queue is empty. Requires
std::is_nothrow_destructible<T>::value == true.
Only a single writer thread can perform enqueue operations and only a single reader thread can perform dequeue operations. Any other usage is invalid.
Huge page support
In addition to supporting custom allocation through the standard custom allocator interface this library also supports standard proposal P0401R3 Providing size feedback in the Allocator interface. This allows convenient use of huge pages without wasting any allocated space. Using size feedback is only supported when C++17 is enabled.
The library currently doesn't include a huge page allocator since the APIs for allocating huge pages are platform dependent and handling of huge page size and NUMA awareness is application specific.
Below is an example huge page allocator for Linux:
#include <sys/mman.h>
template <typename T> struct Allocator {
using value_type = T;
struct AllocationResult {
T *ptr;
size_t count;
};
size_t roundup(size_t n) { return (((n - 1) >> 21) + 1) << 21; }
AllocationResult allocate_at_least(size_t n) {
size_t count = roundup(sizeof(T) * n);
auto p = static_cast<T *>(mmap(nullptr, count, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
-1, 0));
if (p == MAP_FAILED) {
throw std::bad_alloc();
}
return {p, count / sizeof(T)};
}
void deallocate(T *p, size_t n) { munmap(p, roundup(sizeof(T) * n)); }
};
See src/SPSCQueueExampleHugepages.cpp for the full example on how to use huge pages on Linux.
Implementation
The underlying implementation is a ring buffer.
Care has been taken to make sure to avoid any issues with false sharing. The head and tail pointers are aligned and padded to the false sharing range (cache line size). The slots buffer is padded with the false sharing range at the beginning and end.
References:
- Intel. Avoiding and Identifying False Sharing Among Threads.
- Wikipedia. Ring buffer.
- Wikipedia. False sharing.
Testing
Testing lock-free algorithms is hard. I'm using two approaches to test the implementation:
- A single threaded test that the functionality works as intended, including that the element constructor and destructor is invoked correctly.
- A multithreaded fuzz test that all elements are enqueued and dequeued correctly under heavy contention.
Benchmarks
Throughput benchmark measures throughput between 2 threads for a SPSCQueue<int> of size 256.
Latency benchmark measures round trip time between 2 threads communicating using 2 queues of type SPSCQueue<int>.
The following numbers are for a 2 socket machine with 2 x Intel(R) Xeon(R) CPU E5-2620 0 @ 2.00GHz.
| NUMA Node / Core / Hyper-Thread | Throughput (ops/ms) | Latency RTT (ns) |
|---|---|---|
| #0,#0,#0 & #0,#0,#1 | 63942 | 60 |
| #0,#0,#0 & #0,#1,#0 | 37739 | 238 |
| #0,#0,#0 & #1,#0,#0 | 25744 | 768 |
Cited by
SPSCQueue have been cited by the following papers:
- Peizhao Ou and Brian Demsky. 2018. Towards understanding the costs of avoiding out-of-thin-air results. Proc. ACM Program. Lang. 2, OOPSLA, Article 136 (October 2018), 29 pages. DOI: https://doi.org/10.1145/3276506
About
This project was created by Erik Rigtorp <[email protected]>.
836 Dec 25, 2022
7.4k Jan 3, 2023
50 Nov 23, 2022
129 Dec 31, 2022
2.1k Jan 4, 2023
392 Dec 3, 2022
3.6k Dec 29, 2022
6 Sep 9, 2021
81 Dec 30, 2022
30 Jan 7, 2023
1.7k Jan 5, 2023
21 May 30, 2021
33 Dec 22, 2022
77 Dec 30, 2022
1 Nov 28, 2022
30 Sep 19, 2022
50 Dec 8, 2022