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

91–100 of 100 posts

Re: Optimizing a lock-free ring buffer

#91

Post by pjdesno »

jeffbee wrote: post #90
pjdesno wrote: post #89

Earlier quoted context omitted.

It's not a "bogus and misleading baseline". It's precisely the way we teach people how to build thread-safe systems. And we teach them to do it that way because we've learned from experience that letting them code up their own custom synchronization primitives leads to immense woe and suffering. (and it's not slow because of the C++ mutex implementation, either - I tested a C/pthreads version, and it was the same spe…

The GNU libstdc++ STL mutex is nothing but pthread_lock, so that's not a surprise. I really don't understand what you are saying about not using custom primitives. The whole article is "YOLO your own synchronization" and it fails to grapple with the subtleties. An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of…

I don't actually get your point.

You dismissed the standard lock-guarded data structure as a "bogus comparison", despite it being the way every programmer is taught to write multi-threaded code.

Now the more you write, the more you seem to make the case that (a) normal programmers shouldn't be writing code like this, and (b) there are significant speedups possible if someone who knows what they're doing *does* write a highly tuned lock-free library.

Re: Optimizing a lock-free ring buffer

#92

Post by reitzensteinm »

jeffbee wrote: post #90
pjdesno wrote: post #89

Earlier quoted context omitted.

It's not a "bogus and misleading baseline". It's precisely the way we teach people how to build thread-safe systems. And we teach them to do it that way because we've learned from experience that letting them code up their own custom synchronization primitives leads to immense woe and suffering. (and it's not slow because of the C++ mutex implementation, either - I tested a C/pthreads version, and it was the same spe…

The GNU libstdc++ STL mutex is nothing but pthread_lock, so that's not a surprise. I really don't understand what you are saying about not using custom primitives. The whole article is "YOLO your own synchronization" and it fails to grapple with the subtleties. An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of…

Could you macroexpand your claims a little here?

"An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of head_ and tail_."

The Acquire / Release in version 4 looks right to me, but I'd like to know if I'm missing something.

Also, while your linked paper is good background for what the C++11 memory model is intended to abstract over, it's almost entirely its own thing with a mountain of complexity.

Somebody else in this comment section brought atomics knowledge to an Acquire/Release fight and it didn't go well.

As a starting introduction I'd probably recommend this:

https://www.amazon.com.au/C-Concurrency-Action-Practical-Mul...

Re: Optimizing a lock-free ring buffer

#93

Post by jeffbee »

pjdesno wrote: post #91
jeffbee wrote: post #90

Earlier quoted context omitted.

The GNU libstdc++ STL mutex is nothing but pthread_lock, so that's not a surprise. I really don't understand what you are saying about not using custom primitives. The whole article is "YOLO your own synchronization" and it fails to grapple with the subtleties. An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of…

I don't actually get your point. You dismissed the standard lock-guarded data structure as a "bogus comparison", despite it being the way every programmer is taught to write multi-threaded code. Now the more you write, the more you seem to make the case that (a) normal programmers shouldn't be writing code like this, and (b) there are significant speedups possible if someone who knows what they're doing *does* write…

The easy speedup is to use 2 mutexes, one that protects head and tail_cached, and the other that protects tail and head_cached, and align so they don't interfere. In other words, take the RingBufferV5 from the article and define the class like this:

  std::array buffer_;
  alignas(64) absl::Mutex hmu_;
  std::size_t head_{0};
  std::size_t tail_cached_{0};

  alignas(64) absl::Mutex tmu_;
  std::size_t tail_{0};
  std::size_t head_cached_{0};
Then change the code to forget the atomics and just use the locks. On my system this is more than ten times faster than the baseline naïve thread-safe RingBufferV2. That's what I mean about using a bogus baseline.

Re: Optimizing a lock-free ring buffer

#94

Post by foobar10000 »

dalvrosa wrote: post #31
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

Indeed that's true. That extra constraint enables further optimization It's mentioned in the post, but worth reiterating!

Nice!

Should be able to push it more if

* we limit data shared to an atomic-writable size and have a sentinel - less mucking around with cached indexes - just spinning on (buffer_[rpos_]!=sentinel) (atomic style with proper sematics, etc..).

* buffer size is compile-time - then mod becomes compile-time (and if a power of 2 - just a bitmask) - and so we can just use a 64-bit uint to just count increments, not position. No branch to wrap the index to 0.

Also, I think there's a chunk of false sharing if the reader is 2 or 3 ahead of the writer - so performance will be best if reader and writer are cachline apart - but will slow down if they are sharing the same cacheline (and buffer_[12] and buffer_[13] very well may if the payload is small). Several solutions to this - disruptor patter or use a cycle from group theory - i.e. buffer[_wpos%9] for example (9 needs to be computed based on cache line size and size of payload).

I've seen these be able to pushed to about clockspeed/3 for uint64 payload writes on modern AMD chips on same CCD.

Re: Optimizing a lock-free ring buffer

#95

Post by loeg »

reitzensteinm wrote: post #92
jeffbee wrote: post #90

Earlier quoted context omitted.

The GNU libstdc++ STL mutex is nothing but pthread_lock, so that's not a surprise. I really don't understand what you are saying about not using custom primitives. The whole article is "YOLO your own synchronization" and it fails to grapple with the subtleties. An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of…

Could you macroexpand your claims a little here? "An example of the unaddressed complexity: use of acquire-release semantics for head_ and tail_ atomics imposes no ordering whatsoever between observations of head_ and tail_." The Acquire / Release in version 4 looks right to me, but I'd like to know if I'm missing something. Also, while your linked paper is good background for what the C++11 memory model is intended…

I think he's complaining that because the head_ and tail_ loads in push/pop are relaxed, rather than also being acquire, they can be reordered relative to the acquire tail_ and head_ loads respectively. I don't believe this impacts the correctness of the logic, but I could be missing something.

Re: Optimizing a lock-free ring buffer

#98

Post by j_seigh »

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…

My impression was LL/SC had forward progress issues due to the difficulties of preventing false sharing of the locked memory reservation region. Updates into that region would keep invalidating the lock.

I had a version of atomic* reference counting that used LL/SC on a ppc mac mini along side x86 versions using cmpxchg16b. Code used to be sourceforge before it went to the dark side.

An early posting of the idea before I got around to implementing it. https://groups.google.com/g/comp.programming.threads/c/HZqn5...

* Std::shared_ptr and Rust ARC aren't actually atomic. You have to own a reference to do a copy. The are what POSIX calls thread-safe. With atomic reference counting, if you copy a reference, you either get a valid reference or null. Like Java references.

Re: Optimizing a lock-free ring buffer

#99

Post by kev946 »

loeg wrote: post #97
kev946 wrote: post #96

Is it okay for push and pop to have noexcept when copy assignment of T could throw?

I'm not sure C++ provides a more satisfying answer here than "don't use this with a T that throws in copy." (And also, why would you want that?)

I was just wondering, because the functions are noexcept in OP's code

Re: Optimizing a lock-free ring buffer

#100

Post by JonChesterfield »

loeg wrote: post #37
JonChesterfield wrote: post #27

Earlier quoted context omitted.

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 pe…

This was _really_ surprising to me. What's the point of marking individual stores if it affects everything, not just that address. But yeah, what I can find online agrees that C++ has done this. Thanks!
Post reply on HN