3 ms·

It's lock-free because it uses ordered loads and stores, which is also how you implement locks. I find the semantic distinction unconvincing. The post is really

by jeffbee 7mo ago

It's lock-free because it uses ordered loads and stores, which is also how you implement locks. I find the semantic distinction unconvincing. The post is really about how slow the default STL mutex implementation is.

loeg 7mo ago
There are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.
- jeffbee 7mo ago
  That only explains the last stage. In order to steelman the mutex alternative, everything before "further optimization" should have used 2 critical sections. That would give a realistic baseline.
  - loeg 7mo ago
    I don’t understand what you’re getting at.
pjdesno 7mo ago
That's what "lock-free" means. You still need to use the hardware mechanisms provided for atomicity. The whole point of lock-free data structures and algorithms is that sometimes you can do better by using these atomic operations inside your own code, rather than using a one-size-fits-all mutex based on those same atomic operations. (Note that I say "sometimes". Too many people believe that lock-free structures are always faster; as always, your mileage may vary. In this case it's a huge win, to the point where I would bet it almost always moves the bottleneck to the code actually using the ring buffer.)
- jeffbee 7mo ago
  My point is that the "huge win" is expressed in terms of a bogus and misleading baseline. The article moves immediately from the worst possible lock-based implementation to a pretty bad atomics-based implementation. The final punchline of the article is expressed as a ratio of the bad baseline. To make an honest conclusion, the article should also explore better ways of using the locks.
  - pjdesno 7mo ago
    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 speed as the C++ version)
    - jeffbee 7mo ago
      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 head_ and tail_. The final solution has four atomics that use acquire-release and does not discuss the fact that threads may observe the values of these four things in very surprising order. The issue is so complex that I consider this 50-page academic paper to be the bare minimum survey of the problem that a programmer should thoroughly understand before they even consider using atomics. https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf
      - pjdesno 7mo ago
        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.

by jeffbee 7mo ago

loeg 7mo ago

There are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.

jeffbee 7mo ago
That only explains the last stage. In order to steelman the mutex alternative, everything before "further optimization" should have used 2 critical sections. That would give a realistic baseline.
- loeg 7mo ago
  I don’t understand what you’re getting at.

pjdesno 7mo ago

That's what "lock-free" means. You still need to use the hardware mechanisms provided for atomicity. The whole point of lock-free data structures and algorithms is that sometimes you can do better by using these atomic operations inside your own code, rather than using a one-size-fits-all mutex based on those same atomic operations. (Note that I say "sometimes". Too many people believe that lock-free structures are always faster; as always, your mileage may vary. In this case it's a huge win, to the point where I would bet it almost always moves the bottleneck to the code actually using the ring buffer.)

jeffbee 7mo ago
My point is that the "huge win" is expressed in terms of a bogus and misleading baseline. The article moves immediately from the worst possible lock-based implementation to a pretty bad atomics-based implementation. The final punchline of the article is expressed as a ratio of the bad baseline. To make an honest conclusion, the article should also explore better ways of using the locks.
- pjdesno 7mo ago
  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 speed as the C++ version)
  - jeffbee 7mo ago
    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 head_ and tail_. The final solution has four atomics that use acquire-release and does not discuss the fact that threads may observe the values of these four things in very surprising order. The issue is so complex that I consider this 50-page academic paper to be the bare minimum survey of the problem that a programmer should thoroughly understand before they even consider using atomics. https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf
    - pjdesno 7mo ago
      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.