Hacker News Reader

Comment by singron | Hacker News Reader

I love this. This is great to read if you are trying to use TLA+ for something.

In a different vein, another thing TLA+ isn't great at is modeling atomics and in particular weak-memory semantics or anything that's not sequentially consistent. If you translate your algorithm to pcal, it will run as if it was sequentially consistent. If you need to model non-sequential-consistency, then that needs to be spelled out with explicit logic to TLA+, which is probably too complicated and error-prone to do by hand. The C/C++/Rust memory models permit a lot of wacky stuff. I imagine you need to add read caches and writeback buffers for each variable with cache-flushing instructions at appropriate points, but maybe there is a more elegant way to do it.

If you use rust, miri and loom both have analyzers that can check some non-sequentially-consistent behavior (and loom doesn't actually implement sequential-consistency at all).

View on HN

For C++ GenMC is probably the state of the art for this: https://plv.mpi-sws.org/genmc/

There's also RustMC for Rust.

I think the style guides I’ve seen only permit acquire/release memory orders for locks, and relaxed for simple counters. Anything more complicated including lockless hashtables or RCU, using seq_cst is required by the style guide.

The restriction is a good thing because there are very few humans who can reason about acquire/release semantics in situations other than locks.

Which style guides? That makes no sense to me because 1) if you're writing a lock-free algorithm/data structure you presumably both know what you're doing and care a lot about performance, 2) many lock-free algorithms don't even require any seq_cst operations (or equivalent fences), and 3) weak memory orderings can be essential to getting acceptable performance in critical paths.

I would also note that aside from formal methods, LLMs are absolutely not trustworthy but the top frontier models can reason to some degree about weak memory orderings, and can at least find concurrency bugs which can be later confirmed by human expert review (preferably after eliminating false positives via adversarial LLM review of the findings).

The well-known C++ Core Guidelines say this:

> Atomic variables can be used simply and safely, as long as you are using the sequentially consistent memory model (memory_order_seq_cst), which is the default.

That’s from https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

A lot of companies’ in-house guidelines then say you are allowed to use acquire/release if you are implementing a lock, relaxed if are implementing a counter.

This IMO probably reflects most companies’ distrust in their own developers to develop lock free data structures.

I disagree with this advice, and consider it outdated.

Arguably, seq_cst is helpful for informal reasoning, because it's not hard to imagine all permutations and interleavings. But in my opinion, nobody should be doing lock-free programming based on informal reasoning. Algorithms should be considered incorrect unless they've been rigorously validated, ideally with formal methods or at least model checking.

Very few lock-free algorithms require sequential consistency. There are exceptions, such as Chase-Lev queues, but they are rare.

The added confidence that seq_cst gives you if the algorithm hasn't been properly validated is IMHO worthless.

I disagree as well. It’s more of a clutch to make inexperienced people complain that their lockless algorithm is slow and find a reputable third-party library instead.

Agree, look at how many incorrect concurrent algorithms have been published over the years, where seq_cst is assumed. It's easy enough to mess up concurrency without any weak memory orderings. There are only a few people I know of who I would trust to informally reason about weak memory orderings in nontrival algorithms (Dmitry Vyukov, for one).

Yeah, the last time I had to check anything regarding memory orderings, I wrote a custom analyzer for that problem. It's...not easy. The state space is enormous too, so even with compiled code I had to take some shortcuts and prove parts of the problem by hand.

This is true, and it falls into the "possible but not ergonomic" category for modeling systems like this in TLA+. Concurrent programs reading & writing to shared variables can be reordered at two levels: the compiler, and then the CPU. Specifying this in TLA+ is possible but difficult, and your conventional TLA+ specification will assume things happen in a linear order within each thread, and are interleaved arbitrarily between threads. In other words by default PlusCal works like there is both a barrier and memory fence between each action. Even with strong memory semantics like x86-TSO, specifying something like the action of the store buffer (where a core writes a value and can read the updated value but its write is not yet visible to other cores) requires actually writing your own tiny implementation of x86-TSO; there isn't one already defined as a library you can easily use.

I've been thinking lately about how to make this more ergonomic, as I've been getting into lock-free algorithms and would like to be able to specify them nicely in TLA+.

Reply on news.ycombinator.com