A lock-free, concurrent, generic queue in 32 bits

https://nullprogram.com/blog/2022/05/14/

by signa11 • 4 years ago

163 89 4 years ago

This is cool but it seems like it occupies an unusual place in tradeoff space. Most of the time SPSC queues would benefit from having the start and end pointers in separate pages, or even having cached copies of the start and end pointers in even more separate pages to avoid atomics[0].

[0] https://rigtorp.se/ringbuffer/

phlip9• 4 years ago

separate cache lines not pages :)

anonymoushn5• 4 years ago

You are correct, of course

zozbot234• 4 years ago

But then those accesses have to be protected by a lock in order to enforce invariants between "start" and "end". The whole point of representing both with a single atomic value is that this makes it trivial to preserve those required invariants.

gpderetta7• 4 years ago

Because the queue grows only in one direction and it is consumed in the other direction, reading a stale value from the other side is still safe, so two-word atomicity is not needed.

In fact the other side value is normally cached in a local memory location so to amortize the cost of roundtrips over multiple reads and writes.

vlovich123• 4 years ago

I wonder if there’s a way to integrate futexes in there to let consumers and producers park. Otherwise whenever the rate of production or consumption is meaningfully different (which it is in the real world), there’s a lot of CPU being wasted…

anonymoushn5• 4 years ago

I can't speak to the use case of TFA, but in some contexts where similar data structures are prominently used we park by spin waiting (which may include looking at all our other queues) because we don't want to pay a bunch of microseconds of latency for actually being descheduled and resheduled again.

Maybe TFA is for embedded use?

tialaramex3• 4 years ago

I don't see how spin waiting constitutes parking? In what sense is the execution context "parked" if in fact it's just spinning?

sgtnoodle3• 4 years ago

A lock free queue still helps to have, even if you use an explicit semaphore or futex to synchronize threads at a higher level. A producer can queue up multiple items per post, and a consumer can empty the queue between pends. Without the lock free queue, the queue itself would have to be protected by a mutex. It's actually nice when lock free data structure implementations leave OS level synchronization up to the caller. It makes the implementation more generally useful and portable. It's perhaps a less obvious example of "dependency injection".

gpderetta7• 4 years ago

Yes! You can use (futex based) event counts to add blocking behaviour to any lock free queue.

gigatexal• 4 years ago

The c code examples are odd:

For (;;) … While (condition…) …

Why not use while in both situations, so while(1)… instead of for(;;) ?

Taniwha2• 4 years ago

it's no big deal, just one person's coding style, I've done the same thing for at least 40 years now

asveikau• 4 years ago

Both are common in idiomatic C.

for (;;) is less typing.

dataflow• 4 years ago

Why not use while in both situations, so while(1)… instead of for(;;) ?

Because some compilers warn that the condition is constant and suggest you rewrite it as for (;;)

chrisseaton5• 4 years ago

Many many decades ago, non-optimising compilers would literally check 1==1 on each iteration of the latter.

Not a problem now.

rowanG0774• 4 years ago

And why would you need to write while(1==1) and not just while(1)?

mgaunard• 4 years ago

Someone made a similar comment on my code recently, is that a generational thing?

for (;;) has always been the idiomatic way to do an infinite loop.

throwaway_2382• 4 years ago

I started programming in C circa 1997, following a brother who started a few years earlier, and always used while(1).

FWIW https://github.com/robohack/ucb-csrg-bsd contains both variants.

sgtnoodle3• 4 years ago

The semantics of the for loop with an omitted condition more accurately conveys the intent. "Loop forever", vs. "Loop while true is true". A clever compiler will optimize it to the same machine code, but conceptually the while loop is more complex. It requires understanding what a tautology is, for example.

timmb• 4 years ago

I’m used to seeing for(;;) in C code but I disagree that it’s conceptually similar - the opposite actually. The for() syntax is already inconsistent with three expressions being interpreted as statement;guard-expression;statement.

There’s no other occasion I can think of where an expression becomes vacuously true by being omitted. If it were conceptually coherent you’d write for(;true;). I guess maybe the reason they made C accept for(;;) but not while() is because while() might confuse a compiler by looking like a function call.

JonChesterfield5• 4 years ago

Even a really stupid compiler is going to map for(;;) and while(1) to the same thing. An unconditional back branch at the end of the block. Anything else would be more work.

david2ndaccount• 4 years ago

I personally prefer ‘for’ for both cases actually ;)

mh72• 4 years ago

Why do so many people use the head==tail as full condition?

You can use the entire buffer and not waste one slot by doing:

push: buf[writeidx % bufsize] = x;

writeidx++;

pop: x = buf[readidx % bufsize];

readidx++;

Unsigned integers, you get size by doing: writeidx - readidx; Then you check size==0 or size==bufsize to detect empty/full.

orlp2• 4 years ago

This breaks when your indices wrap around the integer limit. I'm not saying this can't be worked around but you end up with something much more complicated than just head==tail. It's a memory/runtime trade-off that I think is worth wasting one slot for.

mh72• 4 years ago

No, nothing breaks with unsigned integers.

Modular arithmetic makes it work. Try a few examples close to UINT_MAX if you want to convince yourself.

adrian_b3• 4 years ago

This method is fine, but with it you must always take care to choose bufsize as a power of two, otherwise the overhead of having to do integer divisions for all queue operations may be noticeable.

arinlen3• 4 years ago

but with it you must always take care to choose bufsize as a power of two, otherwise the overhead of having to do integer divisions

Keep in mind that one of the reasons behind the arbitrary "power of two" requirement is that the method proposed by the author abuses a single atomic integer to hold two shorts representing the indices for the head and tail elements.

I don't think it makes much sense to talk about overhead given this method requires doing a bunch of bitmasks to operate over the high and low short.

dundarious2• 4 years ago

Fabian Giesen's always excellent blog has a post about various ring buffer implementations: https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-qu...

He has a companion post about a "magic" ring buffer that uses a virtual memory mapping to make a ring buffer where you can always address the entire sizes as contiguous memory, but I think it has a bit of minor bit rot in the linked implementations. https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

kevin_thibedeau• 4 years ago

This creates an ambiguity for testing the full and empty conditions. You end up having to store an additional atomic flag to track that state.

Matthias2472• 4 years ago

Why is the _Atomic qualifier on the actual data array here required? Shouldn't it be part of the atomic qualifiers on the index read/write operations to make sure those are not reordered and the memory is actually valid? Given array elements could be > 64bit in size I guess it won't be to make the access actually atomic? Is it another hint to the compiler not to reorder things? Not super familiar with those C qualifiers, and therefore curious.

And is the acquire ordering on push/pop and release on commit the right thing?

arinlen3• 4 years ago

Why is the _Atomic qualifier on the actual data array here required?

Also, my C skills are lacking but I recall that C's support for atomic data structures is a higher-level abstraction that could very well use locks under the hood.

C's support for atomics even provides a atomic_is_lock_free function which is used to check whether a data structure is lock-free or not.

https://en.cppreference.com/w/c/atomic/atomic_is_lock_free

Using ints with C's atomics does not ensure the atomic data type is lock-free. C even provides a macro to verify whether the primitive data type has lock-free access or not.

https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_cons...

Using C's atomic in this context to claim lock-free status sounds a lot like hand-waving over the problem domain to pretend locks aren't there. It's a cool read, but the underlying claim doesn't really hold.

slimsag• 4 years ago

I've heard rumors that on modern processors, "lock free" doesn't even make a ton of sense. It's actually contention that is costly, when there is no contention atomic data structures are virtually free as I understand it.

Don't know if there is data to back that up, though.

JonChesterfield5• 4 years ago

The data array / buffer doesn't need to be atomic. Once the atomic load/store on indices has justified access to the data you're good.

C puts atomic on the type, not the operation. That's conservative and occasionally very annoying (can't use normal stores in some parts of the program and atomic in others, thanks to aliasing rules) but doesn't hurt this particular application.

dahart• 4 years ago

There’s a paragraph in the article about this.

“The single producer and single consumer didn’t require locks nor atomic accesses to the storage array since the queue guaranteed that accesses at the specified index were not concurrent. However, this is not the case with multiple-consumers. Consumers race when popping. The loser’s access might occur after the winner’s commit, making its access concurrent with the producer. Both producer and consumers must account for this.”

Matthias2472• 4 years ago

Yes, I read that one, but still didn't understand what will change in code generation due to it. If it's about the read on the consumer side not being reordered after the commit, then I assumed the release on the atomic will take care of it. Maybe I'll throw it into godbolt later on to figure out.

binarycoffee3• 4 years ago

The multiple-consumer version looks extremely similar, if not identical, to the Go [1] and Tokio [2] local work-stealing queues.

These do a bit more though, as they also allow batch stealing operations.

[1] https://github.com/golang/go/blob/master/src/runtime/proc.go...

[2] https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue

amelius4• 4 years ago

It can store up to 32,767 elements at a time — more than enough for message queues, which must always be bounded.

Imagine I have a Gui where the user presses a button, upon which a message is sent to a queue, upon which a consumer reads it and performs some long-running task. Why should that queue be bounded?

Hercuros• 4 years ago

In an interactive application, you probably don't want to allow the user to queue up 30000 actions that will then slowly get executed over the next, say, 10 minutes. That would mean there is an extremely large delay between taking a UI action and seeing the result of that action (because the other 29999 actions have to be handled before the latest one can be handled). That's also why some applications display a progress spinner and block you from interacting with the UI further (of course that's not always ideal either, you might want to have some small queue and optimistically update the UI already).

If they are just batch background tasks (i.e. there is no expectation of seeing some immediate UI update as a response), then having a larger queue might be fine. There's not really that much reason to put a (small) limit on say the number of files to be downloaded in a queue. And having a really large queue bound is not that dissimilar from having an arbitrarily large queue (limited be memory of course), in terms of buffer bloat and added latency.

amelius4• 4 years ago

If they are just batch background tasks (i.e. there is no expectation of seeing some immediate UI update as a response), then having a larger queue might be fine.

"Larger" is not good enough; you really want an unbounded queue (unbounded in theory of course), because otherwise the GUI thread might block at some point. Unless you want to spend a lot of effort on exception handling (at which point unbounded is still the best choice, see below).

Also, unnecessary restrictions in your program might cause problems in the future when your software is ported to a larger architecture, or when demands change.

secondcoming3• 4 years ago

Why would it be preferable for it to be unbounded?

Bounds let you have a `try_push` function that can obviously fail, whereas with unbounded you can only really know it failed because of OOM, or your producer thread gets blocked.

When `try_push` failure happens you know something strange is happening in your code.

amelius4• 4 years ago

Unbounded can also have a try_push() functionality.

Unbounded is preferable because that's how we do everything else, and best prepares for porting to larger architectures. Do your strings have a maximum size, for example?

anonymoushn5• 4 years ago

Does your device have infinite memory?

JonChesterfield5• 4 years ago

32bit here turns out to mean head and tail indices are in the same 32bit integer and the data is somewhere else. That's enough to put head and tail in the same cache line, so it's a disaster for performance on roughly any platform.

The mpmc variant looks non-serialising (threads push multiple things before another manages to push one) so it's not a queue, and it has a cas loop in it so lock-free is a bit of a stretch.

binarycoffee3• 4 years ago

Note that the second variant does not claim to be MPMC, only SPMC.

Many lock-free structures use CAS loops. It would not be lock-free if a consumer pre-empted at the wrong time could prevent other consumers to make progress, but I don't think this is the case here.

bob10292• 4 years ago

Head and tail not being the same abstraction is the central theme for why alternatives like the LMAX Disruptor are so fast, even in MP/MC scenarios.

pclmulqdq2• 4 years ago

This queue seems to have issues with multi-producer operation. Each producer busy polls until the previous producer finishes. What happens if the previous producer gets de-scheduled while you are busy polling? You keep occupying a core that the other thread could use to do useful work.

When I transitioned from trading to tech, I realized that HFT data structures have limited usefulness when you are not also doing HFT. You can do a lot more things lock-free when you don't have to worry about adverse scheduling.

By the way, there is no easy way to fix this with an MPMC ring buffer. You have to accept some chance of adverse behavior. There may be something complicated you can do, but it's easier to just split into multiple rings.

anthomtb2• 4 years ago

Why is having head and tail in the same cache line bad for performance? Given that the code reads both head and tail to check if the queue is empty, being in the same cache line seems optimal.

anthomtb2• 4 years ago

https://rigtorp.se/ringbuffer/, from a comment below, answered my question.

In rough terms, every push or pop from the queue also causes head or tail to be written, thus dirtying a line of cache. That’s the bit I misunderstood.

atq2119• 4 years ago

it has a cas loop in it so lock-free is a bit of a stretch.

To be fair, if that's your standard, there are virtually no lock-free algorithms. The multi-consumer has a wait-free retry loop. That's pretty much as good as it gets.

And the SPSC case is lock-free under even the strictest definitions, though of course that's not particularly difficult to achieve.

JonChesterfield5• 4 years ago

That's reasonable. I'm twitchy about CAS loops because I'm used to unfair schedulers, but they're a great choice in Linux/x64 land

gpderetta7• 4 years ago

An SPSC circular queue can be implemented with just load and stores and acquire/release consistency (which is very cheap on x86), so using a single variable for both read and write pointers seems quite suboptimal.

Using two distinct 16bit _Atomic variables would have been an improvement, but I guess having both pointers in the same cacheline is going through be the bottleneck anyway.

A lock-free, concurrent, generic queue in 32 bits

Related Stories