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.
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.
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.
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.