- The article explains the motivation for building a fast lock-free queue, noting that while simple mutex-based queues work for 90% of applications, high-demand systems like HFT, game engines, or audio pipelines require better performance to avoid context switch overhead.
- Lock-free queues use atomic operations and CAS loops instead of mutexes to avoid expensive kernel context switches, but they introduce challenges like the ABA problem and memory reclamation issues.
- A naive lock-free queue (Michael Scott design) suffers from three problems: excessive heap allocations (new/delete per element), poor cache locality due to scattered linked list nodes, and use-after-free/ABA bugs.
- Batching elements into fixed-size blocks (e.g., 1024 slots per node) drastically reduces allocations and improves cache locality by storing slots in contiguous memory.
- Hazard pointers solve memory reclamation safely: threads publish pointers they're about to dereference, and other threads defer deletion of any pointer still 'hazarded', preventing use-after-free.
- A thread-local node cache eliminates heap allocation on the hot path by recycling retired nodes per thread, avoiding allocator contention.
- The final FastQueue template class offers compile-time configuration (buffer size, thread count, blocking vs non-blocking, cache size) and achieves significant speedups over mutex queues, especially under high contention (up to ~12x faster in benchmarks).
- Benchmarks show the lock-free queue scales linearly with thread count, while mutex queues degrade drastically under contention due to OS scheduler overhead.