Hacker News Reader

Comment by sillysaurusx | Hacker News Reader

One neat thing is, you don't actually need a spinlock if you're using a ringbuffer. You can use atomic increment on a counter to claim a slot, then write to that slot.

It can be between two to three orders of magnitude higher throughput. Equally important, lower latency.

(Throughput tends to be a consequence of low latency, but not always.)

I'm not saying this should be the norm, though. You probably don't need this design. But when you do, e.g. processing millions of stock market messages, there's no substitute.

EDIT: I love hearing about the designs and questions, but it was probably a mistake for me not to be explicit. Sorry! The thing I'm referring to is LMAX Disruptor pattern: https://lmax-exchange.github.io/disruptor/

I learned about it in 2011-ish, and it deeply changed my perspective on high speed designs.

View on HN

I spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.

The problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm).

Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.

There are many scenarios where you’re subject to preemption and CAS is empirically faster and completely viable. This including hardware with over 200 hardware threads of concurrency. In that same realm of hardware, atomic increments can be as fast or faster.

Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.

Yeah, we've been bitten by horrible degradation as soon as anything else is running on the system next to the main application, like a cron job or unknowingly running CI on a VM where the VM's vCPUs are subject to preemption.

As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread.

Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.

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.

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.

> 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

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

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.

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.

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

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

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.

Do you have an example of this in action? I'd be interested to know what steps are taken to avoid false sharing of cache lines in the ring buffer itself.

You pad each counter so that it's on a separate cache line. https://lmax-exchange.github.io/disruptor/ goes into detail on the false sharing problem.

(A+ and full marks on recognizing that that's a central problem.)

I think reitzensteinm was referring to the actual data inside the ring. There is a false sharing problem there particularly for the MPMC type ring buffer like disruptor. The solution is to pad each data slot in addition to the read and write indices. I do this in my MPMC ring buffer queue: https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...

You can align and pad each ring buffer slot to the cache line size. Example https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...

Ringbuffers and thread-per-core architecture is great for low latency transaction processing systems, like exchanges and trading systems.

Sometimes you don't have time to do things perfectly and might use a spinlock when initializing some cache on first use... Only light contention, not great not, not terrible :).

Last time I looked at Disruptor it still required a WaitStrategy, one of which was a Spinlock

Not for the single producer multi consumer case, which is approximately the most useful case. (For me, anyway.)

If you have multiple producers and consumers though, then yes. But it's very cool to me that you can do without the spinlock in any useful case.

Are you sure? It's been a while since I ported it to C++ and so maybe the code has changed, but doesn't the producer have to wait for all consumers to consume, and don't consumers have to wait for the producer to produce?

The BlockingWaitStrategy was mutex based IIRC.

The original whitepaper goes into detail about where the lock isn't necessary: https://lmax-exchange.github.io/disruptor/files/Disruptor-1....

I did this in 2011 or so, so it's been a decade. But my feelings are, "I'm quite certain that if I were to re-read the paper from start to finish, I'd end up feeling convinced of the position I just tried to convince you of."

If that's not true, then I'm simply a fool, and will happily concede. :) But! For now, I have to go look at a house that we're thinking of renting.

Long live the LMAX?

All hail!

It was truly a cool design, for its time.

I feel strongly like it's one of those designs you should study just to even be aware that such a thing exists. Otherwise I probably would've been like "Oh, a spinlock! Yes, always."

(It's the disruptor pattern: https://lmax-exchange.github.io/disruptor/)

Reply on news.ycombinator.com