Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing a lock-free ring buffer

david.alvarezrosa.com

Post reply on HN
Print view View original

41–50 of 100 posts

Re: Optimizing a lock-free ring buffer

#41

Post by dalvrosa »

erickpintor wrote: post #38
erickpintor wrote: post #32

Great post! Would you mind expanding on the correctness guarantees enforced by the atomic semantics used? Are they ensuring two threads can't push to the same slot nor pop the same value from the ring? These type of atomic coordination usually comes from CAS or atomic increment calls, which I'm not seeing, thus I'm interested in hearing your take on it.

I see you replied on comment below with: > note that there are only one consumer and one producer That clarify things as you don't need multi-thread coordination on reads or writes if assuming single producer and single consumer.

Exactly, that's right

Re: Optimizing a lock-free ring buffer

#42

Post by ramon156 »

Something to add to this; if you're focussing on these low-level optimizations, make sure the device this code runs on is actually tuned.

A lot of people focus on the code and then assume the device in question is only there to run it. There's so much you can tweak. I don't always measure it, but last time I saw at least a 20% improvement in Network throughput just by tweaking a few things on the machine.

Re: Optimizing a lock-free ring buffer

#43

Post by loeg »

kevincox wrote: post #28

Random idea: If you have a known sentinel value for empty could you avoid the reader needing to read the writer's index? Just try to read, if it is empty the queue is empty, otherwise take the item and put an empty value there. Similarly for writing you can check the value, if it isn't empty the queue is full. It seems that in this case as you get contention the faster end will slow down (as it is consuming what the…

Yeah, or you could put a generation number in each slot adjacent to T and a read will only be valid if the slot's generation number == the last one observed + 1, for example. But ultimately the reader and writer still need to coordinate here, so we're just shifting the coordination cache line from the writer's index to the slot.

Re: Optimizing a lock-free ring buffer

#45

Post by loeg »

erickpintor wrote: post #32

Great post! Would you mind expanding on the correctness guarantees enforced by the atomic semantics used? Are they ensuring two threads can't push to the same slot nor pop the same value from the ring? These type of atomic coordination usually comes from CAS or atomic increment calls, which I'm not seeing, thus I'm interested in hearing your take on it.

This is a SPSC queue -- there aren't multiple writers to coordinate, nor readers. It simplifies the design.

Re: Optimizing a lock-free ring buffer

#46

Post by dalvrosa »

ramon156 wrote: post #42

Something to add to this; if you're focussing on these low-level optimizations, make sure the device this code runs on is actually tuned. A lot of people focus on the code and then assume the device in question is only there to run it. There's so much you can tweak. I don't always measure it, but last time I saw at least a 20% improvement in Network throughput just by tweaking a few things on the machine.

Agreed. For benchmarking I used this https://github.com/david-alvarez-rosa/CppPlayground/blob/mai...> which relies on GoogleBenchmark and pins producer/consumer threads to dedicated CPU cores

What else could be improved? Would like to learn :)

Maybe using huge pages?

Re: Optimizing a lock-free ring buffer

#47

Post by loeg »

superxpro12 wrote: post #24
smj-edison wrote: post #21

Earlier quoted context omitted.

Don't most people use C++11 atomics now? You have SeqCst, Release, Acquire, and Relaxed (with Consume deprecated due to the difficulty of implementing it). You can do loads, stores, and exchanges with each ordering type. Zig, Rust, and C all use the same orderings. I guess Java has its own memory model since it's been around a lot longer, but most people have standardized around C++'s design. Which is a slight shame…

I've taken an interest in lock-free queues for ultra-low power embedded... think Cortex-m0, or even avr/pic. Things get interesting when you're working with a cpu that lacks the ldrex/strem assembly instructions that makes this all work. I think youre only options at that point are disable/enable interrupts. IF anyone has any insights into this constraint I'd love to hear it.

For ultra low-power embedded, wouldn't a mutex approach work just fine? You're running on a single core anyway.

Re: Optimizing a lock-free ring buffer

#48

Post by blacklion »

JonChesterfield wrote: post #27
loeg wrote: post #18

Earlier quoted context omitted.

> It's obviously, trivially broken. Stores the index before storing the value, so the other thread reads nonsense whenever the race goes against it. Are we reading the same code? The stores are clearly after value accesses. > Also doesn't have fences on the store ?? It uses acquire/release semantics seemingly correctly. Explicit fences are not required.

Push: buffer_[head] = value; head_.store(next_head, std::memory_order_release); return true; There's no relationship between the two written variables. Stores to the two are independent and can be reordered. The aq/rel applies to the index, not to the unrelated non-atomic buffer located near the index.

write with release semantic cannot be reordered with any other writes, dependent or not.

Relaxed atomic writes can be reordered in any way.

Re: Optimizing a lock-free ring buffer

#49

Post by loeg »

secondcoming wrote: post #23
dalvrosa wrote: post #15

Earlier quoted context omitted.

Sorry, but that's not actually true. There are no data races, the atomics prevent that (note that there are only one consumer and one producer) Regarding the style, it follows the "almost always auto" idea from Herb Sutter

If you enforce that the buffer size is a power of 2 you just use a mask to do the if (next_head == buffer.size()) next_head = 0; part

This was, in fact, mentioned in the article.

Re: Optimizing a lock-free ring buffer

#50

Post by kevincox »

loeg wrote: post #43
kevincox wrote: post #28

Random idea: If you have a known sentinel value for empty could you avoid the reader needing to read the writer's index? Just try to read, if it is empty the queue is empty, otherwise take the item and put an empty value there. Similarly for writing you can check the value, if it isn't empty the queue is full. It seems that in this case as you get contention the faster end will slow down (as it is consuming what the…

Yeah, or you could put a generation number in each slot adjacent to T and a read will only be valid if the slot's generation number == the last one observed + 1, for example. But ultimately the reader and writer still need to coordinate here, so we're just shifting the coordination cache line from the writer's index to the slot.

I think the key difference is that they only need to coordinate when the reader and writer are close together. If that slows one end down they naturally spread apart. So you don't lose throughput, only a little latency in the contested case.
Post reply on HN