atomic_queue

C++14 multiple-producer-multiple-consumer lock-free queues based on circular buffers and [std::atomic][3].

Designed with a goal to minimize the latency between one thread pushing an element into a queue and another thread popping it from the queue.

It has been developed, tested and benchmarked on Linux. Yet, any C++14 platform implementing std::atomic is expected to compile the unit-tests and run them without failures just as well.

Continuous integrations running the unit-tests on GitHub are set up for x86_64 and arm64 platforms, Ubuntu-22.04, Ubuntu-24.04 and Windows. Pull requests to extend the [continuous integrations][18] to run the unit-tests on other architectures/platforms are most welcome.

Design Principles

When minimizing latency a good design is not when there is nothing left to add, but rather when there is nothing left to remove, as these queues exemplify.

Minimizing latency naturally maximizes throughput. Low latency reciprocal is high throughput, in ideal mathematical and practical engineering sense. Low latency is incompatible with any delays and/or batching, which destroy original (hardware) global time order of events pushed into one queue by different threads. Maximizing throughput, on the other hand, can be done at expense of latency by delaying and batching multiple updates.

The main design principle these queues follow is minimalism, which results in such design choices as:

• Bare minimum of atomic instructions. Inlinable by default push and pop functions can hardly be any cheaper in terms of CPU instruction number / L1i cache pressure.
• Explicit contention/false-sharing avoidance for queue data members and its elements.
• Linear fixed size ring-buffer array. No heap memory allocations after a queue object has constructed. It doesn't get any more CPU L1d or TLB cache friendly than that.
• Value semantics. Meaning that the queues make a copy/move upon push/pop and keep no references/pointers to its function arguments after returning, and that no reference/pointer to elements in the queue ring-buffer can be obtained. Simplest to use, hard to misuse, best machine code due to no pointer aliasing possible.

The impact of each of these small design choices on their own is barely measurable, but their total impact is much greater than a simple sum of the constituents' impacts, aka super-scalar compounding or synergy. The synergy emerging from combining multiple of these small design choices together is what allows CPUs to perform at their peak capacities least impeded.

These design choices are also limitations:

• The maximum queue size must be set at compile time or construction time. The circular buffer side-steps the memory reclamation problem inherent in linked-list based queues for the price of fixed buffer size. See [Effective memory reclamation for lock-free data structures in C++][4] for more details. Fixed buffer size may not be that much of a limitation, since once the queue gets larger than the maximum expected size that indicates a problem that elements aren't consumed fast enough, and if the queue keeps growing it may eventually consume all available memory which may affect the entire system, rather than the problematic process only. The only apparent inconvenience is that one has to do an upfront calculation on what would be the largest expected/acceptable number of unconsumed elements in the queue.
• There are no OS-blocking push/pop functions. This queue is designed for ultra-low-latency scenarios and using an OS blocking primitive would be sacrificing push-to-pop latency. For lowest possible latency one cannot afford calling the OS kernel or blocking in the OS kernel because the wake-up latency of a blocked thread is about 1-3 microseconds, whereas this queue's round-trip time (push a message to another thread and pop its reply) can be below 100 nanoseconds. CPU vulnerability mitigations made system calls dramatically more expensive, crippling performance even worse. In general, handing off spin-waiting to an OS blocking primitive is a problem with no satisfactory low-latency solutions.

Ultra-low-latency applications need just that and nothing more. The minimalism pays off, see the [throughput and latency benchmarks][1].

Role Models

Several other well established and popular thread-safe containers are used for reference in the [benchmarks][1]:

Queue	Type	Description
std::mutex	MPMC	A fixed size ring-buffer with std::mutex.
pthread_spinlock	MPMC	A fixed size ring-buffer with pthread_spinlock_t.
boost::lockfree::spsc_queue	SPSC	A wait-free queue from Boost library.
boost::lockfree::queue	MPMC	A lock-free queue from Boost library.
moodycamel::ConcurrentQueue	quasi-MPMC	A lock-free queue used in non-blocking mode. Designed to maximize throughput at the expense of latency, eschewing global time order, by emulating a MPMC queue with a bunch of SPSC queues under the hood. It is not equivalent to other queues benchmarked here in this respect.
moodycamel::ReaderWriterQueue	SPSC	A lock-free queue used in non-blocking mode.
xenium::michael_scott_queue	MPMC	A lock-free queue proposed by Michael and Scott (similar to boost::lockfree::queue which is also based on the same proposal).
xenium::ramalhete_queue	MPMC	A lock-free queue proposed by Ramalhete and Correia.
xenium::vyukov_bounded_queue	MPMC	A bounded queue based on the version proposed by Vyukov.
tbb::spin_mutex	MPMC	A locked fixed size ring-buffer with tbb::spin_mutex from Intel Threading Building Blocks.
tbb::concurrent_bounded_queue	MPMC	Eponymous queue used in non-blocking mode from Intel Threading Building Blocks.

Using the library

The containers provided are header-only class templates, no building/installing is necessary.

Installing

From GitHub

1. Clone the project:

   git clone https://github.com/max0x7ba/atomic_queue.git
   

2. Add atomic_queue/include directory (use full path) to the include paths of your build system.
3. #include <atomic_queue/atomic_queue.h> in your C++ source.

If you use CMake, these can be simplified as follows:

add_subdirectory(atomic_queue)
target_link_libraries(main PRIVATE atomic_queue::atomic_queue)

From GitHub using cmake FetchContent

You can also use CMake's FetchContent.

include(FetchContent)
FetchContent_Declare(
        atomic_queue
        GIT_REPOSITORY https://github.com/max0x7ba/atomic_queue.git
        GIT_TAG v1.9.2
)
FetchContent_MakeAvailable(atomic_queue)
target_link_libraries(main PRIVATE atomic_queue::atomic_queue)

From vcpkg

vcpkg install atomic-queue

It provides CMake targets:

find_package(atomic_queue CONFIG REQUIRED)
target_link_libraries(main PRIVATE atomic_queue::atomic_queue)

Install using conan

Follow the official tutorial on how to consume conan packages. Details specific to this library are available in ConanCenter.

Build and run

Building is necessary to run the unit-tests and benchmarks.

GNU Make Makefile is the original/reference build system this project has been developed, unit-tested and benchmarked with. It is feature-complete and most efficient, but the least portable to anything else than Linux. Linux tools, however, are the ultimate best for development, benchmarking, deep performance analyses and profiling at CPU instruction level.

CMake and Meson build systems provide the greatest portability and easy usage/consumption of the library, build and run the unit-tests on their supported platforms. They provide the best library user experience, as opposed to best library developer experience.

Build and run unit-tests

Building and running the unit-tests require Boost.Test library (e.g. libboost-test-dev on Debian/Ubuntu). Installing the complete set of Boost development libraries is the easiest (e.g. libboost-all-dev on Debian/Ubuntu).

git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue

Then:

# Build and run the unit-tests with gcc (default).
make -R -j$(($(nproc)/2)) BUILD=debug run_tests

# Build and run the unit-tests with gcc,gcc-14,clang,clang-20 in parallel.
make -R -j$(($(nproc)/2)) BUILD=debug TOOLSET=gcc,gcc-14,clang,clang-20 run_tests

Build and run benchmarks

Building and running the benchmarks require additional third-party libraries:

• Boost.Lockfree library. Installing the complete set of Boost development libraries is the easiest (e.g. libboost-all-dev on Debian/Ubuntu).
• Intel TBB library (e.g. libtbb-dev on Debian/Ubuntu). When Intel TBB library is installed elsewhere, you may like to specify that location in cppflags.tbb and ldlibs.tbb in Makefile.
• Several other third-party libraries are expected to be cloned into sibling directories:

git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git

git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue

Then:

make -R -j$(($(nproc)/2)) run_benchmarks_n       # Build and run the benchmarks once.
make -R -j$(($(nproc)/2)) run_benchmarks_n N=3   # Build and run the benchmarks 3 times.

make -R -j$(($(nproc)/2)) TOOLSET=gcc-14 run_benchmarks_n    # Build with gcc-14 and run the benchmarks.
make -R -j$(($(nproc)/2)) TOOLSET=clang-20 run_benchmarks_n  # Build with clang-20 and run the benchmarks.

taskset --cpu-list 0,1,14,15 make -R -j$(($(nproc)/2)) TOOLSET=gcc-14 run_benchmarks_n  # Use only cpus [0,1,14,15] to build with gcc-14 and run the benchmarks 3 times.

Library contents

Available queues

• AtomicQueue - a fixed siz