10 ms·

Proposal: Non-cooperative goroutine preemption

150 points by mseepgood 9y ago

stefanchrobot 9y ago
I'd love to see this implemented, especially that I already enjoy this feature a lot in Elixir/Erlang/BEAM.
- dmytrish 9y ago
  The problem with that approach in Go is that BEAM embraces the shared-nothing approach, and the Go runtime is quite promiscuous about sharing mutable data. I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid.
  - mseepgood 9y ago
    Mutating shared state without synchronization is a bug with or without this proposal. Goroutines already run on potentially different OS threads or processors with the current m:n scheduler implementation.
  - jerf 9y ago
    "I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid." They already took a few steps inside of Go to try to ensure that concurrency is quite non-deterministic. Even very simple, naive code like func main() { for i := 0; i < 2; i++ { go func(j int) { fmt.Println("First", j) fmt.Println("Second", j) }(i) } time.Sleep(100*time.Millisecond) } will very frequently produce different results; I just ran that four times and got four different results. This is good, because it tends to bring bugs to the forefront more quickly, rather than having a almost-but-not-quite-deterministic model as has been the case in many other environments. (Yes, I know sleep is not production-quality here, just trying to keep it simpler than several more lines for a proper waitgroup usage.) I doubt there's a lot of code written at the Go level that would explode if you suddenly ran it with a pre-emptive runtime that isn't already exploding. As the proposal discusses, there's a lot of issues down at the runtime level, but at the layer of abstraction presented by the language itself I wouldn't expect a lot of problems. Non-zero, and even then, it would still be things that are technically already bugs. And Go code is already running concurrently all the time in the real world. I'm not even sure how I'd construct an example that runs correctly in the current runtime but fails with true pre-emption.
    - notheguyouthink 9y ago
      > will very frequently produce different results; I just ran that four times and got four different results. This is good, because it tends to bring bugs to the forefront more quickly, rather than having a almost-but-not-quite-deterministic model as has been the case in many other environments. I concur, they do this with maps too. It led to discovering a bug in our system where order was being implicitly depended on via a JSON Object -> Map conversion. Go randomized the map key order when iterated over, revealing the logic bug.
    - lloeki 9y ago
      > They already took a few steps inside of Go to try to ensure that concurrency is quite non-deterministic I would not be surprised as they are already proactively ensuring things like map ordering are randomised so that people just can't rely on some deterministic ordering: run the example code here[0] multiple times and it produces not just a seemingly random result (as would be for a typical hash table) but a truly different result for each run. [0]: https://nathanleclaire.com/blog/2014/04/27/a-surprising-feature-of-golang-that-colored-me-impressed/ https://nathanleclaire.com/blog/2014/04/27/a-surprising-feat...
      - kardianos 9y ago
        Yes, map iteration is explicitly randomized for just this thing.
  - dilap 9y ago
    Go code is not shared-state safe in the way that, say, Python generators are. And with the -race compile flag, it does a pretty good job of detecting violations so you can fix them. So I think Go code should be unaffected by this change.
  - masklinn 9y ago
    > I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid. It already is exactly that (Go already does m:n scheduling, so while your routine currently can't get interrupted between two function calls, two goroutines running on different OS threads can manipulate the same mutable state without synchronisation and make a mess of it), it's just that you don't necessarily notice.
nostalgeek 9y ago
interesting, is the current situation one of the reason Go debugging experience is so poor? Delve debugger is constantly crashing for me, making step debugging extremely hard, especially when debugging tests. If there is one thing that is inferior to Java and C# with Go it's definitely the debugging experience.
- arghwhat 9y ago
  Not at all. Non-cooperative goroutines would make it much harder to implement a debugger. Delve crashing is just related to Delve being buggy. Single-stepping is done at the instruction level, and the task of a Go debugger mostly relates to mapping instructions to source code, and understanding the runtime. You can debug Go with gdb, but without Go runtime comprehension, all you will see is a bunch of worker threads executing Go runtime code, rather than the individual goroutines of your process.
- anonacct37 9y ago
  I've actually never run into a problem debugging go binaries with gdb. Which is weird because everyone's always told me it doesn't work. I'm sure there are edge cases but over the last 5 years or so my experience has been pretty good. emacs + gud mode is a great experience for go debugging. I've even used it to debug low-level issues like plugin loading and verification.
  - isaachier 9y ago
    On Mac, I find lldb is terribly low level. IIRC Linux gcc isn't great either. Even delve will frequently seem to have missing/optimized variables that cannot be printed.
    - yorwba 9y ago
      I frequently hit the problem with variables that are <optimized out> when debugging C code using gdb, and it's especially infuriating when I can look at the disassembly and see that the variable is right there in the register file. Does anyone know whether dwarf simply doesn't support the necessary debug information or whether compilers just don't retain it through the optimization process?
arghwhat 9y ago
So, preemptive green-threads? This seems like a counter-productive and highly complicated re-implementation of what the OS thread model does, but inside the Go runtime. I would very much like for goroutines to remain cooperative. It is much simpler, naturally more performant, and quite easy to reason about. A local implementation of preemptive execution seems like a very high price to pay to only handle a few corner-cases. That is not to say that preemptive scheduling does not have their place: They make a lot of sense at an OS level where independent processes are scheduled, but little sense as an internal green-thread implementation.
- chrisseaton 9y ago
  > This seems like a counter-productive and highly complicated re-implementation of what the OS thread model does, but inside the Go runtime. But I think you still get advantages such as being able to manage stacks yourself, which is what allows for many more coroutines than native threads.
  - jnwatson 9y ago
    This is the part I don’t understand. You know you can specify the stack size explicitly in POSIX? I can set the stack size to the same 2k in Go and have less overhead. The only difference is it won’t auto-expand like in Go.
    - chrisseaton 9y ago
      > The only difference is it won’t auto-expand like in Go. Well yeah that’s the difference I was talking about.
    - coldtea 9y ago
      >The only difference is it won’t auto-expand like in Go. Which makes all the difference.
      - jakewins 9y ago
        Stacks in Linux grow dynamically, so if you want go-like stacks you just set the max stack size == system memory. See http://man7.org/linux/man-pages/man2/setrlimit.2.html http://man7.org/linux/man-pages/man2/setrlimit.2.html
anonacct37 9y ago
I'm really excited about this both for the improved long tail latency as well as (what I believe is) a new way of handling this problem. I'm not aware of another M:N threading model that handles preemption this way with signals. Erlang accomplishes it with reduction budgets and reduced performance.
Cieplak 9y ago
Interesting old thread comparing actors to software transactional memory (STM): https://www.reddit.com/r/haskell/comments/175tjj/stm_vs_actors/ https://www.reddit.com/r/haskell/comments/175tjj/stm_vs_acto... Seems like pre-emptive actor-based concurrency is simple to implement using STM, but much harder to implement STM with actors.
alex7o 9y ago
They should just make it possible to add safeties manually
- icholy 9y ago
  isn't that what runtime.Gosched does?
tinco 9y ago
The way I understand this, and that I think some other people in this thread misunderstand, is that this is not a change to the Go language in any way. The way Go works is that you can spawn green threads, and the Go runtime will magically run them concurrently, in such a way that you do not have to worry about many problems usually associated with concurrent programming. This proposal seeks to modify the way the "magically" part works. Right now, it suggests that what Go does is to 'cooperatively' preempt at function prologues. This change would instead allow the runtime to preempt at a choice of "safe points" the compiler suggests throughout your Go code. Note that this is a little bit in the gray area between cooperative and non-cooperative. It's not like the runtime will just randomly preempt, it still requires cooperation from the code to have these safe points. But maybe I'm misunderstanding the details. Anyway, not much changes for the Go programmer. The Go programmer can expect his code to be a little more predictable, at the cost of having his code be a little less performant, this performance cost I think will not be significant, if not fully compensated by the increased parallelism. All the promises the Go runtime makes towards the programmer will still hold.
- zzzcpan 9y ago
  The proposal is to turn all go code into safe points.
- mseepgood 9y ago
  > at the cost of having his code be a little less performant Where did you read this? The proposal states: "This approach will solve the problem of delayed preemption with zero run-time overhead."
  - uluyol 9y ago
    Hopefully this can actually decrease overhead. Go's garbage collector has some short STW pauses that require stopping the world. It you have one thread misbehaving by running a tight loop right now, the rest of the threads will sit there spinning until that one thread reaches a preemption point. With explicit preemption, that period would be much shorter.
- 9y ago
krylon 9y ago
Can someone make an informed guess on how much that would complicate the implementation? And/or how much of a performance impact it would have (for better or for worse)?
PDoyle 9y ago
Pre-emptive runtimes are hard. Inserting yield points judiciously in loops isn't that incredibly difficult, and neither is reducing the cost of a yield point. It's far harder to make sure every machine instruction in every part of the runtime is prepared to be interrupted and have all it assumptions violated by the time it resumes.
- bradfitz 9y ago
  > Inserting yield points judiciously in loops isn't that incredibly difficult, and neither is reducing the cost of a yield point. The Go team has done both over the past few years but we haven't been happy enough with the performance. Hence Austin's proposal.
- zzzcpan 9y ago
  Imagine how much simpler and faster a runtime could be if every function was split into a series of non interruptible blocks. Sure, a bit tricky with loops, you'd have to cap them to make sure they are not hogging the system and you don't introduce too much overhead. But small price to pay for not wasting years of man-hours on silly low level stuff and barely achieving usable results.

150 points by mseepgood 9y ago

stefanchrobot 9y ago

I'd love to see this implemented, especially that I already enjoy this feature a lot in Elixir/Erlang/BEAM.

dmytrish 9y ago
The problem with that approach in Go is that BEAM embraces the shared-nothing approach, and the Go runtime is quite promiscuous about sharing mutable data. I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid.
- mseepgood 9y ago
  Mutating shared state without synchronization is a bug with or without this proposal. Goroutines already run on potentially different OS threads or processors with the current m:n scheduler implementation.
- jerf 9y ago
  "I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid." They already took a few steps inside of Go to try to ensure that concurrency is quite non-deterministic. Even very simple, naive code like func main() { for i := 0; i < 2; i++ { go func(j int) { fmt.Println("First", j) fmt.Println("Second", j) }(i) } time.Sleep(100*time.Millisecond) } will very frequently produce different results; I just ran that four times and got four different results. This is good, because it tends to bring bugs to the forefront more quickly, rather than having a almost-but-not-quite-deterministic model as has been the case in many other environments. (Yes, I know sleep is not production-quality here, just trying to keep it simpler than several more lines for a proper waitgroup usage.) I doubt there's a lot of code written at the Go level that would explode if you suddenly ran it with a pre-emptive runtime that isn't already exploding. As the proposal discusses, there's a lot of issues down at the runtime level, but at the layer of abstraction presented by the language itself I wouldn't expect a lot of problems. Non-zero, and even then, it would still be things that are technically already bugs. And Go code is already running concurrently all the time in the real world. I'm not even sure how I'd construct an example that runs correctly in the current runtime but fails with true pre-emption.
  - notheguyouthink 9y ago
    > will very frequently produce different results; I just ran that four times and got four different results. This is good, because it tends to bring bugs to the forefront more quickly, rather than having a almost-but-not-quite-deterministic model as has been the case in many other environments. I concur, they do this with maps too. It led to discovering a bug in our system where order was being implicitly depended on via a JSON Object -> Map conversion. Go randomized the map key order when iterated over, revealing the logic bug.
  - lloeki 9y ago
    > They already took a few steps inside of Go to try to ensure that concurrency is quite non-deterministic I would not be surprised as they are already proactively ensuring things like map ordering are randomised so that people just can't rely on some deterministic ordering: run the example code here[0] multiple times and it produces not just a seemingly random result (as would be for a typical hash table) but a truly different result for each run. [0]: https://nathanleclaire.com/blog/2014/04/27/a-surprising-feature-of-golang-that-colored-me-impressed/ https://nathanleclaire.com/blog/2014/04/27/a-surprising-feat...
    - kardianos 9y ago
      Yes, map iteration is explicitly randomized for just this thing.
- dilap 9y ago
  Go code is not shared-state safe in the way that, say, Python generators are. And with the -race compile flag, it does a pretty good job of detecting violations so you can fix them. So I think Go code should be unaffected by this change.
- masklinn 9y ago
  > I am afraid that introducing non-deterministic preemptive stops will just make Go concurrency a mess similar to the mutex/conditionals mess they've been trying to avoid. It already is exactly that (Go already does m:n scheduling, so while your routine currently can't get interrupted between two function calls, two goroutines running on different OS threads can manipulate the same mutable state without synchronisation and make a mess of it), it's just that you don't necessarily notice.

nostalgeek 9y ago

interesting, is the current situation one of the reason Go debugging experience is so poor? Delve debugger is constantly crashing for me, making step debugging extremely hard, especially when debugging tests. If there is one thing that is inferior to Java and C# with Go it's definitely the debugging experience.

arghwhat 9y ago
Not at all. Non-cooperative goroutines would make it much harder to implement a debugger. Delve crashing is just related to Delve being buggy. Single-stepping is done at the instruction level, and the task of a Go debugger mostly relates to mapping instructions to source code, and understanding the runtime. You can debug Go with gdb, but without Go runtime comprehension, all you will see is a bunch of worker threads executing Go runtime code, rather than the individual goroutines of your process.
anonacct37 9y ago
I've actually never run into a problem debugging go binaries with gdb. Which is weird because everyone's always told me it doesn't work. I'm sure there are edge cases but over the last 5 years or so my experience has been pretty good. emacs + gud mode is a great experience for go debugging. I've even used it to debug low-level issues like plugin loading and verification.
- isaachier 9y ago
  On Mac, I find lldb is terribly low level. IIRC Linux gcc isn't great either. Even delve will frequently seem to have missing/optimized variables that cannot be printed.
  - yorwba 9y ago
    I frequently hit the problem with variables that are <optimized out> when debugging C code using gdb, and it's especially infuriating when I can look at the disassembly and see that the variable is right there in the register file. Does anyone know whether dwarf simply doesn't support the necessary debug information or whether compilers just don't retain it through the optimization process?

arghwhat 9y ago

So, preemptive green-threads? This seems like a counter-productive and highly complicated re-implementation of what the OS thread model does, but inside the Go runtime. I would very much like for goroutines to remain cooperative. It is much simpler, naturally more performant, and quite easy to reason about. A local implementation of preemptive execution seems like a very high price to pay to only handle a few corner-cases. That is not to say that preemptive scheduling does not have their place: They make a lot of sense at an OS level where independent processes are scheduled, but little sense as an internal green-thread implementation.

chrisseaton 9y ago
> This seems like a counter-productive and highly complicated re-implementation of what the OS thread model does, but inside the Go runtime. But I think you still get advantages such as being able to manage stacks yourself, which is what allows for many more coroutines than native threads.
- jnwatson 9y ago
  This is the part I don’t understand. You know you can specify the stack size explicitly in POSIX? I can set the stack size to the same 2k in Go and have less overhead. The only difference is it won’t auto-expand like in Go.
  - chrisseaton 9y ago
    > The only difference is it won’t auto-expand like in Go. Well yeah that’s the difference I was talking about.
  - coldtea 9y ago
    >The only difference is it won’t auto-expand like in Go. Which makes all the difference.
    - jakewins 9y ago
      Stacks in Linux grow dynamically, so if you want go-like stacks you just set the max stack size == system memory. See http://man7.org/linux/man-pages/man2/setrlimit.2.html http://man7.org/linux/man-pages/man2/setrlimit.2.html

anonacct37 9y ago

I'm really excited about this both for the improved long tail latency as well as (what I believe is) a new way of handling this problem. I'm not aware of another M:N threading model that handles preemption this way with signals. Erlang accomplishes it with reduction budgets and reduced performance.

Cieplak 9y ago

Interesting old thread comparing actors to software transactional memory (STM): https://www.reddit.com/r/haskell/comments/175tjj/stm_vs_actors/ https://www.reddit.com/r/haskell/comments/175tjj/stm_vs_acto... Seems like pre-emptive actor-based concurrency is simple to implement using STM, but much harder to implement STM with actors.

alex7o 9y ago

They should just make it possible to add safeties manually

icholy 9y ago
isn't that what runtime.Gosched does?

tinco 9y ago

The way I understand this, and that I think some other people in this thread misunderstand, is that this is not a change to the Go language in any way. The way Go works is that you can spawn green threads, and the Go runtime will magically run them concurrently, in such a way that you do not have to worry about many problems usually associated with concurrent programming. This proposal seeks to modify the way the "magically" part works. Right now, it suggests that what Go does is to 'cooperatively' preempt at function prologues. This change would instead allow the runtime to preempt at a choice of "safe points" the compiler suggests throughout your Go code. Note that this is a little bit in the gray area between cooperative and non-cooperative. It's not like the runtime will just randomly preempt, it still requires cooperation from the code to have these safe points. But maybe I'm misunderstanding the details. Anyway, not much changes for the Go programmer. The Go programmer can expect his code to be a little more predictable, at the cost of having his code be a little less performant, this performance cost I think will not be significant, if not fully compensated by the increased parallelism. All the promises the Go runtime makes towards the programmer will still hold.

zzzcpan 9y ago
The proposal is to turn all go code into safe points.
mseepgood 9y ago
> at the cost of having his code be a little less performant Where did you read this? The proposal states: "This approach will solve the problem of delayed preemption with zero run-time overhead."
- uluyol 9y ago
  Hopefully this can actually decrease overhead. Go's garbage collector has some short STW pauses that require stopping the world. It you have one thread misbehaving by running a tight loop right now, the rest of the threads will sit there spinning until that one thread reaches a preemption point. With explicit preemption, that period would be much shorter.
9y ago

krylon 9y ago

Can someone make an informed guess on how much that would complicate the implementation? And/or how much of a performance impact it would have (for better or for worse)?

PDoyle 9y ago

Pre-emptive runtimes are hard. Inserting yield points judiciously in loops isn't that incredibly difficult, and neither is reducing the cost of a yield point. It's far harder to make sure every machine instruction in every part of the runtime is prepared to be interrupted and have all it assumptions violated by the time it resumes.

bradfitz 9y ago
> Inserting yield points judiciously in loops isn't that incredibly difficult, and neither is reducing the cost of a yield point. The Go team has done both over the past few years but we haven't been happy enough with the performance. Hence Austin's proposal.
zzzcpan 9y ago
Imagine how much simpler and faster a runtime could be if every function was split into a series of non interruptible blocks. Sure, a bit tricky with loops, you'd have to cap them to make sure they are not hogging the system and you don't introduce too much overhead. But small price to pay for not wasting years of man-hours on silly low level stuff and barely achieving usable results.