>Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically.
You can have a single tail with an atomic add, and that's pretty much it. The consumer needs to know, if the data is available, so there has to be a serialization point that with each producer has to wait - effectively a locking mechanism... or the consumer has to check all the producers progress.
It doesn't feel harder. The disruptor part/fame mostly came as it didn't have to allocate new memory.
For example writing a lock-free, max capacity limited, FIFO requires a single long (64bit) in each node and then reading head (1st), then tail one by the producers. Same idea - 64bits are too many to cause an integer overflow when increasing one-by-one.
It has been awhile since the time I wrote lock free stuff (occasional CAS and COW do not count). My current job doesn't really need it.
> You can have a single tail with an atomic add, and that's pretty much it.
That's the primary difference. In a disruptor queue, there's two tails. The first one is used for producers to allocate space in the buffer to write to, and the second one is used to commit it so that it's available to consumers.
It's true that there is a small amount of necessary synchronization across producers, because a producer can't commit its data before a concurrent producer earlier in the buffer does, and can end up spinning on an atomic compare-and-exchange. They can both independently write to their allocated parts of the buffer freely before that point, though, so in practice it's not a contention point.
My point about the sync part w/ the producers, the consumers won't be ready to read from the producers before it's ready. However another option would NOT using a contention point of a shared tail but marking each record as done - need write/write memory fence, so even if the consumers start reading, then can bail out if the write process has not committed.
> the buffer freely before that point, though, so in practice it's not a contention point.
Likely a false sharing between the producers, unless the impl. is careful enough to allocate cache-line sized records.
You can have a single tail with an atomic add, and that's pretty much it. The consumer needs to know, if the data is available, so there has to be a serialization point that with each producer has to wait - effectively a locking mechanism... or the consumer has to check all the producers progress.
It doesn't feel harder. The disruptor part/fame mostly came as it didn't have to allocate new memory.
For example writing a lock-free, max capacity limited, FIFO requires a single long (64bit) in each node and then reading head (1st), then tail one by the producers. Same idea - 64bits are too many to cause an integer overflow when increasing one-by-one.
It has been awhile since the time I wrote lock free stuff (occasional CAS and COW do not count). My current job doesn't really need it.