A lock-free queue is a concurrent data structure that allows multiple threads to enqueue and dequeue items without using mutexes or locks. Instead, it relies on atomic operations (compare-and-swap) to ensure thread safety.
The key advantage in game development: no thread can block another. With a mutex-based queue, if the game thread locks the queue while the AI thread needs to add a result, the AI thread stalls until the lock is released. With a lock-free queue, both threads can operate simultaneously.
In Unreal Engine, TQueue<T> provides a lock-free single-producer/single-consumer (SPSC) queue. The DonAI Navigation plugin uses these to pass pathfinding tasks and results between the game thread and the worker thread without any locks.
Trade-offs:
- Pros — no deadlocks, no priority inversion, predictable latency
- Cons — harder to implement correctly, may use more CPU cycles (spinning), SPSC queues only work with exactly one producer and one consumer