3 ms·
> 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 i
by 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 agoI'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 agoModern 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 agoIt'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 agoYou 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 agoLock/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.