LockFreeQueue
Lock Free Queue Based On Hazard Pointer.
Feature
- Thread-safe and Lock-free.
- Hazard pointer.
- ABA safe.
- Inter thread helping.
- Singly-linked list with a sentinel node.
- Support Multi-producer & Multi-consumer.
- Dynamic size.
- Dynamically allocate nodes(performance bottlneck). Or you can simply implement a thread-safe memory pool, e.g. by thread_local storage identifier.
Benchmark
| Magnitude | Enqueue | Dequeue | Enqueue & Dequeue |
|---|---|---|---|
| 10K | 1.8ms | 1.4ms | 2.6ms |
| 100K | 33.6ms | 32.3ms | 38.6ms |
| 1000K | 209.2ms | 185.1ms | 299.3ms |
The above data was tested on my i5-7500 cpu with gcc -O3.
You can also compare the tested data with BlockingQueue which is implemented by mutex.
The data of first and second column was obtained by starting 4 threads to enqueue concurrently and dequeue concurrently, the data of third column was obtained by starting 2 threads to enqueue and 2 threads to dequeue concurrently, each looped 10 times to calculate the average time consumption. See also test.
Build
make && ./test
API
void Enqueue(const T& data);
void Enqueue(T&& data);
void Emplace(Args&&... args);
bool Dequeue(T& data);
size_t size() const;Reference
Lock-Free Data Structures with Hazard Pointers
C++ Concurrency in Action, Second Edition