4 ms·

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C1

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C11 and C++11 memory model and atomic operations. I had some thoughts, which I'm offering in hopes of clarifying my understanding, and possibly helping to improve your software in the process. I don't see any correctness problems in your code, but I do see what look like several opportunities for optimization. Though please take these with a slight grain of salt, as I am still learning the C11 atomics. Your aring_give() ends with a release barrier and your aring_take() begins with an acquire barrier. That makes sense to me, as a way of ensuring the sequencing of the reads/writes to aring->rb and to item. However I don't see why aring_give() needs to begin with an acquire and aring_take() needs to end with a release. I think both of these could be changed to memory_order_relaxed with no change in correctness. But I think we can go a step further actually. Your atomic_fetch_add_explicit() and atomic_fetch_sub_explicit() operations operate on a shared aring->items member. Both the reader and writer write to this variable, which requires expensive locked operations and which will degrade under contention. I don't think this is actually necessary. Instead you could eliminate aring->items completely and simply compute it based on aring->head and aring->tail. Only the writer writes to head and only the reader writes to tail, so you could use just atomic_load_explicit()/atomic_store_explicit() with memory_order_relaxed on these variables to read and write them. Then calculate the number of items present by comparing them. This could make the overall queue significantly more efficient. I'd be curious to hear your thoughts on this.

temac 11y ago
Not the author, but anyway; I'm not sure you can release on one variable and acquire on an other while having ordering guarantee between the two. Anyway, I agree that having both acq and rel on both reader on writer side seems weird. I guess you can come with a solution with only one rel for the writer and only one acq for the reader. UPDATE: I'm stupid, actually not possible if you don't want to overflow.
- haberman 11y ago
  Interesting, it was my impression that the release/acquire are not specific to a memory location. They are just barriers, aren't they? But as I said I'm just learning.
  - temac 11y ago
    They are specific. See 5 in 5.1.2.4 Multi-threaded executions and data races in n1570. In term of real hardware it translates well in MESI/MESI-like protocol on cache lines on ooo cores, without much more constraints (of course some arch are sufficiently weak to still require special instructions, but on the other hand x86 don't need anything for acq/rel). If the different cores never touch the same cache line, they don't need to do interact at all even when both execute unrelated acq/rel atomics.
    - haberman 11y ago
      Interesting. I bought C++ Concurrency in Action today and am learning all these details of the memory model. You mention of caches makes me realize that a single-reader single-writer queue can probably also be optimized by putting the head pointer and the tail pointer on different cache lines. The reader and writer can cache the other's value on their own page, and only reload it when the queue otherwise looks full or empty, respectively. This should allow the reader and writer to act without needing to synchronize cache lines for many operations.
      - djcapelis 11y ago
        I think that works on some architectures but would not be guaranteed behavior. In theory on a system with no memory ordering constraints, the pointers could update before the cache lines for the underlying ring buffer. Which means that without an acquire barrier at the beginning of aring_take, which without an item count, would require writes to the shared head/tail pointers to sync anyway, you can't ensure the the data written to the ring buffer is visible to the thread, even though your pointers would indicate there's data there and so you may load either torn or completely different data into the consumer thread. Which means that if your memory barriers are operating correctly, they're just causing two cache lines to sync for the metadata instead of one, if the pointers are split across two lines. Whereas with an item count, only one line ever has to sync, even if the pointers are split across two, since the pointers aren't shared between threads. In practice, the compiler might not be smart enough to realize this and might be enforcing order for all side effects before the barriers though, even if the other thread doesn't read them. So maybe this isn't a good approach.
djcapelis 11y ago
As you might have guessed, after a few conversations today (not very good ones, for the most part, I was tempted to give up the Internet.) I've been thinking about this code quite a bit in the last 12 hours. I think you're right that there might be an opportunities for improvement. I admit that once the performance hit about 140 cycles per item, I mostly shrugged and called it a day. I felt a lot more concerned about its safety across various architectures than bringing that cycle count down to the absolute minimum. But I also did my benchmarking on x86_64, which has surprisingly strong memory guarantees by default, and so the difference here may be larger on other architectures. Thanks for looking it over! I definitely am interested and hope to grab some time to try benchmark some tweaks (and test for correctness) on a bunch of different architectures. Unfortunately I don't have all the state I'd need sitting at the top of my brain to revise this code at the moment, or even know whether your proposed changes are safe, since I find I can't write atomics code safely unless I devote at least an afternoon to the process of analyzing the problem's safety. I remember there was a reason I chose using a shared item count instead of having the pointers be shared, I think mostly just to minimize the shared state to one thing, but it may not be the fastest choice. If you want to give trying some changes a shot, I'd love to hear what you find! Email is in my profile. :)

temac 11y ago

Not the author, but anyway; I'm not sure you can release on one variable and acquire on an other while having ordering guarantee between the two. Anyway, I agree that having both acq and rel on both reader on writer side seems weird. I guess you can come with a solution with only one rel for the writer and only one acq for the reader. UPDATE: I'm stupid, actually not possible if you don't want to overflow.

haberman 11y ago
Interesting, it was my impression that the release/acquire are not specific to a memory location. They are just barriers, aren't they? But as I said I'm just learning.
- temac 11y ago
  They are specific. See 5 in 5.1.2.4 Multi-threaded executions and data races in n1570. In term of real hardware it translates well in MESI/MESI-like protocol on cache lines on ooo cores, without much more constraints (of course some arch are sufficiently weak to still require special instructions, but on the other hand x86 don't need anything for acq/rel). If the different cores never touch the same cache line, they don't need to do interact at all even when both execute unrelated acq/rel atomics.
  - haberman 11y ago
    Interesting. I bought C++ Concurrency in Action today and am learning all these details of the memory model. You mention of caches makes me realize that a single-reader single-writer queue can probably also be optimized by putting the head pointer and the tail pointer on different cache lines. The reader and writer can cache the other's value on their own page, and only reload it when the queue otherwise looks full or empty, respectively. This should allow the reader and writer to act without needing to synchronize cache lines for many operations.
    - djcapelis 11y ago
      I think that works on some architectures but would not be guaranteed behavior. In theory on a system with no memory ordering constraints, the pointers could update before the cache lines for the underlying ring buffer. Which means that without an acquire barrier at the beginning of aring_take, which without an item count, would require writes to the shared head/tail pointers to sync anyway, you can't ensure the the data written to the ring buffer is visible to the thread, even though your pointers would indicate there's data there and so you may load either torn or completely different data into the consumer thread. Which means that if your memory barriers are operating correctly, they're just causing two cache lines to sync for the metadata instead of one, if the pointers are split across two lines. Whereas with an item count, only one line ever has to sync, even if the pointers are split across two, since the pointers aren't shared between threads. In practice, the compiler might not be smart enough to realize this and might be enforcing order for all side effects before the barriers though, even if the other thread doesn't read them. So maybe this isn't a good approach.

djcapelis 11y ago

As you might have guessed, after a few conversations today (not very good ones, for the most part, I was tempted to give up the Internet.) I've been thinking about this code quite a bit in the last 12 hours. I think you're right that there might be an opportunities for improvement. I admit that once the performance hit about 140 cycles per item, I mostly shrugged and called it a day. I felt a lot more concerned about its safety across various architectures than bringing that cycle count down to the absolute minimum. But I also did my benchmarking on x86_64, which has surprisingly strong memory guarantees by default, and so the difference here may be larger on other architectures. Thanks for looking it over! I definitely am interested and hope to grab some time to try benchmark some tweaks (and test for correctness) on a bunch of different architectures. Unfortunately I don't have all the state I'd need sitting at the top of my brain to revise this code at the moment, or even know whether your proposed changes are safe, since I find I can't write atomics code safely unless I devote at least an afternoon to the process of analyzing the problem's safety. I remember there was a reason I chose using a shared item count instead of having the pointers be shared, I think mostly just to minimize the shared state to one thing, but it may not be the fastest choice. If you want to give trying some changes a shot, I'd love to hear what you find! Email is in my profile. :)