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

21–30 of 100 posts

Re: Optimizing a lock-free ring buffer

#21

Post by smj-edison »

kristianp wrote: post #7

This is in C++, other languages have different atomic primitives.

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 since Load-Linked/Store-Conditional is pretty cool, but I guess that's limited to ARM anyways, and now they've added extensions for CAS due to speed.

Re: Optimizing a lock-free ring buffer

#22

Post by loeg »

smj-edison wrote: post #21
kristianp wrote: post #7

This is in C++, other languages have different atomic primitives.

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…

LL/SC is still hinted at in the C++11 model with std::atomic::compare_exchange_weak:

https://en.cppreference.com/w/cpp/atomic/atomic/compare_exch...

Re: Optimizing a lock-free ring buffer

#23

Post by secondcoming »

dalvrosa wrote: post #15
JonChesterfield wrote: post #12

It's obviously, trivially broken. Stores the index before storing the value, so the other thread reads nonsense whenever the race goes against it. Also doesn't have fences on the store, has extra branches that shouldn't be there, and is written in really stylistically weird c++. Maybe an llm that likes a different language more, copying a broken implementation off github? Mostly commenting because the initial replies…

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

Re: Optimizing a lock-free ring buffer

#24

Post by superxpro12 »

smj-edison wrote: post #21
kristianp wrote: post #7

This is in C++, other languages have different atomic primitives.

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.

Re: Optimizing a lock-free ring buffer

#27

Post by JonChesterfield »

loeg wrote: post #18
JonChesterfield wrote: post #12

It's obviously, trivially broken. Stores the index before storing the value, so the other thread reads nonsense whenever the race goes against it. Also doesn't have fences on the store, has extra branches that shouldn't be there, and is written in really stylistically weird c++. Maybe an llm that likes a different language more, copying a broken implementation off github? Mostly commenting because the initial replies…

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

Re: Optimizing a lock-free ring buffer

#28

Post by kevincox »

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 other end just read) and this will naturally create a small buffer and run at good speeds.

The hard part is probably that sentinel and ensuring that it can be set/cleared atomically. On Rust you can do `Option` to get a sentinel for any type (and it very often doesn't take any space) but I don't think there is an API to atomically set/clear that flag. (Technically I think this is always possible because the sentinel that Option picks will always be small even if the T is very large, but I don't think there is an API for this.)

Re: Optimizing a lock-free ring buffer

#29

Post by JonChesterfield »

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

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