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

31–40 of 100 posts

Re: Optimizing a lock-free ring buffer

#31

Post by dalvrosa »

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

Indeed that's true. That extra constraint enables further optimization

It's mentioned in the post, but worth reiterating!

Re: Optimizing a lock-free ring buffer

#32

Post by erickpintor »

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.

Re: Optimizing a lock-free ring buffer

#33

Post by dalvrosa »

JonChesterfield wrote: post #29
secondcoming wrote: post #23

Earlier quoted context omitted.

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

If it's a power of two, you don't need the branch at all. Let the unsigned index wrap.

Interesting, I've never heard about anybody using this. Maybe a bit unreadable? But yeah, should work :)

Re: Optimizing a lock-free ring buffer

#35

Post by dalvrosa »

wat10000 wrote: post #17
jitl wrote: post #10

Earlier quoted context omitted.

Really? Pretty much all atomics i’ve used have load, store of various integer sizes. I wrote a ring buffer in Go that’s very similar to the final design here using similar atomics. https://pkg.go.dev/sync/atomic#Int64

They generally map directly to concepts in the CPU architecture. On many architectures, load/store instructions are already guaranteed to be atomic as long as the address is properly aligned, so atomic load/store is just a load/store. Non-relaxed ordering may emit a variant load/store instruction or a separate barrier instruction. Compare-exchange will usually emit a compare and swap, or load-linked/store-conditional…

100% agree +1

Re: Optimizing a lock-free ring buffer

#37

Post by loeg »

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.

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

No, this is incorrect. If you think there's no relationship, you don't understand "release" semantics.

https://en.cppreference.com/w/cpp/atomic/memory_order.html

> A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store.

Re: Optimizing a lock-free ring buffer

#38

Post by erickpintor »

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.

Re: Optimizing a lock-free ring buffer

#39

Post by dalvrosa »

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.

Thanks! That's not ensured, optimizations are only valid due to the constraints

- One single producer thread

- One single consumer thread

- Fixed buffer capacity

So to answer

> Are they ensuring two threads can't push to the same slot nor pop the same value from the ring?

No need for this usecase :)

Re: Optimizing a lock-free ring buffer

#40

Post by judofyr »

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.

This is just wrong. See https://en.cppreference.com/w/cpp/atomic/memory_order.html. Emphasis mine:

> A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store. All writes in the current thread are visible in other threads that acquire the same atomic variable (see Release-Acquire ordering below) and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic (see Release-Consume ordering below).

Post reply on HN