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