5 ms·

Why is the _Atomic qualifier on the actual data array here required? Shouldn't it be part of the atomic qualifiers on the index read/write operations to make su

Why is the _Atomic qualifier on the actual data array here required? Shouldn't it be part of the atomic qualifiers on the index read/write operations to make sure those are not reordered and the memory is actually valid? Given array elements could be > 64bit in size I guess it won't be to make the access actually atomic? Is it another hint to the compiler not to reorder things? Not super familiar with those C qualifiers, and therefore curious. And is the acquire ordering on push/pop and release on commit the right thing?

arinlen 4y ago
> Why is the _Atomic qualifier on the actual data array here required? Also, my C skills are lacking but I recall that C's support for atomic data structures is a higher-level abstraction that could very well use locks under the hood. C's support for atomics even provides a atomic_is_lock_free function which is used to check whether a data structure is lock-free or not. https://en.cppreference.com/w/c/atomic/atomic_is_lock_free https://en.cppreference.com/w/c/atomic/atomic_is_lock_free Using ints with C's atomics does not ensure the atomic data type is lock-free. C even provides a macro to verify whether the primitive data type has lock-free access or not. https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_consts https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_cons... Using C's atomic in this context to claim lock-free status sounds a lot like hand-waving over the problem domain to pretend locks aren't there. It's a cool read, but the underlying claim doesn't really hold.
- slimsag 4y ago
  I've heard rumors that on modern processors, "lock free" doesn't even make a ton of sense. It's actually contention that is costly, when there is no contention atomic data structures are virtually free as I understand it. Don't know if there is data to back that up, though.
  - flaviut 4y ago
    Modern processors use something like https://en.m.wikipedia.org/wiki/MOESI_protocol https://en.m.wikipedia.org/wiki/MOESI_protocol to share data between processors. So basically, writing a shared line is expensive. Atomic reads are free, as are atomic writes to a cache line that no one else is using.
    - tialaramex 4y ago
      It's never truly free but on some CPUs (e.g. x86 and x86-64) you're always paying for it anyway and so you might as well use it.
  - Asooka 4y ago
    You can think of a lock-free data structure as a data structure with an embedded wait-free lock implemented with atomics. This has several advantages: - Less memory - a pthread mutex is around 40 bytes, compared to 4 bytes for this queue. - No waiting - in some cases you don't want to wait, just do a try-push and if you can't, do some other work with the thread and then try again. Eventually you will have to either wait or discard the data, depending on your situation. - No syscalls - mutexes weren't always as light as they are now, older implementations would always do a syscall and context switch to take or release a mutex.
    - gpderetta 4y ago
      > wait-free lock That's an oxymoron.
    - tialaramex 4y ago
      > Less memory - a pthread mutex is around 40 bytes, compared to 4 bytes for this queue. This sort of thing is pretty ugly, and is one place where "portable" C and C++ really betrays the value of the language. Chances are many (often all) your uses are Linux, and so a futex is all you actually needed, which costs 4 bytes like this structure. But to be portable you can't ask for a futex, and it's deliberately not made easy to try to directly call into Linux system calls for futex since you'll probably get it wrong and then blame everybody else. So you ask for pthread_mutex and now it's ten times bigger and you're regretting your life choices.
      - arinlen 4y ago
        > So you ask for pthread_mutex and now it's ten times bigger and you're regretting your life choices. It's 36 bytes bigger. Unless you're for some reason doing embedded development with a resource constrained system running a UNIX-like OS, that is not a concern that registers anywhere. And you get standard code that runs anywhere. Arguing about 36 bytes per critical section makes no sense. You waste far more than that by handling a string.
        gpderetta 4y ago
  - grogers 4y ago
    Lock/wait freedom is not about performance but about progress guarantees. Often lock free data structures are not faster than locked ones. Reducing contention applies to both locked and lock-free structures.
JonChesterfield 4y ago
The data array / buffer doesn't need to be atomic. Once the atomic load/store on indices has justified access to the data you're good. C puts atomic on the type, not the operation. That's conservative and occasionally very annoying (can't use normal stores in some parts of the program and atomic in others, thanks to aliasing rules) but doesn't hurt this particular application.
dahart 4y ago
There’s a paragraph in the article about this. “The single producer and single consumer didn’t require locks nor atomic accesses to the storage array since the queue guaranteed that accesses at the specified index were not concurrent. However, this is not the case with multiple-consumers. Consumers race when popping. The loser’s access might occur after the winner’s commit, making its access concurrent with the producer. Both producer and consumers must account for this.”
- Matthias247 4y ago
  Yes, I read that one, but still didn't understand what will change in code generation due to it. If it's about the read on the consumer side not being reordered after the commit, then I assumed the release on the atomic will take care of it. Maybe I'll throw it into godbolt later on to figure out.

arinlen 4y ago

> Why is the _Atomic qualifier on the actual data array here required? Also, my C skills are lacking but I recall that C's support for atomic data structures is a higher-level abstraction that could very well use locks under the hood. C's support for atomics even provides a atomic_is_lock_free function which is used to check whether a data structure is lock-free or not. https://en.cppreference.com/w/c/atomic/atomic_is_lock_free https://en.cppreference.com/w/c/atomic/atomic_is_lock_free Using ints with C's atomics does not ensure the atomic data type is lock-free. C even provides a macro to verify whether the primitive data type has lock-free access or not. https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_consts https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_cons... Using C's atomic in this context to claim lock-free status sounds a lot like hand-waving over the problem domain to pretend locks aren't there. It's a cool read, but the underlying claim doesn't really hold.

slimsag 4y ago
I've heard rumors that on modern processors, "lock free" doesn't even make a ton of sense. It's actually contention that is costly, when there is no contention atomic data structures are virtually free as I understand it. Don't know if there is data to back that up, though.
- flaviut 4y ago
  Modern processors use something like https://en.m.wikipedia.org/wiki/MOESI_protocol https://en.m.wikipedia.org/wiki/MOESI_protocol to share data between processors. So basically, writing a shared line is expensive. Atomic reads are free, as are atomic writes to a cache line that no one else is using.
  - tialaramex 4y ago
    It's never truly free but on some CPUs (e.g. x86 and x86-64) you're always paying for it anyway and so you might as well use it.
- Asooka 4y ago
  You can think of a lock-free data structure as a data structure with an embedded wait-free lock implemented with atomics. This has several advantages: - Less memory - a pthread mutex is around 40 bytes, compared to 4 bytes for this queue. - No waiting - in some cases you don't want to wait, just do a try-push and if you can't, do some other work with the thread and then try again. Eventually you will have to either wait or discard the data, depending on your situation. - No syscalls - mutexes weren't always as light as they are now, older implementations would always do a syscall and context switch to take or release a mutex.
  - gpderetta 4y ago
    > wait-free lock That's an oxymoron.
  - tialaramex 4y ago
    > Less memory - a pthread mutex is around 40 bytes, compared to 4 bytes for this queue. This sort of thing is pretty ugly, and is one place where "portable" C and C++ really betrays the value of the language. Chances are many (often all) your uses are Linux, and so a futex is all you actually needed, which costs 4 bytes like this structure. But to be portable you can't ask for a futex, and it's deliberately not made easy to try to directly call into Linux system calls for futex since you'll probably get it wrong and then blame everybody else. So you ask for pthread_mutex and now it's ten times bigger and you're regretting your life choices.
    - arinlen 4y ago
      > So you ask for pthread_mutex and now it's ten times bigger and you're regretting your life choices. It's 36 bytes bigger. Unless you're for some reason doing embedded development with a resource constrained system running a UNIX-like OS, that is not a concern that registers anywhere. And you get standard code that runs anywhere. Arguing about 36 bytes per critical section makes no sense. You waste far more than that by handling a string.
      - gpderetta 4y ago
- grogers 4y ago
  Lock/wait freedom is not about performance but about progress guarantees. Often lock free data structures are not faster than locked ones. Reducing contention applies to both locked and lock-free structures.

JonChesterfield 4y ago

The data array / buffer doesn't need to be atomic. Once the atomic load/store on indices has justified access to the data you're good. C puts atomic on the type, not the operation. That's conservative and occasionally very annoying (can't use normal stores in some parts of the program and atomic in others, thanks to aliasing rules) but doesn't hurt this particular application.

dahart 4y ago

There’s a paragraph in the article about this. “The single producer and single consumer didn’t require locks nor atomic accesses to the storage array since the queue guaranteed that accesses at the specified index were not concurrent. However, this is not the case with multiple-consumers. Consumers race when popping. The loser’s access might occur after the winner’s commit, making its access concurrent with the producer. Both producer and consumers must account for this.”

Matthias247 4y ago
Yes, I read that one, but still didn't understand what will change in code generation due to it. If it's about the read on the consumer side not being reordered after the commit, then I assumed the release on the atomic will take care of it. Maybe I'll throw it into godbolt later on to figure out.