AtomicCell: Why do you use SeqCst?

[RalfJung]

This recent great blogpost said that AtomicCell doesn't let the user choose the memory ordering, which is fair, but of course I had to immediately check which one it uses ;) . I was very surprised to see it use SeqCst. I would have expected Acq/Rel/AcqRel. This allows reasoning by ownership transfer, which is strong enough for almost everything.

I wouldn't usually care enough to actually submit an issue about this, but now I found this comment:

So AtomicCell is basically Mutex<Cell>, except faster. That's it.

This is not in the documentation as far as I can see, but I agree it makes sense as a principle. The thing is, from all I know it is perfectly legal to implement locks with release-acquire spinlocks, so by this argument, the accesses in AtomicCell should definitely be release-acquire!

The post claims that

let x = AtomicCell::new(false);
let y = AtomicCell::new(false);
let z = AtomicCell::new(0usize);

scope(|s| {
    s.spawn(|| x.store(true));
    s.spawn(|| y.store(true));

    s.spawn(|| {
        while !x.load() {}
        if y.load() { z.fetch_add(1); }
    });

    s.spawn(|| {
        while !y.load() {}
        if x.load() { z.fetch_add(1); }
    });
}).unwrap();

assert!(z.load() > 0);

will pass when using Mutex<Cell>, but (assuming this was tested) I think that is just an accident of the current implementation. Nothing in the C11 memory model requires this to pass when using locks, and you absolutely shouldn't rely on it.

Cc @jeehoonkang @stjepang

[jeehoonkang]

I agree with @RalfJung that:

• Acquire/release will be enough for AtomicCell. I regard the current implementation using seqcst as temporary. I was thinking of sending a PR that lowers the orderings to acquire/release, and then forgot about it :(

• C/C++ doesn't guarantee his example to pass when using Mutex<Cell>. Such a negative reasoning (i.e. either x=true or y=true should happen strictly before the other) usually doesn't hold in C/C++ even using the seqcst ordering. If it's strictly necessary, use seqcst fence.

@RalfJung Thank you so much for digging into Crossbeam, I really appreciate it! <3

Memory orderings of AtomicCell are still an unresolved question and we haven't settled on any guarantees yet. Perhaps this is a good time to decide. But right now, orderings are at least Acq/Rel/AcqRel.

I've been pushing hard for guaranteeing SeqCst orderings because std::atomic<T> in C++ (by default), atomics in Go, atomics in Java, and so on all guarantee SeqCst orderings, which makes sense because stronger guarantees make for fewer bugs. This is an important precedent - I want users coming from other languages to feel at home. And if one wants weaker semantics, there are alternatives to AtomicCell.

In crossbeam-rs/crossbeam-utils#39, my belief was that simply adding a SeqCst fence to optimistic reads would make all operations on AtomicCell behave just as if they were SeqCst. But then @jeehoonkang insisted that wouldn't really work because sequential consistency is broken on some platforms so guaranteeing SeqCst is bogus anyway.

I wonder if we can just put that SeqCst fence into optimistic reads and call it a day. Can we then document "all operations on AtomicCell<T> behave same as if you had an AtomicT and used SeqCst orderings, whatever SeqCst means"? And if that implies memory orderings are broken on some platforms, so be it, then even AtomicUsize is broken just as much as AtomicCell is - and that is not our problem, it's a problem with the memory model, LLVM, and hardware.

All that said, I could be wrong and overlooking something important here. Am I?

Another point against SeqCst was that it's slower than AcqRel. My opinion is: if performance matters so much, don't use AtomicCell. In that case, you probably want to have finer control and be able to specify orderings anyway, which automatically rules AtomicCell out of the question.

And, to reiterate: AtomicCell must primarily be simple. It's not a primitive for us, it's for everyone, especially those who find std::sync::atomic intimidating. There's always Atomic for advanced users and we can come up with new atomic primitives if needed.

Finally, it's worth pointing out that Go developers had a similar, long discussion about SeqCst vs AcqRel for atomics and seem to have settled with SeqCst. If I understood correctly, they didn't want to risk going with the weaker AcqRel semantics: golang/go#5045

Apologies for feeling so anxious about AcqRel - it's just that no other language chose AcqRel as the default ordering for an atomic primitive so I want to be extra sure we're making the right choice here. :)

One more thing: I haven't really decided whether the right mental model for AtomicCell is "Mutex, but faster" or "AtomicT, but easy". I feel torn between those two. Does anyone have a preference?

[RalfJung]

And, to reiterate: AtomicCell must primarily be simple.

I think there is no simple code that is correct with SeqCst but wrong with release-acquire.

all operations on AtomicCell behave same as if you had an AtomicT

I have no idea how to verify if that is the case for your seqlock construction.

Unfortunately SeqCst is not just broken in C11, AFAIK it is also unclear what good reasoning principles for SeqCst might be in a program that also uses relaxed accesses. I presume it should be possible to verify the correctness of Dekker's algorithm, or to verify the example I quoted in the OP.
Basically, I understand release-acquire+relaxed (somewhat), and SeqCst in isolation (very well), but I have no intuition for what happens when you combine them.

Maybe we could ask the libs team what they think in Berlin next week?

But first it would be good to hear from @jeehoonkang if putting a SeqCst fence into the optimistic lock would make AtomicCell<T> behave exactly like AtomicT with SeqCst orderings.