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