3 ms·
The notion of "lock-free" is fundamentally misleading. It trips up everybody who hopes "lock-free" will be a magic bullet freeing them from resource contention
by ncmncm 5y ago
The notion of "lock-free" is fundamentally misleading.
It trips up everybody who hopes "lock-free" will be a magic bullet freeing them from resource contention bottlenecks.
When you have explicit locks, aka mutexes (condition variables, semaphores, what-have-you), the interaction between your threads is visible on the surface. Replacing that with "lock-free" interaction, you have essentially the same set of operations as when taking a mutex. On the up side, overhead cost may be lower. On the down side, mistakes show up as subtly wrong results instead of deadlocks. And, you get less control, so when you have a problem, it is at best harder to see why, and harder to fix.
Because the lock-free operations involve similar hardware bus interactions under the covers, they cannot fix contention problems. You have no choice but to fix contention problems at a higher, architectural design level, by reducing actual contention. Having solved the problems there, the extra cost of explicit mutex operations often does not matter, and the extra control you get may be worth any extra cost.
What is lock-free good for, then? Lock-free components reduce overhead when there is no contention. Given any actual contention, performance is abandoned in favor of correctness. So, if you have mutexes and performance is good, moving to lock-free operations might make performance a little better. If performance is bad, mutexes and lock-free operations will be about equally as bad.
- duped 5y agoUnfortunately I think this comment does is muddy the waters even more. All "lock free" means is that one process(+) may not cause any other process to block during execution. "Contention" is not very meaningful to a lock-free algorithm, since lock-free algorithms typically do not permit shared data access semantics. Rather they describe how data is sent between processes, which is why a lock-free solution looks very different than something behind mutexes. But to the heart of your point, I do wish people spent more time understanding that lock-free vs lock-ful is a distinction in semantics and doesn't imply anything about performance. There are subtle trade offs. (+) I'm using "process" with a lot of hand waving, assume it means whatever your atom of parallelism is
- ncmncm 5y agoYou are confusing two fundamentally different topics. Anywhere there is no possibility of contention for access to a resource, "lock-free" is trivially meaningless.
- Kranar 5y agoDon't see anything more misleading about lock free than about anything else involving parallelism. Lock freedom has to do with guarantees about scheduling, you can be lock free and still have contention but a lock free algorithm is guaranteed to make progress within a bounded amount of time. A blocking algorithm is not guaranteed to make any kind of progress within a bounded amount of time. If you're working on a real time system, and I don't mean the colloquial meaning of that word, but rather a system that must guarantee that a side effect is produced no later than a given period of time, then you must use a lock free algorithm, there is no alternative. Avionics, DSP, high frequency trading, these are all domains where lock free algorithms are necessary. Making a fast lock free algorithm is great and generally the goal of any kind of parallelism is performance, but fast is not an unambiguous term, it can mean low latency or high bandwidth and it's very unlikely to write an algorithm that is both. Lock free algorithms are great when you need low latency and guaranteed throughput. If you don't need that then it's possible to trade those properties for much higher bandwidth and use blocking algorithms.
- ncmncm 5y agoIf you are counting on lock-free operations to guarantee you will meet your real-time scheduling requirements, you have chosen to fail, right out of the gate. Guaranteeing met deadlines takes engineering. Using lock-free operations is not a substitute for engineering. There is no such substitute. Also: All this has nothing to do with parallelism. Parallelism is about things happening at the same time. Locking or not locking, and contention, are about concurrency, which is about synchronization and serialization, a different topic.
- Kranar 5y agoIf you are using a mutex to guarantee real-time scheduling requirements, you have failed. Furthermore if you think a discussion about benchmarking an algorithm on a 24-core SMP system involving atomic reads, writes and shared caches has nothing to do with parallelism then let's just agree to disagree with one another and I wish you all the best in your programming endeavors. People can decide for themselves what credibility they wish to lend to your argument given your perspective on this matter.
- oshiar53-0 5y ago(Commenting here since the other thread is going nowhere) To clarify, the main property of a non-blocking algorithm is that it's exclusively composed of simpler, smaller ("atomic") operations that demonstrate time-bound/progress-making guarantees, in turn making the bigger algorithm generally easier to reason about (Note "generally"). The consequence of this argument is twofold: 1. It's entirely possible to make a blocking algorithm provide the same guarantees as a non-blocking algorithm, as long as the underlying operations (blocking or otherwise) are proven to be correct. Blocking algorithm tend to throw other complex systems into the mix (e.g. the scheduler), and all of the dependencies and their usages have to be correct (w.r.t. whatever property we desire) to show that the final blocking algorithm is also correct. For instance, it can be argued that the priority inversion problem stems from the lack of scheduler's correctness, or alternatively, the incorrect use of the scheduler. However, in the absense of such problems, there are effectively no disadvantages on blocking algorithms on this respect. 2. If it turns out any atomic operations below the non-blocking algorithm do not meet the expected guarantees, then the non-blocking algorithm itself also becomes unsafe. I think the OP clearly demonstrates this problem--the CPU atomic instructions are but some kind of hardware "locks" (either a LOCK# pin on older processors or some complex cache coherency protocol, but this is an implementation detail) on their own that can sometimes fail to meet the programmer's expectations, leading to surprising results. In short, the fine line between blocking algorithms and nonblocking algorithms can be drawn by whichever smaller operations or components we assume to be correct.