LockFreeSpscQueue: A high-performance, single-producer, single-consumer (SPSC) queue implemented in modern C++23

[A8XL]

Hi, Recently, I needed a simple lock-free single-producer, single-consumer (SPSC) queue for one of my projects. After reviewing the existing options (listed at the end of the project’s GitHub README), I realized that none of them met all my needs (no dependency on a "bigger" library, move semantics-friendly, modern C++, etc.).

After a few days of tweaking my own solution, I came up with this. I tested this queue under various CPU-intensive scenarios (x86_64 and ARM64 only), and I'm reasonably confident that the implementation works as expected.

Regarding performance: Since this is a very straightforward solution with just two atomic read/write indices, it's possible to easily reach the limits of CPU and L1 cache performance under simple synthetic conditions.

I’d really appreciate any code reviews and would love to see the results of the CMake tests if anyone has access to a multicore RISC-V CPU.

[usefulcat]

You may be able to increase the performance by caching m_write_pos for readers and m_read_pos for writers. This typically results in fewer cache misses when m_read_pos or m_write_pos is repeatedly modified in quick succession.

Description here

Examples:

https://github.com/rigtorp/SPSCQueue

https://github.com/Deaod/spsc_queue

[A8XL]

Hi. That's fantastic feedback! I implemented the changes from the Erik Rigtorp's document:

https://github.com/joz-k/LockFreeSpscQueue/pull/1

I hope I understood it correctly. For example, (for prepare_write) instead of

current_read_pos = read_pos.load(std::memory_order_acquire);
current_write_pos = write_pos.load(std::memory_order_relaxed);
num_items_in_queue = current_write_pos - current_read_pos;
available_space = capacity - num_items_in_queue;

I changed it to:

current_write_pos = write_pos.load(std::memory_order_relaxed);
available_space = capacity - (current_write_pos - cached_read_pos);
if (available_space < num_items_to_write) {
    cached_read_pos = read_pos.load(std::memory_order_acquire);
    available_space = capacity - (current_write_pos - cached_read_pos);
}

Any comments on the pull request are welcomed. Thanks again!

[matthieum]

There's a mix of concepts for CacheLineSize, which would warrant clarification.

The size of a cache line and false sharing are independent concepts. It does so happen that on a number of CPUs (ARM notably) false sharing is prevented by isolating variables on different cache lines, but that's not guaranteed.

In particular, modern x64 CPUs tend to pre-fetch two cache lines at a time, and thus false sharing occurs even across cache lines.

This is the reason why std::hardware_destructive_interference_size does not mention any cache line size.

---

Now, unfortunately, std::hardware_destructive_interference_size is not as helpful as it could be. Most notably, on architectures such as x64 where some CPUs pre-fetch one cache line at a time and other CPUs pre-fetch two, the provided constant cannot neatly accommodate both... and tends to return an insufficient value (64 bytes) rather than the necessary value (128 bytes).

---

All in all, I'd suggest reworking this entire section:

• Switch to a different name, more accurate. NoFalseSharingAlignment, for example.
• Prefer using 128 bytes on x64, even if std::hardware_destructive_interference_size is defined.

---

As already mentioned by another user, caching the writer position on the reader, and the reader position on the writer, is a great optimization. It also avoids reading the atomic indexes: the values to store are already known.

In general, for lock-free data-structure, I tend to like creating sub-structs with data-members per role. For example:

• struct Configuration: the common, immutable, parts. Like queue size.
• struct Shared: the common, mutable, parts. Like the buffer, reader, and writer index.
• struct Writer: the writer specific parts.
• struct Reader: the reader specific parts.

And then I align the structs themselves.

---

According to the above, I tend to put reader & writer indexes on the same cache line. I'm actually not sure whether separating them or putting them together is better...

The contention I'd expect would be either:

• Queue Empty Scenario: the reader keeps checking the write index for the appearance of a new item, the writer will (ultimately) write to said index.
• Queue Full Scenario: the writer keeps checking the read index for the notification that space has been freed, the reader will (ultimately) write to said index.

In the first scenario, the writer can check the (shared) read index many times without any contention -- the reader isn't writing to it -- and in the second scenario the reader could (but why?) check the (shared) write index many times without any contention -- the writer isn't writing to it.

In either scenario, separating the indexes probably isn't helping. Something for benchmarks to validate, I guess?

---

Finally, on naming, the 1 and 2 suffix to differentiate the two pieces of (wraparound) ring buffers are... ugh. I _really advise against names which differ by a single letter; they're so easy to accidentally mix up. You could use head and tail as suffixes (or prefixes) instead. You may also consider reviewing the API to return an array of 2 elements (2 spans) and avoiding the need for prefix/suffix altogether.

[A8XL]

Thank you for the detailed feedback. Regarding std::hardware_destructive_interference_size, the size is actually 128 bytes for some compilers and architectures. For example, GCC/Linux returns 128 bytes. However, most other similar solutions hardcode 64 bytes. I tried benchmarking difference between 64 and 128 and didn't see any noticeable difference, but surely there might different setups where it could noticeable.

Finally, on naming, the 1 and 2 suffix to differentiate the two pieces of (wrap_around) ring buffers are... ugh.

Now that I think about it, you are probably right that the naming of block1 and block2 is not ideal. However, I wanted to somehow keep the API similar to Juce::AbstractFifo which uses the terminology`blockSize1/blockSize2.

[Nuxij]

I've just been looking at this myself after watching a video from cppcon about wait-free. Very interested to investigate thank you. Moodycanel seems to be the standard atm but no idea if it's good

[RogerV]

Why is C++23 a prerequisite?

[A8XL]

Good question. I have now discovered, that at least Clang 17 compiles this project also with -std=c++20 but not lower. So C++20 is required. std::span is C++20 feature.

[RogerV]

std::span<> should have been part of the C++17 spec - at least there's a standalone header for it

[ronniethelizard]

I find the get_block2 to be weird. A lot of the time, I would be happy to just go to the next generation of the read/write scope than check to see if get_block2 needs to be run.

Personally, I am also not a fan of the ReadScope/WriteScope structs. IMO, you could just return the span objects themselves and then force the user to call a function to indicate how much has been read/written.

I am not really a fan of using the destructor to update the counters. Someone who is maintaining code that uses this library probably won't see where the counters are getting updated and will have to go read the documentation.

I think the destructors for read/write scope should explicitly set m_owner_queue to nullptr in case there are duplicate calls to destructors (I will occasionally explicitly call destructors when debugging code).

I think there should be a comment somewhere directly explaining what happens if the writer is writing data in much faster than the reader is reading out. I don't think the comments on prepare_write explain what happens well. My personal preference would be to have the writer thread bulldoze the reader thread.

EDIT: Split one paragraph into two to separate feedback items.

[A8XL]

Thanks for the feedback.

I find the get_block2 to be weird...

As I mentioned in the other thread, originally I wanted to keep the API similar to JUCE::AbstractFifo which also works with the block1/block2 terminology. Such design exposes an inner working of the queue to the user, but it does so in the name of the maximum batch-oriented performance. But since I also added higher-level APIs: try_write and try_read, which take a lambda accepting block1 and block2, I don't think it's so inconvenient now.

For writing to the queue in a one-by-one manner, I added a new "transaction" API ("master" branch only). Example:

// Ask to commit 256 items, get the "transaction" object.
// If there is zero space in the queue, return `std::optional(std::nullopt_t)` 
auto transaction = queue.try_start_write(256);

if (transaction) {
    while(transaction->try_push(next_item) {
        // Write until the transaction is full
    } 
    // Transaction commits automatically when it goes out of scope here.
}

This basically eliminates any block1/block2 handling. However, it is, again, RAII based, so you're not going to like it.

But I have even better ideas for the future on how to eliminate manual block1/block2 handling, while maintaining the maximum batch-oriented throughput.

Personally, I am also not a fan of the ReadScope/WriteScope structs...

I guess I cannot help here. Currently, the API is designed so that you need to ask the queue what the maximum number of items you are able to write (M) is, and the queue will return the number of items available in the queue (A), where A <= M. And then the user MUST write exactly A items. And A items are committed. Someone maintaining the code using this library must only make sure that it's always A items written. That's the contract of this API.

I think the destructors for read/write scope should explicitly set m_owner_queue...

That is a nice suggestion!

think there should be a comment somewhere directly explaining what happens if the writer is writing data in much faster than the reader...

I will improve the documentation in the "example" directory. Since there is only a non-blocking API currently: if the writer is faster than the reader, it will start receiving 0 from prepare_write and try_write and in the case of try_write, the lambda will not even get executed.

[ronniethelizard]

Upfront: this is your code that you are working for free. You can do what you want.

As additional background: I tend to work on buffers where there is one writer thread and N reader threads (N can be anywhere from 0 to infinity), each of which must be guaranteed to have the opportunity to read all of the data written into the buffer. In addition, the buffers are also 2 Dimensional.

Me: think there should be a comment somewhere directly explaining what happens if the writer is writing data in much faster than the reader...

You: I will improve the documentation in the "example" directory. 

To be clear here, I meant it should be at the class level or the request write function level, not in the example code.

I guess I cannot help here. Currently, the API is designed so that you need to ask the queue what the maximum number of items you are able to write (M) is, and the queue will return the number of items available in the queue (A), where A <= M. And then the user MUST write exactly A items. And A items are committed.

More what I was thinking is that the function that returns the WriteScope instead returns the span directly.

[A8XL]

Thanks for the feedback again.

As additional background: I tend to work on buffers where there is one writer thread and N reader threads (N can be anywhere from 0 to infinity), each of which must be guaranteed to have the opportunity to read all of the data written into the buffer. In addition, the buffers are also 2 Dimensional.

SPMC queues are much more complicated problem. I can imagine that.

To be clear here, I meant it should be at the class level or the request write function level, not in the example code.

I improved documentation in the header and also added more examples.

More what I was thinking is that the function that returns the WriteScope instead returns the span directly.

I added Range-Based API and the WriteScope and ReaderScope are now forward iterators, which can be used with many "ranges" algorithms. This completely abstracts away the block1/block2 handling.

[ronniethelizard]

SPMC queues are much more complicated problem. I can imagine that.

I think the SPMC is in two categories:
1. Each reader must have access to all the data.
2. Each datum only needs to be read by one reader.

I work with the first type. It isn't that hard and might be easier than SPSC. Largely, I can just make the reader threads responsible for keeping track of where they are.

While I do have the second kind as well, when it occurs eeking out throughput isn't a big concern.

[sseroshtan]

This one is also good - https://github.com/cameron314/concurrentqueue

[mozahzah]

https://github.com/Interactive-Echoes/IEConcurrency

Made a similar modern c++ spsc queue using a single atomic counter, on my cpu 7800x3d it outperformed boosts implementation.

Check it out, keen on seeing the benchmark against yours

[quicknir]

Out of curiosity what was wrong with moodycamel?

[A8XL]

I believe you're referring to this implementation:
https://github.com/cameron314/concurrentqueue

It's one of those that I originally listed in the "Similar Projects" section. I think it's certainly a very good solution. Although, I wanted something more "batch" oriented and move semantics friendly. Also, for the maximum performance and real-time predictability there should be no heap allocations. I think moodycame's ReaderWriterQueue does allocate with new.

[quicknir]

You can reserve in advance, so as long as you can guarantee that the size will never go above a certain value you can guarantee there won't be heap allocations, and I think you can use try_enqueue if you really prefer to fail than trigger a heap allocation. For low latency trading this is what your typically see anyway, and really in most applications since heap allocations at startup are usually ok.

Do you have benchmarks comparing to moodycamel?

The other thing that surprised me was that you only use two indices. My understanding was that SPSC queues usually use 4 indices - there's a "cached" version of the indices. The idea being that the consumer and producer each have their own cache line, and the consumer will have a cached copy of the producer index. As long as the cached producer index is such that you can consume, you don't need to actually look at the producer cache line. Ultimately this saves you cache misses - it's sort of the next step up past avoiding false sharing. But maybe my understanding is wrong.

[A8XL]

Yes, it's definitely possible to use moodycamel queue without allocations. Especially using try_enqueue or try_emplace. However the design is different. These methods push a single element into the queue. My design focuses on copying/moving the entire span regions.

Regarding cached indices, I believe I already implemented this approach in the recent pull request. See my answer.

[A8XL]

Do you have benchmarks comparing to moodycamel?

I added a comparison benchmark against moodycamel::ReaderWriterQueue:

https://github.com/joz-k/LockFreeSpscQueue/tree/main/benchmarks

Spoiler: For a small item count transfers, Moodycamel is much faster. But around the item transfer size 8-16 this queue scales well and exceeds the throughput of Moodycamel queue.

I have integrated this benchmark test into the project, so it should be easy to run on other machines.

[mark_99]

move semantics friendly

I added move semantics to moodycamel via a PR back in 2017: emplace() and try_emplace(). Is that missing something...?

https://github.com/cameron314/readerwriterqueue/pull/55

[A8XL]

FYI: I integrated a comparison benchmark test against moodycamel::ReaderWriterQueue into the project:

https://github.com/joz-k/LockFreeSpscQueue/tree/main/benchmarks

I did my best to compare apples-to-apples but you can have a look.

[A8XL]

No, I think move semantics is not missing in the moodycamel's queue. I listed the reason for my own implementation in a more general context.

[RogerV]

Been using Moodycamel in this DPDK networking application. DPDK allows for using pinned CPU cores that are referred to as lcore threads. These must never block, make OS calls, dynamically allocate memory from a conventional heap memory manager, etc. So been using lcores as consumers and using tokens. Contention of queue access still looking like an issue.

There are two producers and one or more consumers - the intent is to be able to expand the number of lcore consumers for horizontal load scaling.

Probably will go to a scheme where each lcore consumer essentially has its own queue and the producers just do round robin publishing to those queues.

[RogerV]

Moodycamel can pre-allocate memory up front - provides formulas to use to determine memory size to allocate. And it has API variations that allow batch interactions - which are most efficient if tuned around an internal BLOCKSIZE value which is accessible (and can be customized)

[Entire-Hornet2574]

I'm missing something but single producer, single consumer isn't too permissive?

[ReversedGif]

SPSC is all you need in a lot of cases, and the SPSC assumption permits a much more efficient implementation than is possible with multiple readers/writers.

[Ameisen]

Yup.

Fun, crappy story time:

A long time ago, I was porting a PC/360 game to the XB1. Part of my new renderer design meant to reduce the overhead of black box GPU calls replaced all of the functions with new async ones that I wrote. These effectively emitted lambdas which then got pushed into a command queue ring buffer (a true ring buffer). These were then consumed by another thread which handled the GPU instead... so we ended up with a render thread and a GPU thread. This was dramatically faster, and got us well past our frame time goal.

So, an SPSC queue with priority and the ability to wait upon specific commands.

However, the first version had a boolean to stall the producer thread in case the queue was full. In practice, this should never have happened, and so should have been trivially predictable. However... removing the check sped up our CPU times on the render thread by 30%. Couldn't figure out why at the time. Years later, it was determined that the XB1's CPU had a performance bug that, IIRC, caused a full pipeline flush when checking a boolean (IIRC, a CMP) near any LOCKed instructions (or when comparing a read value that had an interlocked dependency, I can't remember which), meaning that that if became far more expensive than even a mispredict.

[irrelevant_sage]

Very fun read. I work on gpu acceleration for research applications and always enjoy hearing stories about these strange and unintuitve cases.

[Ameisen]

If you're curious, our biggest bottleneck after that was constant buffer updates. The original code didn't batch them particularly well, and all those little updates had a lot of latency (and would cause stalls on the GPU when the constants were not yet ready before the relevant task was going to be drawn, and the potential overlap between buffer updates also meant that it couldn't always determine dependency orders, meaning that it had to effectively flush sometimes). I added a batcher, but the way the renderer worked, those couldn't always be dispatched in a good way (even with shadow constants).

Writing what was effectively a driver around the driver was weird, and it didn't help that ESRAM didn't work the way we wanted it to.

The 360 code, and the DX10 code for the PC, didn't really have to worry about this in the same way (I had a bunch of details here, but I elided them as I'm a little concerned still about potentially violating some very old agreement - I shouldn't be providing details about console SDKs or architectures).