Hacker News Reader

Comment by PaulDavisThe1st | Hacker News Reader

> The only time locks beat atomics is when you are updating a bunch of things in which case it may be faster to lock once than to update 10 atomic variables.

Locks are mandatory when you're updating data that does not fit into a single atomic type. You cannot use N atomics to create atomic update of a data structure that must be semantically atomic across its N members.

View on HN

Sure, forgot to mention that, but that's only if it must be semantically atomic. That's not always the case.

Technically any algorithm can be implemented in a lock free way and there are n-way CAS constructs that indeed allow updating N memory locations atomically. In practice they are very slow.

You can use RCU to do this, but I'd argue that everything else ends up being more or less a lock by another name (maybe you could do read/write where the read is optimistic, but at least the write side will have some sort of lock). I'm curious what you had in mind?

I misplaced my copy of The Art Of Multiprocessor Programming with the details, but with a simple CAS primitive you can build a general N-CAS algorithm and from that implement any algorithm ina a truly wait free way. It will be slow and won't scale, but will indeed be wait free

Most RCU requires a lock, if only to handle cleaning up the "dead wood" that occurs on every update (write).

Lock-free garbage collection exists and there's quite a body of literature.

Yeah, I've read a lot of it. It all comes with caveats and potential performance issues.

Seemed okay to me with regard to caveats.

Performance issues -> it's lock-free and scales profoundly better than non-lock-free.

You can do this sort of thing with write-ordering a "generation counter" that is updated before and after writing a bunch of other data elements. The problem is that it makes the read slow - you have to use a CAS-style loop even to read anything (you must check that the generation counter has the same value before and after reading the other data). It also adds more memory barriers than a simple lock.

This is the mechanism that I had in mind. It's actually a really good one if you have lots of concurrent reads and few writes because there isn't going to be any cacheline ping pong. With a more traditional read-write lock, even the readers write to the cacheline holding the lock, and that's a shared cacheline so it's going to ping pong around. By contrast, the generation counter is read-only to readers.

But consider: the generation counter effectively acts as a lock that locks out reader threads while the update takes place. It also serves to lock out other writer threads.

So yes, one can call that "lock-free" if one really wants to, but I find it more honest to just admit that it's a custom lock with custom properties.

It's not lock-free, it's wait-free and therein lies the problem. The reader thread(s) are not locked out - they are free to continue running, endlessly looping waiting for the moment when they can consistently read the pseudo-atomic data. That's quite different behavior than if they used a lock, which they would find already held, and they would sleep.

But it is not wait-free, not even non blocking; if I understand your model correctly, a writer blocked in the right moment will prevent a reader to make progress exactly as you described.

Edit: with double buffering I guess it would be lock free, but still not wait free as a fast producer can still starve consumers indefinitely.

/Pedantic

Neither writer nor reader needs to block. The writer does CAS on the generation counter to ensure it is safe against other writer threads. The reader just spins until it reads the same generation counter value before and after the read.

What happens if a writer halts in the middle of a write? How the reader can ever complete a consistent read?

With double buffering the reader can always fall back on the other buffer (hence it is lock-free, assuming somehow that writers always agree on the current write buffer), but then a fast writer can always prevent a slow reader from reading a consistent timestamp in a row which means it is not wait free.

If I'm understanding it correctly, you are describing a seq lock, which can be implemented with #StoreStore barriers on the writer side and #LoadLoad on the reader side. Topically these are significantly cheaper than the #StoreLoad required for a lock acquisition.

You can produce this behaviour. Look for MCAS, from Cambridge Uni.

It never took off. I think it didn't scale.

Reply on news.ycombinator.com