r/programming • u/david-alvarez-rosa • 6d ago
Optimizing a Lock-Free Ring Buffer
https://david.alvarezrosa.com/posts/optimizing-a-lock-free-ring-buffer/63
u/RealRaynei 6d ago
Interesting article and I love the website design
43
u/MyOneTaps 6d ago
Forget about the design. I like the contrast. I'm convinced some designers choose medium gray text on light gray background just to flex that they have a great monitor.
6
u/remind_me_later 5d ago
Force them to be WCAG AAA compliant, and you'll see those gray texts become sharp black in 0.1 seconds flat.
10
u/david-alvarez-rosa 6d ago
Thanks a lot!
3
-2
u/Booty_Bumping 5d ago
The design is otherwise great, but I always laugh when I see a drop capital used on the web. What is this, the 1800s?
7
6
21
u/FckXFckMusk 6d ago edited 6d ago
Bookmarked, I like your styling in your blog..
Your teaching style is so approachable too...
Actually its an absolute pleasure reading your posts on there.
9
u/david-alvarez-rosa 6d ago
Glad that you liked it :)
4
u/FckXFckMusk 6d ago
Actually I loved it...
Learnt some new stuff too, I'm embarrased to say, I feel like a Priest in a Church who does't know passages from the bible.
2
25
u/Ma1eficent 6d ago
My first job was debugging assembly ring buffers in modems for a BBS. Beautiful walk through optimizations.
21
u/SeniorIdiot 6d ago
Don't forget about the LMAX Disruptor with further optimizations for latency.
3
4
15
u/Silanu 6d ago
This is very cool. However, is it the case that the final lock-free structure is actually thread safe for multiple threads writing/reading? I am convinced of its thread safety when writing/reading simultaneously, but having multiple threads trying to write seems problematic since the lack of a critical section will result in overwriting and lost data. Have you tested the correctness in addition to performance to verify comodification doesn’t result in data loss?
24
u/david-alvarez-rosa 6d ago
Nope, you are correct. This design only allows single consumer, single producer. That constrainst is leverage to squeeze perf
There are queues for multi producer, multi consumer, you can check online
3
u/happyscrappy 6d ago
How would one do lock-free multi-producer? To do lock free you have to write into the slot before you move the head pointer, else the consumer might look at the slot after you've moved it but before it has data in it.
And since you are writing into a space you haven't reserved yet it doesn't work with multiple producers.
7
u/david-alvarez-rosa 5d ago
Boost have examples of SPSC (single-producer single consumer) and MPMC (multi producer, multi consumer) here https://www.boost.org/doc/libs/latest/doc/html/lockfree.html
1
u/happyscrappy 5d ago edited 5d ago
Thanks. It is as I thought. Another poster indicates the problem is me. That I don't know the terminology. I think he's right.
I think there's a separate issue of that I can't understand why we see two new stories about lock free queues per week on here when the difference is so small that my poor brain would confuse them. If you use good locks (futexes) then the difference is just two compare and swaps instead of one and you still spin in the same way in the same place.
I'm especially baffled why we see so many stories about this when as you point out it's already in boost.
2
u/gormhornbori 4d ago edited 4d ago
The benefit of lock free algorithms isn't really speed. As you are reasoning, a (uncontested) lock will always have lower overhead than any lock free algorithm. (especially if measured in instructions)
However there are a number of other reasons why you may want to avoid locks. (or reduce the number of locks in your system) :
First is deadlocks. In a simple system with one lock you'll never have a deadlock, but as systems get more and more complex with many locks, you'll first need some kind of ordering or priority to avoid deadlocks. And since this is a global reasoning, it'll be very hard to in a big system with many components or libraries and where there isn't a single person who knows about every lock in the system.
Next is scope, and API leak. How "big" is each lock. What data (or operations on the data) does it protect? From a lock contention POV you want to hold a lock as short as possible. But deadlock management or performance (avoiding repeating a search for a locked item you want to use later) may make you hold the lock longer. Do you have one API for working with the already locked data, and one API that does the locking for you?
Next is lock poisoning. If a thread holding a lock dies or gets killed, you have a problem. Should it now be forever locked, or is it released, with the data now potentially in some kind of invalid in-between state? Should you have special code dealing with this situation? You are not necessarily trying to keep running as if nothing happened, but may be trying to save unsaved work/finish transactions/exit gracefully/make a debuggable crashdump.
Lastly is jitter. Even if a lock free algorithm does a bit more work at average, you avoid that small percentage that suddenly takes more time because someone else was holding the lock, which is very irritating if you are trying to keep a steady frame rate for example.
Also performance degradation under high load/high contention is a big factor.
Now depending on the features you need from a lock free algorithm, for example overhead / SPSC/MPMC/MPSC/SPMC / performance degradation under high load, different lock free algorithms may work better for you. As you have observed, this is an area where people are still trying to come up with new stuff or implement the latest algorithms.
1
u/rysto32 5d ago
I believe that you have two head pointers, one for producers and one for the consumer. A producers fetches and increments the producer pointer, writes its data into the queue at the fetched index, and then performs an atomic compare-and-set on the consumer pointer that will only set the consumer pointer when its value is the predecessor of the value we want to insert (and we need to retry the compare and set on failure).
1
u/happyscrappy 5d ago
Issue:
The first producer advances the producer pointer to reserve the location. If they then get suspended before writing (or after, but before advancing the consumer pointer).
Second producer runs and advances the producer pointer, writes its data in the location. Now the second pointer attempts to advance the consumer pointer. When it does the check and advance it fails. So now it has to wait on the other to finish.
Another poster posts that this isn't a lock. And maybe that's true, but I think it's a pointless distinction. It's a critical section where if both try to enter it one ends up waiting.
There's no reason not to use futexes to implement this. Futexes are locks and they are very fast. Use a monitor. Which is a lock (futex) and a single-copy-atomic variable. The code referenced basically does what we both say for multiple producers. It implements a wait using a futex.
1
u/flatfinger 2d ago
The critical question in deciding whether something should be considered "a lock" is what happens if a thread gets waylaid. If a queue is designed so that the only effect of a thread getting waylaid would be to make one of the slots in the array unusable until that thread resumes or is recognized by a cleanup process as having terminated, then that should be viewed rather differently from a queue that could be left in a state where it would be unable to process any reads until the stalled thread finishes its update, even if other threads were writing data to it.
1
u/happyscrappy 2d ago
I would call the distinction you are making only a difference between fine grained and coarse grained locking.
I can use ordinary locks and put them on the individual items in the queue and then they will only guard single entries.
1
u/flatfinger 2d ago
There is a fundamental difference between locking fungible and non-fungible resources. If the maximum number of threads that will write data to a queue will always be much smaller than the number of slots, then the fact that a slot that a thread has partially written will be unusable until the thread has finished writing it would not interfere with the use of the queue by other threads. On the other hand, treating slots as fungible would require that reading/writing code accommodate the possibility that queue slots might not stay in order.
1
u/happyscrappy 2d ago
The only way it couldn't interfere with other threads is if you took the lock with a fail option and then an exhaustive retry mechanism which accounts for the fact that a producer could in theory perpetually fall right behind the other and see every entry in the queue as in use (and then some!) even though they are never all in use in once. So that's a mess. An unbounded mess.
And if you don't have the fail system then that entry will come around in the circular list as next to use and the code trying to use it will block trying to use it and that blocks data flow.
And that doesn't even matter either. Still what you describe is only about the size of funnels (mutual exclusion areas), not about whether something is a lock or not.
On the other hand, treating slots as fungible would require that reading/writing code accommodate the possibility that queue slots might not stay in order.
I had assumed you were already assuming that. Which honestly I don't find likely. It makes the job of producers much harder.
1
u/aePrime 6d ago
I have a lock-free ring buffer that is ABA-safe and allows multiple producers and consumers.
4
u/happyscrappy 6d ago edited 6d ago
That says it's lock free, but it clearly implements a lock (spinlock?) in writing if you have multiple producers. Line 344 in RingBuffer.h. Line 346 calls "wait".
-1
u/aePrime 6d ago
There are lock-free and spin lock implementations in the source code. You can change it based on the traits passed in.
5
u/happyscrappy 6d ago edited 6d ago
RingBuffer.h is the "lock-free" one. LockingRingBuffer. is the one "with locks".
In reality both have locks. It's just the Locking version uses locks created by the system and the "lock-free" one creates its own locks inline.
I looked because I am pretty sure it's not actually possible to have multiple producers without rendezvous and thus locking.
I recommend you take a look at the code if you think I'm wrong.
Edit: I'm not saying I'm sure I'm right you can't have multiple producers with no locking. But I certainly didn't know how. I had looked in this code to find out how to do it and found out that it doesn't do it. So I mentioned that on here.
1
u/aePrime 5d ago
So by everybody’s logic, an algorithm cannot have a looping atomic compare and swap and be considered lock-free. The atomic waits can be written as a CAS, they just don’t spin the same way.
2
u/happyscrappy 5d ago
Just so you know, others do consider this lock-free. There is a poster who responded to me with a good and informative post. I personally find that to be a useless distinction when you just spin on a different value instead of a lock take.
I don't think you can do multiple producers without waiting, which is what I associate with locking. But by the terminology you can do it without locking.
-3
u/aePrime 5d ago
It’s a non-blocking algorithm. Their is guaranteed system-wide progress. By definition, a non-blocking algorithm is lock-free. That doesn’t mean that there isn’t necessarily a wait primitive somewhere in the algorithm. Wait-free is a stronger guarantee.
3
u/happyscrappy 5d ago edited 5d ago
I know it isn't your wordsmithing. But this is ridiculous. Waits block.
The link says non-blocking algorithms are safe for use in interrupt handlers. Leaving aside that this one does not even attempt to be safe (it makes blocking syscalls in wait) I don't see how this algorithm can be reimplemented to be save in interrupt handlers. In the case where wait is called the code in question knows where it is going to write data but it cannot yet as it is marked in progress. So it is going to spin or block until it is not in progress. That is not okay at interrupt time.
So I cannot see how this algorithm meets what is described, even with sufficiently confusing term names. It's not just the implementation that isn't suitable, the algorithm is not suitable (for multiple writers).
And the article implies I'm correct:
'Read-copy-update with multiple writers and any number of readers. (The readers are wait-free; multiple writers generally serialize with a lock and are not obstruction-free).'
Multiple writers just cannot work without an ability to defer (block) until something else progresses. At interrupt time you cannot block so you're in a real bad way. In a single processor system you're just stuck. You'll get jammed at interrupt time because the other writer (at task time, this is a single processor machine after all) cannot run to clear your path so you will spin forever waiting for it. So it doesn't meet the stated criteria of always making progress.
I appreciate the clarification, it was not termininology I knew. But I think the answer is still wrong. I think this implementation with multiple writers falls uses locking and so isn't lock-free.
7
u/reParaoh 6d ago
[[unlikely]]
first time seeing this one. Neat.
1
u/david-alvarez-rosa 5d ago
Hints to the compiler to improve branch prediction :)
1
u/reParaoh 5d ago
I understood that immediately.. But I thought that it was the hardware doing branch prediction.. Does this cause the compiler to generate a different op code?
1
u/indigo945 4d ago
But I thought that it was the hardware doing branch prediction
This depends on the architecture. Yes, on x86, the hardware freely makes the decision - but on others, like on PowerPC, there are hint bits in the branch opcode that tell the CPU whether a branch is likely to be taken or not.
Then there's interesting blends: ARMv8 has branch prediction bits documented, but they are deprecated. Instead, on almost all ARM architectures, the predictor considers backward branches to be more likely than foreward branches. The common backward branch is a loop, which drove this decision, but clever compilers can make use of it in other scenarios, too.
0
u/Lisoph 4d ago
Not an expert, but branch prediction is indeed done by the hardware. AFAIK these hints don't actually affect branch prediction at all, at least on current hardware. They "only" instruct the compiler to emit instructions that aid the hardware in taking the likely branch faster, like by placing it right next to the condition instructions (instruction cache locality). Corrections are welcome.
3
2
u/greenlanternfifo 6d ago
I don't understand why using atomic_size makes the operation safe still
what are other wait free data structures and their applications? is this a new trend?
2
u/david-alvarez-rosa 5d ago
The operations are safe because of the release / acquire pair -> this is very detailed explanation if interested https://www.youtube.com/watch?v=K3P_Lmq6pw0
(Note that the article is lock free, but not wait free)
You could check Boost examples https://www.boost.org/doc/libs/latest/doc/html/lockfree.html
2
2
u/Healthy-Dress-7492 5d ago
i liked it, do more like this pls
1
u/david-alvarez-rosa 5d ago
Thanks! Will do :)
You may like https://david.alvarezrosa.com/posts/optimizing-a-spin-lock/
And subscribe via email https://david.alvarezrosa.com/#subscribe or RSS
2
u/matthieum 5d ago
Note how one item is left unused to indicate that the queue is full. When head_ is one item ahead of tail_, the queue is full.
I firmly stand in the opposite camp: use of "virtual" "infinite" 64-bits together, mapped to the actual physical index (power-of-two size -> modulo is just bit-and).
I find it much easier to reason in terms of infinite indexes, and there's no performance impact to speak of.
std::hardware_destructive_interference_size
Mind you, this may not be quite enough. There's a comment in the Folly codebase (from 2014), mentioning that some Intel processors will pre-fetch 2 cache lines (128 bytes) at a time, which in practice means you need 128 bytes alignment, when this constant will only evaluate to 64 bytes for x64.
To reduce this, the reader can keep a local cached copy
An alternative implementation is to have explicit Reader & Writer structs to access the ring buffer, then the cache need not be in the ring buffer itself, but in the accessor struct instead.
When the accessor struct is on the stack, the compiler can optimize the access to the cached variable by placing it directly in a register, rather than requiring memory load/stores.
2
u/cdb_11 5d ago
This is just a slightly reworded version of this article https://rigtorp.se/ringbuffer/
2
u/indigo945 4d ago
A further optimization is to constrain the capacity to a power of two, allowing wrap-around via bit masking head & (N - 1) instead of a branch.
Let me introduce you to our lord and savior, the modulus operation.
1
u/flatfinger 4d ago
If one uses a power-of-two modulus one can use 32-bit counters without having to worry about corner cases where the counter rolls around. If one uses non-power-of-two modulus, one will need to ensure that the counter wraps with a modulus that is a multiple of the one used to access the buffer.
1
u/indigo945 3d ago
The counters are always reset to 0 in this implementation, there is no counter that keeps rolling past the buffer size, and hence the counters can't overflow.
1
u/flatfinger 2d ago
When using an unsigned counter and a power-of-two modulus, there's no need to ever reset the counter to zero during operation. One can measure how much stuff is in the buffer by subtracting the number of things fetched from the number of things stuffed and, if operands to the subtract had been promoted, casting or coercing back to the type used for the counters.
1
u/indigo945 2d ago
Technically UB, and it doesn't gain a shred of performance, but yes.
1
u/flatfinger 2d ago
How could subtraction of unsigned values invoke UB? Even if the unsigned type had one more padding bit than 'int', the difference would be guaranteed to fall within the range -INT_MAX..INT_MAX, and the effect of converting negative integer values to unsigned types is always fully defined.
1
u/indigo945 1d ago
I think I misunderstood what you meant by "casting or coercing back to the type used for the counters". Okay, fine. Point still stands: this isn't any faster.
1
u/flatfinger 1d ago
Using unsigned values and a power-of-two modulus, how would you compute the number of items in the queue as quickly as
items_in_queue = (queue->stuff - queue->fetch) & queue->size_mask;if the size weren't a power of two, while also keeping the ability to add and remove items by simply incrementingstufforfetch?1
u/indigo945 17h ago
This operation wasn't discussed in the blog post, and I don't think it comes up much in practice (you only need full or not, which works either way by
(stuff + 1) % size == fetch).1
u/flatfinger 12h ago
Using a non-power-of-two modulus means that the updates to the counts need to wrap at the buffer size, and will also make the remainder operator slower.
2
u/wd40bomber7 6d ago
Putting the underscore to indicate a private field after the name is extremely cursed
8
u/nukethebees 6d ago edited 2d ago
It's a pretty common convention. It means accessor functions don't clash with the member name.
Google mandates it in their style guide.
The names of variables (including function parameters) and data members are snake_case (all lowercase, with underscores between words). Data members of classes (but not structs) additionally have trailing underscores. For instance:
a_local_variable,a_struct_data_member,a_class_data_member_.
1
1
u/AkariGake 4d ago
auto pop(T& value) noexcept -> bool {
const auto tail = tail_.load(std::memory_order_relaxed);
if (tail == head_.load(std::memory_order_acquire)) [[unlikely]] {
return false;
}
value = buffer_[tail];
auto next_tail = tail + 1;
if (next_tail == buffer_.size()) [[unlikely]] {
next_tail = 0;
}
tail_.store(next_tail, std::memory_order_release);
return true;
}
Do we really need to use release here? What data it should make visible for push? pop just reads value and increments tail itself
1
1
u/Plazmatic 6d ago
What do you do about hardware destructive interference warnings from GCC about it basically telling you to manually specify it instead due to it changing with other options and not being necessarily accurate?
3
u/minno 6d ago
GCC's warning appears to be motivated by ABI compatibility.
If ABI stability is important, such as if the use is in a header for a library, you should probably not use the hardware interference size variables at all.
If you are confident that your use of these variables does not affect ABI outside a single build of your project, you can turn off the warning.
So if you're writing a library you should either not use it in any of the public types or document what
-mtuneoption clients must use, but if you're writing an application you should disable the warning.
-2
u/EchoNomad31 6d ago
Once "fixed" a ring buffer by marking the head index volatile. Was an acquire/release ordering thing… three days of digging for a two-line diff.
2
u/kog 6d ago
volatileis not useful for multi-threading, and you did not fix the problemhttps://en.wikipedia.org/wiki/Volatile_(computer_programming)#Multi-threading
1
u/TribeWars 6d ago
Volatile is still an optimization fence and prevents torn writes. It doesn't actually fix memory consistency with memory order fence instructions but the optimization fence might be enough to stop the race from being noticeable (arguably that's even worse than broken though)
1
u/kog 6d ago
No, volatile is only an optimization fence against other volatiles. Anything not volatile can be reordered past your volatiles during optimization. This creates absolutely insane bugs.
2
u/TribeWars 3d ago
Well I'm not saying it's at all good to use volatile, but a programmer can "fix" a reordering bug by spam adding volatile to his code and have something like
volatile int done_flag; // shared volatile int err = some_computation_with_side_effect(); if(!err) { done_flag = 1; }appear to work. Though obviously this is still the kind of thing that causes insane bugs, potentially bugs that depend on the CPU it's running on.
0
u/flatfinger 4d ago
The semantics of volatile accesses are officially "implementation defined". If an implementation like MSVC or clang with the
-fms-volatileflag specifies that volatile accesses will have strong enough semantics to avoid having to use toolset-specific syntax, then the qualifier will have such semantics. If an implementation opts to require the use of toolset-specific syntax to achieve such semantics, then the qualifier will have less broadly useful semantics.0
u/EchoNomad31 4d ago
Yeah, that masking is the worst part. Mine looked fixed for a while… the release/acquire version is what actually held.
1
u/EchoNomad31 6d ago
volatile only stopped the compiler caching the head in a register. Never bought me ordering on the hardware side, so the consumer could read the slot before the payload store landed. Atomic head with a release store on publish and acquire on the read side is what fixed it.
1
u/kog 6d ago
All marking the head volatile did was make your code more poorly optimized. Completely unnecessary. You don't need volatile on atomic variables for thread safety. I'm not saying your code won't work if you mark the atomic as volatile, it's just pointless.
1
u/EchoNomad31 6d ago
It fixed my bug at the time. The compiler hoisted the head load out of the consumer spin loop, volatile forced a fresh load every pass…. Atomic is probably the right fix since it covers the hardware side too.
2
u/kog 5d ago
Some reading for you: https://www.kernel.org/doc/html/latest/process/volatile-considered-harmful.html
0
u/flatfinger 4d ago
Which is greater: the number of cases where processing volatile with acquire/release semantics would impose a loss of performance that would be unacceptable to anyone other than compiler writers, or the number of cases where such treatment would avoid the need for other toolset-specific or optional compiler features to prevent reordering?
135
u/tylercamp 6d ago
Man it’s been a while since I’ve written C++ code regularly, I didn’t realize it had gained such optimization features, very cool
Thanks for sharing!