3 ms·
Sorry, I think I was confusing LLVM's 'monotonic' with 'atomic'. The docs (https://llvm.org/docs/LangRef.html#ordering https://llvm.org/docs/LangRef.html#orderi
by mjb 7y ago
Sorry, I think I was confusing LLVM's 'monotonic' with 'atomic'. The docs (https://llvm.org/docs/LangRef.html#ordering https://llvm.org/docs/LangRef.html#ordering) say:
> In addition to the guarantees of unordered, there is a single total order for modifications by monotonic operations on each address. All modification orders must be compatible with the happens-before order. There is no guarantee that the modification orders can be combined to a global total order for the whole program (and this often will not be possible). The read in an atomic read-modify-write operation (cmpxchg and atomicrmw) reads the value in the modification order immediately before the value it writes.
Am I wrong to read that as being equivalent to linearizability, in the case of atomic operations with monotonic ordering? I'm not an expert on compiler internals, so it could be that I'm reading the docs wrong.
If there's a better reference, I'd love to see it.
- mehrdadn 7y agoCould you define explicitly what you mean by linearizability?
- mjb 7y agoThe defininition from Herlihy and Wing (https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf), page 471. More informally, aphyr's definition from https://aphyr.com/posts/313-strong-consistency-models https://aphyr.com/posts/313-strong-consistency-models works well: > each operation appears to take effect atomically at some point between its invocation and completion. Here, operations are on single values (the paper calls them objects). So they are things like "add 1 to x" and not things like "read y and add its value to x".
- mehrdadn 7y agoIf that's what you mean then linearizable can't be the same as monotonic since monotonicity is weaker than sequential consistency, not stronger. If I understand LLVM's docs correctly, the difference between monotonicity and sequential consistency is that the former is for a single address whereas the latter is for all addresses. They would've been more clear on this if they had said "that the modification orders for different addresses can be combined to a global total order for the whole program".