What could Go wrong with a mutex • Hacker News Board

Re: What could Go wrong with a mutex

#41

Post by ndr » Wed, Nov 03, 2021, 12:01 PM UTC

gpderetta wrote: post #36

ndr wrote: post #32

Earlier quoted context omitted.

Isn't that a live lock? Can anything really shield you from that? It seems nothing can, in the same way nothing can really shield you from an infinite loop.

> Isn't that a live lock? If they are blocked it is not a live lock. If they are spinning in a try_read then it would be a live lock. > Can anything really shield you from that? It seems nothing can, in the same way nothing can really shield you from an infinite loop Non-Turing Complete languages can be proven to terminate(they do exist, see total functional programming). Similarly I think there are programming parad…

> If they are blocked it is not a live lock.

If they're blocked then we are no longer talking about non-blocking, did we go full circle?

> Non-Turing Complete languages can be proven to terminate [...]

Of course, and while I appreciate the point for sake of argument, these languages have very limited applicability.

> Similarly I think there are programming paradigms that might be truly deadlock free but my recollection is fuzzy.

Look up Pony, from an earlier message in this thread :)

Re: What could Go wrong with a mutex

#42

Post by gpderetta » Wed, Nov 03, 2021, 12:18 PM UTC

ndr wrote: post #41

gpderetta wrote: post #36

Earlier quoted context omitted.

> Isn't that a live lock? If they are blocked it is not a live lock. If they are spinning in a try_read then it would be a live lock. > Can anything really shield you from that? It seems nothing can, in the same way nothing can really shield you from an infinite loop Non-Turing Complete languages can be proven to terminate(they do exist, see total functional programming). Similarly I think there are programming parad…

> If they are blocked it is not a live lock. If they're blocked then we are no longer talking about non-blocking, did we go full circle? > Non-Turing Complete languages can be proven to terminate [...] Of course, and while I appreciate the point for sake of argument, these languages have very limited applicability. > Similarly I think there are programming paradigms that might be truly deadlock free but my recollecti…

> Look up Pony, from an earlier message in this thread :)

after 5 minutes of googling, pony has non-blocking reads and uses promises with continuations. The CPS transform of a program that can deadlock will still deadlock. Just because you reify your wait queue does not mean you are free from deadlocks. They are just much harder to debug as you do not have a clean stackframe and process identity.

edit: to be more clear, to say that a program that uses promises and continuations can't deadlock is equivalent to saying that a C program running on linux can't deadlock because the kernel is still able to make progress. From the kernel point of view the C program looks exactly like the pony program, with continuations suspended on wait queues.

Re: What could Go wrong with a mutex

#43

Post by iainmerrick » Wed, Nov 03, 2021, 12:21 PM UTC

masklinn wrote: post #17

hnlmorg wrote: post #15

Earlier quoted context omitted.

I think deferring unlocks should be more openly described as an anti-pattern. I do appreciate the convenience of defer generally speaking but it has two problems that specifically hinder effective use of mutexes: 1. it allows you to roll up additional code that doesn't need to be inside the mutex, thus keeping other threads waiting longer for an unlock 2. Benchmarks have shown[1][2] that using defer is actually more…

> So defer directly causes complications here that, in my opinion, outweighs any benefits you get with regards to readability. The primary advantage of defer is not readability, it’s safety, in the presence of both panics and code evolving.

Does Go still run defers at function exit rather than scope exit? Changing that would be a big improvement, although I guess they’d have to use a different keyword to avoid breaking compatibility.

Re: What could Go wrong with a mutex

#44

Post by ndr » Wed, Nov 03, 2021, 12:44 PM UTC

gpderetta wrote: post #42

ndr wrote: post #41

Earlier quoted context omitted.

> If they are blocked it is not a live lock. If they're blocked then we are no longer talking about non-blocking, did we go full circle? > Non-Turing Complete languages can be proven to terminate [...] Of course, and while I appreciate the point for sake of argument, these languages have very limited applicability. > Similarly I think there are programming paradigms that might be truly deadlock free but my recollecti…

> Look up Pony, from an earlier message in this thread :) after 5 minutes of googling, pony has non-blocking reads and uses promises with continuations. The CPS transform of a program that can deadlock will still deadlock. Just because you reify your wait queue does not mean you are free from deadlocks. They are just much harder to debug as you do not have a clean stackframe and process identity. edit: to be more cle…

My understanding is that it doesn't use promises with continuations, what source suggests it does? The message queues are unbounded, do not block on writes, and only one can actor can read. There's no blocking nor waiting, so I'm not sure you can get into two actors waiting on each other at all. Infinite loops, sort-of live locks, and OOM are all still possible.

More in this presentation[0] (slides here [1]) and this [2].

[0] https://www.infoq.com/presentations/pony-type-system/

[1] https://qconlondon.com/london-2017/system/files/presentation...

[2] https://www.infoq.com/podcasts/sylvan-clebsch-pony-formal-ve...

Re: What could Go wrong with a mutex

#45

Post by gpderetta » Wed, Nov 03, 2021, 12:52 PM UTC

ndr wrote: post #44

gpderetta wrote: post #42

Earlier quoted context omitted.

> Look up Pony, from an earlier message in this thread :) after 5 minutes of googling, pony has non-blocking reads and uses promises with continuations. The CPS transform of a program that can deadlock will still deadlock. Just because you reify your wait queue does not mean you are free from deadlocks. They are just much harder to debug as you do not have a clean stackframe and process identity. edit: to be more cle…

My understanding is that it doesn't use promises with continuations, what source suggests it does? The message queues are unbounded, do not block on writes, and only one can actor can read. There's no blocking nor waiting, so I'm not sure you can get into two actors waiting on each other at all. Infinite loops, sort-of live locks, and OOM are all still possible. More in this presentation[0] (slides here [1]) and this…

From a cursory look and from my understanding of [1] and [2], promise next takes the continuation to apply to the future (elsewhere known as 'then').

[1] https://kevinhoffman.medium.com/modeling-non-blocking-intera...

[2] https://stdlib.ponylang.io/promises-Promise/

Re: What could Go wrong with a mutex

#46

Post by _ph_ » Wed, Nov 03, 2021, 1:01 PM UTC

hnlmorg wrote: post #39

_ph_ wrote: post #31

Earlier quoted context omitted.

There are several patterns possible which resolve this problem, your third example actually shows that, as it uses a function which only does the container access in a separate function which uses defer - this guarantees that no other code is executed while the lock is held. Alternatively, you could use an anonymous function inside your function which immediately gets called and performs the locking, lookup and defer…

That doesn't address the overhead of defer though (point 2) which can be a problem if your locks are in a well travelled path. One might argue that if you have a hot path that depends on mutexes then perhaps you need to restructure your code to avoid sharing data (and thus the need for a mutex). And that point would be valid, generally speaking. But there's always that one edge case where it is unavoidable (or even s…

Yes, the overhead isn't avoided. This example was thought as the "safe" choice. If you want to be "fast", you have to very carefully analyze what you are doing and then deciding accordingly. If you have code which cannot panic, you have no need to use defer and can unlock directly after the access. And the biggest gain would be avoiding acquiring and releasing the lock in the hot path in the first place.

I think the best practice is to approach a problem from the safe direction as long as performance isn't a total disaster and then try to find the spots which carefully have to be optimized relaxing some of the safeties. But as you are dealing with small hot spots, you can manually analyze the code in question. Similar to the "unsafe" package - if you use it only punctually, the safety loss is usually not a problem.

Re: What could Go wrong with a mutex

#47

Post by ndr » Wed, Nov 03, 2021, 1:01 PM UTC

gpderetta wrote: post #45

ndr wrote: post #44

Earlier quoted context omitted.

My understanding is that it doesn't use promises with continuations, what source suggests it does? The message queues are unbounded, do not block on writes, and only one can actor can read. There's no blocking nor waiting, so I'm not sure you can get into two actors waiting on each other at all. Infinite loops, sort-of live locks, and OOM are all still possible. More in this presentation[0] (slides here [1]) and this…

From a cursory look and from my understanding of [1] and [2], promise next takes the continuation to apply to the future (elsewhere known as 'then'). [1] https://kevinhoffman.medium.com/modeling-non-blocking-intera... [2] https://stdlib.ponylang.io/promises-Promise/

I think that's just normal code, nothing that affects the runtime, that Promise is just a pony actor and abides to the same rules, with the same causal messaging guarantees.

Re: What could Go wrong with a mutex

#48

Post by gpderetta » Wed, Nov 03, 2021, 2:15 PM UTC

ndr wrote: post #47

gpderetta wrote: post #45

Earlier quoted context omitted.

From a cursory look and from my understanding of [1] and [2], promise next takes the continuation to apply to the future (elsewhere known as 'then'). [1] https://kevinhoffman.medium.com/modeling-non-blocking-intera... [2] https://stdlib.ponylang.io/promises-Promise/

I think that's just normal code, nothing that affects the runtime, that Promise is just a pony actor and abides to the same rules, with the same causal messaging guarantees.

Let's say I'm writing a trivial proxy which simply forwards data unchanged between two sockets. This is my pseudocode:

   while true:
       x = read s1
       write s2, x
       y = read s2
       write s1, y

This can deadlock. If for example s1 stops sending data, read(s1) blocks, so the proxy won't forward any data from s2 back to s1, potentially leading to a full pipeline deadlock.

Now, the above can be expressed in purely non blocking fashion as follow :

   letrec f = async_read s1, \x ->
              async_write s2, x \->
              async_read s2, \y ->
              async_write s1, y, f

It still deadlocks exactly as the previous program.

I'm not going to learn pony for the sake of an example, but I'm 97.5% sure you can express the above in Pony, except you do not pass the continuation directly to read and writes but to the returned promise. Sure, the pony runtime will still work and technically the actor could potentially handle other messages, but that's not very useful for the end user that has to deal with a deadlocked pipeline.

So claiming that pony is deadlock-free might be true in a trivial sense, but in practice it is at the very least misleading and potentially dangerous.

edit: it is of course possible to write the program in such a way that it doesn't deadlock, the point is that if pony was truly deadlock free it would reject all programs that can deadlock.

edit2: and of course, if one were to show that the above program is in fact not expressible in pony, it would be a great result and I would want to know about!

Re: What could Go wrong with a mutex

#49

Post by _ph_ » Wed, Nov 03, 2021, 2:27 PM UTC

iainmerrick wrote: post #43

masklinn wrote: post #17

Earlier quoted context omitted.

> So defer directly causes complications here that, in my opinion, outweighs any benefits you get with regards to readability. The primary advantage of defer is not readability, it’s safety, in the presence of both panics and code evolving.

Does Go still run defers at function exit rather than scope exit? Changing that would be a big improvement, although I guess they’d have to use a different keyword to avoid breaking compatibility.

At function exit. You can of course always create an anonymous function to emulate a block like:

  func() {
    defer something()
    ...
  }()

This basically has the same behavior as having a block there, but with the defer being called at the exit of that functions body.

Re: What could Go wrong with a mutex

#50

Post by ndr » Wed, Nov 03, 2021, 3:23 PM UTC

gpderetta wrote: post #48

ndr wrote: post #47

Earlier quoted context omitted.

I think that's just normal code, nothing that affects the runtime, that Promise is just a pony actor and abides to the same rules, with the same causal messaging guarantees.

Let's say I'm writing a trivial proxy which simply forwards data unchanged between two sockets. This is my pseudocode: while true: x = read s1 write s2, x y = read s2 write s1, y This can deadlock. If for example s1 stops sending data, read(s1) blocks, so the proxy won't forward any data from s2 back to s1, potentially leading to a full pipeline deadlock. Now, the above can be expressed in purely non blocking fashion…

I think you might not be able to write that program, there simply is no way to block in Pony (modulo FFI).

The scheduler wakes up actors that have messages (in their local/private queue) to process, all actors can do is to consume their queue and send (wait-free) messages to other actors if they want to.

From your example "read X" would be reading from the actor's queue, so it would not be blocking. If the message queue is empty that actor won't be scheduled, no blocking there.

That "while true" would not be writeable as such, you'd have to have two "behaviors" (in Pony terms, you can imagine it's an event handler) one that process the writing of s1 and one for the writing of s2, and "on read" they'd do the write. There'd be no "while true".

> I'm not going to learn pony for the sake of an example ... > edit2: and of course, if one were to show that the above program is in fact not expressible in pony, it would be a great result and I would want to know about!

I might have misunderstood what your example was supposed to do, but I suspect you'd find it interesting to try it out.