Hacker News Reader

Comment by Animats | Hacker News Reader

"What locks it" can include "owned by different threads". That's a lock at a higher level, really.

"Lock free" data structures are tied very closely to the data being locked, and depend heavily on certain CPU operations being atomic. This is more of an issue with ARM than with x86, because ARM needs more fence instructions. Really, "lock free" programming is just locking critical sections with lower level hardware primitives.

The opposite extreme is POSIX locks. Locks are the OS's problem, and nothing in the code says what's covered by the lock. That was once standard practice and is now recognized as being bad.

View on HN

> Really, "lock free" programming is just locking critical sections with lower level hardware primitives.

I have to disagree, as the more interesting lock free algorithms use atomic operations that can fail. Yes, a compare-and-swap is like having a critical section on modifying that particular address. But a compare-and-swap can fail if what is currently there is unexpected. The result of that failure generally means redoing a bunch of work, rather than just trying again. Interesting lock free algorithms tend to have the structure:

1. Read some data.

2. Perform computations on that data.

3. Trying to commit the result of that computation. If someone else committed data to the same location after you read it in step 1, go back to step 1.

That's less like a "critical section," and more like a transaction. For lock free algorithms that just rely on atomic operations that cannot fail (such as an atomic increment), then yes, those are just like having a lower-level critical section. (And, on some architectures, that's exactly what they are.)

compare-and-swap

Compare and swap is interesting. It's a tiny transaction. It can even operate across networks - FireWire had hardware compare and swap support. Compare and swap with retry may have to wait and retry, which is effectively waiting for someone else to stop using a resource you want. So it's a form of a critical section lock.

Optimistic locking is still locking. The low level compare-and-swap operation still uses CPU cacheline-level locking. https://en.wikipedia.org/wiki/MESI_protocol

What's important is that you no longer have a critical section, where mutual exclusion is enforced. The only piece of code that has mutual exclusion is an attempt to commit the transaction. The kind of thinking required to implement such algorithms is quite different than when you can rely on mutual exclusion.

(Also, not all architecture use hardware mechanisms to enforce actual mutual exclusion. For example, Power does not, as it uses load-linked, stored-conditional: https://en.wikipedia.org/wiki/Load-link/store-conditional. On Power, even things like atomic increments are implemented with LL/SC. Architectures basically have to decide: will they implement atomics through some kind of a lock mechanism, or some kind of LL/SC mechanism.)

You still have a critical section; the cacheline is in an exclusive mode during the change. LL/SC operates on top the cache sharing protocols, just like everything else. Your wikipedia link even refers to that: "Typically, CPUs track the load-linked address at a cache-line or other granularity [...]". MESI and friends are that mechanism.

What lock-free means in this case is that an OS level thread freezing doesn't prevent global progress. That's true on the abstraction level of typical programming, but grandparent is very much correct:

> Really, "lock free" programming is just locking critical sections with lower level hardware primitives.

> Really, "lock free" programming is just locking critical sections with lower level hardware primitives

Can fence instructions really be seen as locking mechanism? While a lock generally is bound to some data, memory fences are bound to relationships between data or a piece of code. I don't know if Rust or any other language can help you with that.

Isn't the actual bad practice to expose locks at all? If the locking is done implicitly in API calls, one doesn't need to ask "What locks it".

The fences aren't a locking mechanism, at least not on their own. The lower (hardware) level locks are the steps in the cache coherency protocols (potentially including explicit cache line locking signals) that allow an execution unit to, eg, perform a correct atomic compare-exchange operation on a 32/64/128-bit piece of data.

See also, eg, the LOCK prefix on x86 instructions.

(disclaimer: I only have approximate knowledge of anything, I'm not an expert)

Agreed. But! Not all architectures implement atomic operations by locking the bus, as x86 does. The Power architecture uses load-linked, stored-conditional (https://en.wikipedia.org/wiki/Load-link/store-conditional) where when you load a value, you can say "pay attention to who modifies this value," and when you go to store the value, you can say "only actually store this value if no one else modified it."

Reply on news.ycombinator.com