It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ which has all the details on avoiding the pitfalls you mention.
As to your specific concern, I think you should be able to preallocate a large buffer of objects that you want to share. In other words, the allocations only need to happen infrequently.
The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. It's true that you do need to be allocating memory, but the memory can be allocated by a thread (lock free), and then the slot is claimed and pointer written (still lock free). But there's nothing special about this process -- just allocate some memory, and stick it into the slot.
The ringbuffer is the thing that handles the coordination, enabling you to allocate memory on whatever thread you want.
Is there a reason more complexity is justified? (More complexity might entirely be justified, and I just haven't had that experience.)
the memory can be allocated by a thread (lock free)
If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory.
The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals.
Yes, because in many cases when I see lock free data structures and get excited about it, what is really presented is a data structure that is putting all of the locking pressure on the memory allocator so that the system as a whole has no net gain.
And this comes down to the crux of the issue, you can write a lock free ring buffer if you stuff all your locking into your memory allocator and I suppose you could claim that the ring buffer is lock free... but the system of ring buffer + memory allocator is then no longer lock free.
That said I'm not saying that this is bad, being lock free doesn't mean good, fast whereas using a lock means slow, bad... it's just that there are a lot of subtle details that make a proper analysis of this much more difficult than it first appears and to the best of my knowledge there is no lock free ring buffer that gives a clear performance benefit.
But as I said, this is such a tricky subject with so many different possible configurations that I would love to see different approaches.
Memory allocation can be avoided by using preallocated buffers for storage. Yeah, that limits the number of maximum elements and could waste memory like hell, but have to live with that and get performance in return.
Race could be eliminated by using separate dirty and free lists (circular buffers, probably implemented as arrays, with the same number of elements as the data storage has). Like declare your storage as a global array, add all of its indexes to the freelist. When adding data to the storage, pop an index from the front of the freelist, fill the given slot of the array, push the index to the back of the dirty list. When processing data, pop an index from the front of the dirty list, process the slot, push the index to the back of the freelist.
If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory.
I'm tempted to say "No need to free it; next time A needs one, let it have that one that you were going to free."
In other words, claiming a slot also claims an already-allocated object.
You're right; this isn't a trivial design consideration. And I'm second-guessing myself as to whether my answer here is wrong. If you see a problem with it, definitely call it out.
(Cheers for the interesting conversation, by the way... Didn't expect it.)
Yeah for sure, at any rate I went over the LMAX Disruptor link you provided and while it doesn't use "locks", it is not a lock-free data structure. The confusion is that their use of the work "lock" means yielding to the operating system, which they don't do, but if a thread is performing a write, then all other threads will spin in a tight loop (which is basically a spin lock) until the write is committed. This is not a lock-free data structure in the typical sense of the word (guarantees at least one thread will make progress) since if the JVM pre-empts the thread currently in the process of writing, then all other writing threads are starved.
You can read more about it here in Section 4.3 on page 6 where they have the following busy waiting:
long expectedSequence = claimedSequence – 1;
while (cursor != expectedSequence) {
// busy spin
}
cursor = claimedSequence
B) Your ring buffer is your allocator: copy (or inplace-construct) your messages direcly in your ring buffer. This work very well for short messages like continuations.
B) each producer thread has a freed-memory lock free queue so that consumers can return memory. The producer can pop the whole queue in one go when it has exhausted its local cache, but pushing an object in the queue can be expensive if the producer was talking with multiple threads. If you want to get fancy you can have NxN spsc queues which works fine with the one thread per core model, but obviously won't scale to ten of thousands of threads.
Your ring buffer is your allocator: copy (or inplace-construct) your messages direcly in your ring buffer.
Then you will need a lock. There's no way to atomically copy data in place without locking.
each producer thread has a freed-memory lock free queue so that consumers can return memory.
Variations of this is how lock free allocators work and the latency penalty for this strategy is very significant, anywhere from 3-5x the latency penalty of a blocking allocator. Certainly lock free allocators have their use cases and if you have a system that needs bandwidth over latency you go for it, but the point is that unless you have hard real time needs for your system, then you're usually better off going for a blocking data structure.
You do not really need a lock. On an spsc queue, the producer will publish the message (by bumping the write pointer of setting the next pointer on the previous message) only after it is done constructing it. In the mpsc case the producer will also need to reserve the space first by atomically increasing the producer shared write pointer.
This is similar to the disruptor model, except that write positions are not pointer sized but arbitrary sized. Similarly to the disruptor model, the mpsc case is technically not lock-free (not even obstruction-free), but writers and the consumer never need to block on an actual lock.
Comments
It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ which has all the details on avoiding the pitfalls you mention.
As to your specific concern, I think you should be able to preallocate a large buffer of objects that you want to share. In other words, the allocations only need to happen infrequently.
The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. It's true that you do need to be allocating memory, but the memory can be allocated by a thread (lock free), and then the slot is claimed and pointer written (still lock free). But there's nothing special about this process -- just allocate some memory, and stick it into the slot.
The ringbuffer is the thing that handles the coordination, enabling you to allocate memory on whatever thread you want.
Is there a reason more complexity is justified? (More complexity might entirely be justified, and I just haven't had that experience.)
If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory.
Yes, because in many cases when I see lock free data structures and get excited about it, what is really presented is a data structure that is putting all of the locking pressure on the memory allocator so that the system as a whole has no net gain.
And this comes down to the crux of the issue, you can write a lock free ring buffer if you stuff all your locking into your memory allocator and I suppose you could claim that the ring buffer is lock free... but the system of ring buffer + memory allocator is then no longer lock free.
That said I'm not saying that this is bad, being lock free doesn't mean good, fast whereas using a lock means slow, bad... it's just that there are a lot of subtle details that make a proper analysis of this much more difficult than it first appears and to the best of my knowledge there is no lock free ring buffer that gives a clear performance benefit.
But as I said, this is such a tricky subject with so many different possible configurations that I would love to see different approaches.
Memory allocation can be avoided by using preallocated buffers for storage. Yeah, that limits the number of maximum elements and could waste memory like hell, but have to live with that and get performance in return. Race could be eliminated by using separate dirty and free lists (circular buffers, probably implemented as arrays, with the same number of elements as the data storage has). Like declare your storage as a global array, add all of its indexes to the freelist. When adding data to the storage, pop an index from the front of the freelist, fill the given slot of the array, push the index to the back of the dirty list. When processing data, pop an index from the front of the dirty list, process the slot, push the index to the back of the freelist.
I'm tempted to say "No need to free it; next time A needs one, let it have that one that you were going to free."
In other words, claiming a slot also claims an already-allocated object.
You're right; this isn't a trivial design consideration. And I'm second-guessing myself as to whether my answer here is wrong. If you see a problem with it, definitely call it out.
(Cheers for the interesting conversation, by the way... Didn't expect it.)
Yeah for sure, at any rate I went over the LMAX Disruptor link you provided and while it doesn't use "locks", it is not a lock-free data structure. The confusion is that their use of the work "lock" means yielding to the operating system, which they don't do, but if a thread is performing a write, then all other threads will spin in a tight loop (which is basically a spin lock) until the write is committed. This is not a lock-free data structure in the typical sense of the word (guarantees at least one thread will make progress) since if the JVM pre-empts the thread currently in the process of writing, then all other writing threads are starved.
You can read more about it here in Section 4.3 on page 6 where they have the following busy waiting:
https://lmax-exchange.github.io/disruptor/files/Disruptor-1....Some other details of the blocking are here:
http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-...
You have many options, here are two:
B) Your ring buffer is your allocator: copy (or inplace-construct) your messages direcly in your ring buffer. This work very well for short messages like continuations.
B) each producer thread has a freed-memory lock free queue so that consumers can return memory. The producer can pop the whole queue in one go when it has exhausted its local cache, but pushing an object in the queue can be expensive if the producer was talking with multiple threads. If you want to get fancy you can have NxN spsc queues which works fine with the one thread per core model, but obviously won't scale to ten of thousands of threads.
Then you will need a lock. There's no way to atomically copy data in place without locking.
Variations of this is how lock free allocators work and the latency penalty for this strategy is very significant, anywhere from 3-5x the latency penalty of a blocking allocator. Certainly lock free allocators have their use cases and if you have a system that needs bandwidth over latency you go for it, but the point is that unless you have hard real time needs for your system, then you're usually better off going for a blocking data structure.
You do not really need a lock. On an spsc queue, the producer will publish the message (by bumping the write pointer of setting the next pointer on the previous message) only after it is done constructing it. In the mpsc case the producer will also need to reserve the space first by atomically increasing the producer shared write pointer.
This is similar to the disruptor model, except that write positions are not pointer sized but arbitrary sized. Similarly to the disruptor model, the mpsc case is technically not lock-free (not even obstruction-free), but writers and the consumer never need to block on an actual lock.