I spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.
The problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm).
Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
There are many scenarios where you’re subject to preemption and CAS is empirically faster and completely viable. This including hardware with over 200 hardware threads of concurrency. In that same realm of hardware, atomic increments can be as fast or faster.
Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.
Yeah, we've been bitten by horrible degradation as soon as anything else is running on the system next to the main application, like a cron job or unknowingly running CI on a VM where the VM's vCPUs are subject to preemption.
As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread.
Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.
Comments
I spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.
The problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm).
Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
There are many scenarios where you’re subject to preemption and CAS is empirically faster and completely viable. This including hardware with over 200 hardware threads of concurrency. In that same realm of hardware, atomic increments can be as fast or faster.
Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.
Yeah, we've been bitten by horrible degradation as soon as anything else is running on the system next to the main application, like a cron job or unknowingly running CI on a VM where the VM's vCPUs are subject to preemption.
As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread.
Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.