5 ms·

Just proposed one of my projects for inclusion: https://github.com/djcapelis/atomic-ring https://github.com/djcapelis/atomic-ring Lock-free Single Producer, Si

Just proposed one of my projects for inclusion: https://github.com/djcapelis/atomic-ring https://github.com/djcapelis/atomic-ring Lock-free Single Producer, Single Consumer (SPSC) queue. The dependencies include C11 and that's it. No POSIX required, should work on any arch you can find a C11 compiler for.

biokoda 11y ago
If all you're doing is passing pointers from one thread to another, lock free is not a very good choice. Try a trivial spinlock based implementation. It will outperform it easily.
- djcapelis 11y ago
  I strongly doubt you're going to build a faster thread-safe workqueue by adding spinlocks to it, but if you think what I wrote is too slow, feel free to build something faster and show the speed difference in a benchmark. You can use the code in test/ if you'd like. The code I wrote does leave an optimization or two on the table. Apple's lockfree queue in GCD is faster than mine because of batching. It also has a ton more features, including being (IIRC) MPSC.
  - biokoda 11y ago
    Locking is cheap, switching a pointer around is cheap. The only expensive thing is waking up a thread that is waiting on a lock. Spinlocks avoid that problem, which is why they outperform other implementations in terms of throughput (of course inversely proportional to the amount of work you do during a lock). Atomic operations have a fixed cost. Spinlocks only really have a cost when contention is high. When you're just moving a pointer to another place, you're not likely to have that much contention to make atomic operations worth it.
    - djcapelis 11y ago
      I don't think you've got this quite right. Spinlocks require memory barriers. C11 atomics are, among other things, a standardized way to implement cross platform memory barriers without dropping into platform specific assembly.
      - biokoda 11y ago
        The only way to test it out is with code. In my own tests spinlocks turned out to provide the highest throughput. I do not care about the problem enough anymore to go try out your implementation. If you implemented a lock free queue, you should be the one testing it out if it actually is better than a simple spinlock.
        deleted 11y ago
        [deleted]
        djcapelis 11y ago
        My code is on github with test harnesses for doing benchmarking on it. Yours is... some files on a hard drive that likely show something completely different than you think it does. I'm sorry, but I don't have time to comment on this thread anymore.
    - CyberDildonics 11y ago
      You are making a big assumption that threads will be woken up in the first place. Also when it comes to concurrency it is all about scaling, and whatever scales will perform better as there are more cores.
      - biokoda 11y ago
        I never said spinlocks are better in every situation. I'm saying they are better in this situation (SPSC queue).
        CyberDildonics 11y ago
        I didn't say that you said that. Why would spinlocks be better than no locks at all?
    - haberman 11y ago
      > Atomic operations have a fixed cost. Spinlocks only really have a cost when contention is high. You're making it sound like spinlocks don't need atomic operations. I'm pretty sure locking a spinlock requires an atomic operation.
    - temac 11y ago
      If you know what you are doing, the C11/C++11 memory model (or another one with roughly the same features, like the linux kernel memory model) and how a computer actually works, I don't think you will find a single architecture on which an atomic implementation of Lock-free Single Producer, Single Consumer (SPSC) queue will not outperform a spinlock. If you use overkill sequential consistency to do that, you might actually end up slower in some cases. Given the amount of expertise you need to use atomics properly (far more difficult than sticking to critical sections), it might as well be preferable to stick with those at application level unless you really need extreme performance and know the applicable memory model and the corresponding target stack (maybe processor architecture, maybe C11/C++11 memory model if you use it, maybe additional compiler guarantee on that and related stuffs, maybe all at the same time). Not that in the end an acquire / release pattern is so hard to understand, but in my experience programmers already can't even stick to properly using critical sections as in textbooks (not even talking about what happens when the textbook is a piece of shit, like when it presents double-checked locking without any regard to the model needed for it to work properly => people end up writing that in C++ on plain variables...). Really, stick to the (good) textbooks and the simplest patterns if you don't know enough about memory models and how processors and compilers work in 2016... How fast you execute buggy code is not a very interesting property, sequential consistency is expensive in lots of cases, and using weaker atomic is incredibly difficult (each time I think I know enough about weak atomics I found something that explain how various model are subtly weaker than I previously thought, not even talking about the fact that the C11/C++11 model is subtly formally unsound and compilers actually not formally respect it... so much if you try to prove some algorithms)
haberman 11y ago
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.

biokoda 11y ago

If all you're doing is passing pointers from one thread to another, lock free is not a very good choice. Try a trivial spinlock based implementation. It will outperform it easily.

djcapelis 11y ago
I strongly doubt you're going to build a faster thread-safe workqueue by adding spinlocks to it, but if you think what I wrote is too slow, feel free to build something faster and show the speed difference in a benchmark. You can use the code in test/ if you'd like. The code I wrote does leave an optimization or two on the table. Apple's lockfree queue in GCD is faster than mine because of batching. It also has a ton more features, including being (IIRC) MPSC.
- biokoda 11y ago
  Locking is cheap, switching a pointer around is cheap. The only expensive thing is waking up a thread that is waiting on a lock. Spinlocks avoid that problem, which is why they outperform other implementations in terms of throughput (of course inversely proportional to the amount of work you do during a lock). Atomic operations have a fixed cost. Spinlocks only really have a cost when contention is high. When you're just moving a pointer to another place, you're not likely to have that much contention to make atomic operations worth it.
  - djcapelis 11y ago
    I don't think you've got this quite right. Spinlocks require memory barriers. C11 atomics are, among other things, a standardized way to implement cross platform memory barriers without dropping into platform specific assembly.
    - biokoda 11y ago
      The only way to test it out is with code. In my own tests spinlocks turned out to provide the highest throughput. I do not care about the problem enough anymore to go try out your implementation. If you implemented a lock free queue, you should be the one testing it out if it actually is better than a simple spinlock.
      - deleted 11y ago
        [deleted]
      - djcapelis 11y ago
        My code is on github with test harnesses for doing benchmarking on it. Yours is... some files on a hard drive that likely show something completely different than you think it does. I'm sorry, but I don't have time to comment on this thread anymore.
  - CyberDildonics 11y ago
    You are making a big assumption that threads will be woken up in the first place. Also when it comes to concurrency it is all about scaling, and whatever scales will perform better as there are more cores.
    - biokoda 11y ago
      I never said spinlocks are better in every situation. I'm saying they are better in this situation (SPSC queue).
      - CyberDildonics 11y ago
        I didn't say that you said that. Why would spinlocks be better than no locks at all?
  - haberman 11y ago
    > Atomic operations have a fixed cost. Spinlocks only really have a cost when contention is high. You're making it sound like spinlocks don't need atomic operations. I'm pretty sure locking a spinlock requires an atomic operation.
  - temac 11y ago
    If you know what you are doing, the C11/C++11 memory model (or another one with roughly the same features, like the linux kernel memory model) and how a computer actually works, I don't think you will find a single architecture on which an atomic implementation of Lock-free Single Producer, Single Consumer (SPSC) queue will not outperform a spinlock. If you use overkill sequential consistency to do that, you might actually end up slower in some cases. Given the amount of expertise you need to use atomics properly (far more difficult than sticking to critical sections), it might as well be preferable to stick with those at application level unless you really need extreme performance and know the applicable memory model and the corresponding target stack (maybe processor architecture, maybe C11/C++11 memory model if you use it, maybe additional compiler guarantee on that and related stuffs, maybe all at the same time). Not that in the end an acquire / release pattern is so hard to understand, but in my experience programmers already can't even stick to properly using critical sections as in textbooks (not even talking about what happens when the textbook is a piece of shit, like when it presents double-checked locking without any regard to the model needed for it to work properly => people end up writing that in C++ on plain variables...). Really, stick to the (good) textbooks and the simplest patterns if you don't know enough about memory models and how processors and compilers work in 2016... How fast you execute buggy code is not a very interesting property, sequential consistency is expensive in lots of cases, and using weaker atomic is incredibly difficult (each time I think I know enough about weak atomics I found something that explain how various model are subtly weaker than I previously thought, not even talking about the fact that the C11/C++11 model is subtly formally unsound and compilers actually not formally respect it... so much if you try to prove some algorithms)

haberman 11y ago

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.