A bounded single-producer single-consumer wait-free and lock-free queue written in C++11
A bounded single-producer single-consumer wait-free and lock-free queue written in C++11
A single producer single consumer wait-free and lock-free fixed size queue written in C++11. This implementation is faster than both boost::lockfree::spsc and folly::ProducerConsumerQueue.
…cpp #include
template struct Allocator { using value_type = T;
struct AllocationResult { T *ptr; size_t count; };
size_t roundup(size_t n) { return (((n - 1) >> 21) + 1) (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 based on a [ring
buffer](https://en.wikipedia.org/wiki/Circular_buffer).
Care has been taken to make sure to avoid any issues with [false
sharing](https://en.wikipedia.org/wiki/False_sharing). The head and tail indices
are aligned and padded to the false sharing range (cache line size).
Additionally the slots buffer is padded with the false sharing range at the
beginning and end, this prevents false sharing with any adjacent allocations.
This implementation has higher throughput than a typical concurrent ring buffer
by locally caching the head and tail indices in the writer and reader
respectively. The caching increases throughput by reducing the amount of cache
coherency traffic.
To understand how that works first consider a read operation in absence of
caching: the head index (read index) needs to be updated and thus that cache
line is loaded into the L1 cache in exclusive state. The tail (write index)
needs to be read in order to check that the queue is not empty and is thus
loaded into the L1 cache in shared state. Since a queue write operation needs to
read the head index it's likely that a write operation requires some cache
coherency traffic to bring the head index cache line back into exclusive state.
In the worst case there will be one cache line transition from shared to
exclusive for every read and write operation.
Next consider a queue reader that caches the tail index: if the cached tail
index indicates that the queue is empty, then load the tail index into the
cached tail index. If the queue was non-empty multiple read operations up until
the cached tail index can complete without stealing the writer's tail index
cache line's exclusive state. Cache coherency traffic is therefore reduced. An
analogous argument can be made for the queue write operation.
This implementation allows for arbitrary non-power of two capacities, instead
allocating a extra queue slot to indicate full queue. If you don't want to waste
storage for a extra queue slot you should use a different implementation.
References:
- *Intel*. [Avoiding and Identifying False Sharing Among Threads](https://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads).
- *Wikipedia*. [Ring buffer](https://en.wikipedia.org/wiki/Circular_buffer).
- *Wikipedia*. [False sharing](https://en.wikipedia.org/wiki/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 item constructor and destructor is invoked
correctly.
- A multi-threaded fuzz test verifies that all items are enqueued and dequeued
correctly under heavy contention.
## Benchmarks
Throughput benchmark measures throughput between 2 threads for a queue of `int`
items.
Latency benchmark measures round trip time between 2 threads communicating using
2 queues of `int` items.
Benchmark results for a AMD Ryzen 9 3900X 12-Core Processor, the 2 threads are
running on different cores on the same chiplet:
| Queue | Throughput (ops/ms) | Latency RTT (ns) |
| ---------------------------- | ------------------: | ---------------: |
| SPSCQueue | 362723 | 133 |
| boost::lockfree::spsc | 209877 | 222 |
| folly::ProducerConsumerQueue | 148818 | 147 |
## 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:
## About
This project was created by [Erik Rigtorp](http://rigtorp.se)
.No open issues yet, or sync has not completed.