5 ms·
> shared-allocating/ locking/ incrementing/ locking/ decrementing Minor nit: shared allocation, counter incrementing, and counter decrementing can all be done
by KMag 6y ago
> shared-allocating/ locking/ incrementing/ locking/ decrementing
Minor nit: shared allocation, counter incrementing, and counter decrementing can all be done lock-free. They'd still need memory fence operations (and retries in case of contention), and the associated performance hits, but not actual locking.
- fpoling 6y agoLwn.net just published an article where a comment https://lwn.net/Articles/849239/ https://lwn.net/Articles/849239/ described how there were no really lock-free data structures on modern CPUs: A couple of decades of writing concurrent algorithms has taught me that scalability is really defined by the frequency the concurrent algorithm accesses/updates shared data, not whether the software algorithm is considered "lockless" or not.
- KMag 6y agoNobody is claiming that memory fences are free or that livelock isn't possible with lockfree algorithms. (Except in corner cases, such as carefully constructed RISC-V code where the architectural specification does guarantee progress in short tight ll-sc loops with proper instruction alignment.) The LWN comment mentions spinlocks to improve worst-case performance of some lockfree algorithms, but that criticism doesn't apply to atomic increments / decrements on multi-issue CPUs. The latency of contended memory operations would completely hide the overhead of the add/subtract and make the atomic add/subtract equivalent to a spinlock. (Also, the LWN comment doesn't apply where the algorithm can be written within guaranteed progress corner-cases of the architecture, where applicable.)