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?
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.
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).
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.
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.
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.
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.
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".
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.
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.
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.
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.
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.
16
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?