10 ms·
A lock-free, concurrent, generic queue in 32 bits
- anonymoushn 5y agoThis 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/ https://rigtorp.se/ringbuffer/
- phlip9 5y agoseparate cache lines not pages :)
- anonymoushn 5y agoYou are correct, of course
- zozbot234 5y agoBut 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.
- gpderetta 5y agoBecause 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.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- yvdriess 5y agoOnly for SPSC. You need H/T consistency in other cases for full/empty checks. Cmon AMD/Intel, give us hardware queues already :)
- vlovich123 5y agoI 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…
- gpderetta 5y agoYes! You can use (futex based) event counts to add blocking behaviour to any lock free queue.
- anonymoushn 5y agoI 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?
- tialaramex 5y agoI don't see how spin waiting constitutes parking? In what sense is the execution context "parked" if in fact it's just spinning?
- couchand 5y agoNot the GP, but I read "we use spin waiting" as a response to "aren't you wasting a bunch of CPU cycles" in the sense that "yes, but it's the least bad option".
- sgtnoodle 5y agoA 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".
- gigatexal 5y agoThe c code examples are odd: For (;;) … While (condition…) … Why not use while in both situations, so while(1)… instead of for(;;) ?
- Taniwha 5y agoit's no big deal, just one person's coding style, I've done the same thing for at least 40 years now
- asveikau 5y agoBoth are common in idiomatic C. for (;;) is less typing.
- deleted 5y ago[deleted]
- dataflow 5y 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 (;;)
- chrisseaton 5y agoMany many decades ago, non-optimising compilers would literally check 1==1 on each iteration of the latter. Not a problem now.
- rowanG077 5y agoAnd why would you need to write while(1==1) and not just while(1)?
- chrisseaton 5y agoYou don’t - but the compiler needs to test if 1 is true (so conceptually 1==1) every iteration if it isn’t an optimising compiler. They lack the code to remove a tautological test. But approximately all compilers these days are optimising compilers, so don’t worry about it.
- deleted 5y ago[deleted]
- mh7 5y agoWhy 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.
- orlp 5y agoThis 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.
- mh7 5y agoNo, nothing breaks with unsigned integers. Modular arithmetic makes it work. Try a few examples close to UINT_MAX if you want to convince yourself.
- stingraycharles 5y agoIt does imply that UINT_MAX needs to be divisible by “bufsize” if I’m not mistaken, right? So that the modulo boundaries align with the overflow.
- properparity 5y agoNot necessarily divisible, but requires power of 2 bufsize with this code (but you probably want that anyway to avoid division). With non-power-2 bufsize you need some extra logic for write/readix++, but the rest of the code can stay the same.
- rep_lodsb 5y agoThat doesn't seem right... If bufsize is a power of 2, doing the modulo would be exactly the same as just using a smaller integer type (like 8 bits on a microcontroller). What we want is the integer wraparound to never coincide with the buffer position wrapping. For that we would need a size that has some other factor than 2, and thus a "real" modulo operation in the indexing (which is slow). Or is there an error in my thinking? edit: Duh, I understand now. If the counter has at least twice the range as the buffer size, the subtraction will always give the correct number of elements used. Power of 2 or not doesn't matter. Not having to do the subtraction could still give a performance benefit, and if the buffer elements aren't very large, one wasted slot is worth the tradeoff.
- Matthias247 5y agoWhy 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?
- arinlen 5y 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 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_consts 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 5y agoI'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.
- flaviut 5y agoModern processors use something like https://en.m.wikipedia.org/wiki/MOESI_protocol https://en.m.wikipedia.org/wiki/MOESI_protocol to share data between processors. So basically, writing a shared line is expensive. Atomic reads are free, as are atomic writes to a cache line that no one else is using.
- binarycoffee 5y agoThe 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#L5754 https://github.com/golang/go/blob/master/src/runtime/proc.go... [2] https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue
- amelius 5y 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 5y agoIn 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.
- amelius 5y 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.
- dundarious 5y ago
- JonChesterfield 5y ago32bit 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.
- binarycoffee 5y agoNote 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.
- bob1029 5y agoHead 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.
- pclmulqdq 5y agoThis 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.
- bob1029 5y ago> 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. This is why newer versions of LMAX offer additional wait strategies beyond BusyWait. The one I prefer to use, unless latency is absolutely insanely critical, is the YieldingWait strategy.
- gpderetta 5y agoAn 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.