3 ms·

”Lock free” has a very precise meaning in computer science, and it’s this: ”given some number of threads of execution, an algorithm is lock free if in some fini

by OskarS 5y ago

”Lock free” has a very precise meaning in computer science, and it’s this: ”given some number of threads of execution, an algorithm is lock free if in some finite number of steps, at least one thread is guaranteed to make forward progress”. When using mutexes, this is not guaranteed under any amount contention: the scheduler is perfectly free to preempt a thread holding a lock, which means no threads make progress. However, if you use a CAS loop (like this code does) to update some value (i.e. a while loop that repeatedly tries to execute a compare-and-swap), that loop will only fail to make progress if some other thread DID make progress. This means that such an algorithm is in fact lock-free: if thread X didn’t progress, it is necessarily because some other thread did. In addition, a scheduler preempting a thread at any point will not stop other threads making progress. Whether an algorithm is lock free or not is not a matter of opinion, it is a mathematical statement. The fact that it annoys you is… weird.

feffe 5y ago
Yes, I'm probably wrong on the semantics of lock free. I should read up on that. My point was that maybe you can gain a factor of 2 by using atomic ops in a "lockless" fashion compared to mutexes but it still scales extremely poorly compared to what you could do if the hardware had real async mechanisms that did not rely on cache coherency. The cache line that is subjected to an atomic operation will be evicted from all other CPUs cache lines, back and forth. A simple example is just letting all CPUs in a multi core CPU doing an atomic add at a memory address. The scaling will be exactly 1 with the number of available cores. I realize this is very of topic wrt to this cool article an implementation in zig. It's just that this problem can't really be solved in an efficient manner with todays hardware.
- OskarS 5y ago
  Yeah, it's a true point that "lock-free" != "fast". If contention is very low, the simple version using mutexes often perform better.

by OskarS 5y ago

feffe 5y ago

Yes, I'm probably wrong on the semantics of lock free. I should read up on that. My point was that maybe you can gain a factor of 2 by using atomic ops in a "lockless" fashion compared to mutexes but it still scales extremely poorly compared to what you could do if the hardware had real async mechanisms that did not rely on cache coherency. The cache line that is subjected to an atomic operation will be evicted from all other CPUs cache lines, back and forth. A simple example is just letting all CPUs in a multi core CPU doing an atomic add at a memory address. The scaling will be exactly 1 with the number of available cores. I realize this is very of topic wrt to this cool article an implementation in zig. It's just that this problem can't really be solved in an efficient manner with todays hardware.

OskarS 5y ago
Yeah, it's a true point that "lock-free" != "fast". If contention is very low, the simple version using mutexes often perform better.