Comment by Animats | Hacker News Reader

Comment by Animats | Hacker News Reader

Deadlock detection is an interesting problem. As the author points out, Rust will not detect this at compile time, but there are run time analyzers.

It's worth looking at deadlock detection at compile time today. Not just to prevent bugs. Sometimes, on some CPUs, the compiler could potentially turn some mutexes into fence operations and become "lock free".

In Rust, code tends to do a lot of scope-based locking. There's a lot of

    item.lock().unwrap().dosomething()

Now, if the compiler detects that 1) every lock on item is scoped, and 2) everything done inside the lock is short and non-blocking, then that lock could potentially be optimized into fence instructions. Worth thinking about.

There's an analogous case for RefCell items. RefCell is a lot like Mutex, except that you call "borrow" instead of "lock", and if the item is ever "busy", waiting won't help, because your own thread made it busy. If every use is a scoped borrow and there are no inner borrows of the same object within the scope of the outer borrow, that's the good case. Reference counts aren't needed at all.

I think that somewhere in this space lies the solution to the back-reference problem, but I haven't gotten there yet.

Compile-time deadlock prevention very, very quickly begins butting up against Rice's theorem, unless you do something silly like having channels be the only way for threads to communicate. Even then, deadlock conditions are still perfectly possible and very common.

You mean channels like Erlang-style message passing? Where the send is async, and the receiver can pick things out of the queue out-of-order? That is indeed hard to deadlock. It's easy to get other pathological behavior out of them (endlessly-backing-up messages being the one I hit with some frequency) but deadlocks are hard. I think they're doable, but it takes work.

Deadlocking Go-style synchronous channels isn't hard. In practice they're practical to use because they're not particularly hard to not deadlock, either, but I can certainly deadlock them in code if I tried. But I'd be using patterns I'd normally be suspicious of.

(By contrast, conventional mutexes are hard to use without deadlocking, because as soon as you have more than one you have troubles. I use mutexes a lot in Go, but my rule is never take more than one at a time. As soon as you are tempted, do something else. IMHO, the conclusion from the 1990s and early 2000s is wrong... it is not that multithreading in general is impossibly hard, it is that multithreading with multiple mutexes is impossibly hard. If you stay away from that, rather than "impossibly hard" it is merely a challenge, but one humans can rise to meet. I think there's an unjustified residual fear of multithreading to this day that stems from this misunderstanding. And I mean "threads" just as multiple independent simultaneous execution, without regard to any particular technology used to implement them.)

So does “Compile time memory safety”. The way Rust does it is by restricting the valid program to a much narrower set than valid C programs (at least in safe Rust). We may as well find a way to make a programming language that will guarantee zero deadlocks at compile time without being too restrictive, in the same fashion the “aliasing XOR mutable” solved the memory safety challenge. Maybe not, but nobody knows.

That language will need to be built around this limited set of programs though, and is really unlikely to be retrofitted in Rust, like C++ can't realistically add a borrow checker at this point.

> Worth thinking about.

Probably not. This would have to be extremely limited and restrictive in order to avoid false positives (which would be outright miscompilations). The more restrictive an optimisation is, the less valuable it is, and the lower the ROI.

This would be an unlikely-to-achieve-anything optimisation around atomics, which compilers already don’t bother much with because they’re hard to get right and have a low ROI.

I don't see how fences are ever enough for mutual exclusion. Maybe you are thinking of transforming a mutex in a spinlock but that would be catastrophic for realtime programs and generally an optimisation that compilers shouldn't make.

What I assume they’re thinking of is, if the compiler can determine that the lock is scoped and the scoped code only reads from shared memory, then it only needs a sequence point (a read barrier).

I don’t think it’s true because if you don’t “hold” the mutex there’s no guarantee that the mutex-protected data is consistent, unless it’s atomic at which point you’re probably better off optimising to an atomic read. Which compilers are unlikely to bother with either way, because optimising atomic operations would be both risky and low-return.

Right. Even if the mutex is protecting a is a single memory location, holding a mutex is still observable behavior (there is a total orders of all critical sections at the very least), and eliding it is questionable.

Isn't that exactly what SeqCst atomic access gives you in this case? Assuming that the critical sections are restricted to doing read-modify-write of an atomic-sized memory location - which would have to be enforced at compile time or require whole-program analysis.

there is a total order of all critical sections on a specific mutex, but I don't think it is technically part of the same total order of seqcst atomics (although it might in practice). This sort of stuff is extremely subtle.

But again, if you only have an atomic-sized memory location, and you bother writing an optimisation for atomic stuff, why bother with barriers when you could just perform an atomic update?

Also SeqCst is way overkill for a mutex, that is literally the use case for acquire and release semantics, the two barriers were named after the lock operation.

> I don't see how fences are ever enough for mutual exclusion.

I thought the same. Memory fences alone can't guarantee mutual exclusion.

BTW, Mutex::get_mut exists and safely gives access without locking, when you can prove to the borrow checker that you have the only reference to the Mutex.

An example of one of the little reasons I expect large-scale Rust code to be faster than C++ in the long term. There's a lot of little things like this that the Rust can do but C++ can't that can add up to a lot over the entire program. But it's really hard to see these in benchmarks because benchmarks are almost never code complicated enough to show these differences, and then even if someone writes one, in the resulting benchmark competition someone may come in and hand-optimize the C++ code for this. But C++ can't scale that sort of attention, so the benchmarked performance won't be anything that real code can obtain.

Reply on news.ycombinator.com