4 ms·

I have not found this to be the case in my situation but there are so many variations of this that I could be missing something. So from my experiments with th

by Kranar 5y ago

I have not found this to be the case in my situation but there are so many variations of this that I could be missing something. So from my experiments with this, in order to avoid a lock you need to have a ringbuffer of atomic pointers (or atomic values if you're literally just buffering ints or similar). You claim a slot which is a pointer, and then swap out the pointer to the stale value with the pointer to the updated value. But this now requires a multithreaded lock free memory pool. Single threaded this is no problem, but multithreaded this is incredibly difficult without high latency. From my own efforts, while it's possible to implement a lock free ring buffer + suitable memory allocator, you end up with high latency. This high latency can only be justified if the size of the data you're buffering is greater than a certain bound because you get increased bandwidth. For data less than a certain bound, my experience is you get much lower latency and lower bandwidth (but still pretty good bandwidth) by tagging each element with a lock-bit. I suspect we work in the same area (finance), so if you have insight into good lock free memory allocators or resources I'd be very happy to better inform myself.

sillysaurusx 5y ago
It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ 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.)
- Kranar 5y ago
  >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.
  - sillysaurusx 5y ago
    > 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.)
    - 5y ago
senderista 5y ago
There are multiple lock-free allocators now that are suitable for production, such as mimalloc.
- Kranar 5y ago
  I was specific in saying that it's hard to implement a low latency lock free memory allocator. mimalloc has very high latency, almost triple that of jemalloc (which is not lock-free). Every single lock-free allocator I've seen is intended to satisfy high throughput at the expense of incurring high latency, and mimalloc is no different in this respect. At any rate you don't normally use a general purpose memory allocator when you need a high performance data structure, instead opting for a data structure specific allocator/memory pool.

by Kranar 5y ago

sillysaurusx 5y ago

It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ 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.)

Kranar 5y ago
>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.
- sillysaurusx 5y ago
  > 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.)
  - 5y ago

senderista 5y ago

There are multiple lock-free allocators now that are suitable for production, such as mimalloc.

Kranar 5y ago
I was specific in saying that it's hard to implement a low latency lock free memory allocator. mimalloc has very high latency, almost triple that of jemalloc (which is not lock-free). Every single lock-free allocator I've seen is intended to satisfy high throughput at the expense of incurring high latency, and mimalloc is no different in this respect. At any rate you don't normally use a general purpose memory allocator when you need a high performance data structure, instead opting for a data structure specific allocator/memory pool.