3 ms·
Looks like a good write up, but I'd caution that some of the statements about memory models aren't completely accurate. The terms relaxed, acquire, and release
by atq2119 10mo ago
Looks like a good write up, but I'd caution that some of the statements about memory models aren't completely accurate.
The terms relaxed, acquire, and release refer to how an atomic operation is ordered against other accesses to memory.
Counter to what the article states, a relaxed atomic is still atomic, meaning that it cannot tear and, for RMW atomic, no other access can go between the read and the write. But a relaxed atomic does not order other accesses, which can lead to unintuitive outcomes.
By contrast, once you've observed another thread's release store with an acquire load, you're guaranteed that your subsequent memory accesses "happen after" all of the other thread's accesses from before that release store -- which is what you'd intuitively expect, it's just that in modern systems (which are really highly distributed systems even on a single chip) there's a cost to establishing this kind of guarantee, which is why you can opt out of it with relaxed atomics if you know what you're doing.
- viega 10mo agoYes, I meant to clarify the memory model discussion; I had tried to simplify and did a poor job; I got similar feedback after it was published, and never remembered to get to it. Will try to do it soon, though it's about the worst time for this to have hit, not sure when I'll be able to sit down for it, but will try to get it done in the next day. Hopefully it doesn't wait until next time it gets some views.
- withinboredom 10mo agoI also note that you don't mention the cache-line contention issue when accessing atomics in a multi-threaded context. That's a huge performance issue with lock-free constructs.
- herodoturtle 10mo ago> Co-founder of Crash Override. <3
- Syzygies 10mo agoYes. I was surprised there was no mention of "false sharing". https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing Rather than incrementing each counter by one, dither the counters to reduce cache conflicts? So what if the dequeue becomes a bit fuzzy. Make the queue a bit longer, so everyone survives at least as long as they would have survived before. Or simply use a prime length queue, and change what +1 means, so one's stride is longer than the cache conflict concern. Any stride will generate the full cyclic group, for a prime.
- gpderetta 10mo agoMy understanding is that there is no global ordering anyway: allocation of a node has a total order, but actually writing data to a node can be arbitrarily delayed. At this point might as well use separate queues for each writer. edit: the author claims the algorithm is linearizable, so I'll keep reading the article. edit2: Right, writer acquires ticket, when done attempts to set the done flag on node. Reader acquires ticket, attempts to consume the node. On failure the writer will retry. Even if you have one producer and one consumer, might not you, theoretically, end up in a scenario where the writer never make progress? I guess as technically no node was produced, this is still technically lock-free, but still... ... oh, I should have read it further, the single writer scenario (even in the dynamic case) is special cased! It will still produce the node. Nice, but it seems exceedingly complex.