Proposal: Non-cooperative goroutine preemption
github.com
github.com
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.
Where did you read this? The proposal states: "This approach will solve the problem of delayed preemption with zero run-time overhead."
That's how it already works, it's just that safepoints only get introduced at function prologues. This is an issue as CPU-heavy functions without any non-inlined function calls mean very few safe points which is problematic for GC and timely scheduling and may even lock up the entire system.
Previous attempts were made to add loop preemption but there are issues with that approach.
The approach in TFA is to make safe points "opt-out", all Go code would be considered safe by default with some "unsafe" regions being excluded. As the author states, this would make Go preemptive rather than cooperative ("I propose that we implement fully non-cooperative preemption").
> Anyway, not much changes for the Go programmer. The Go programmer can expect his code to be a little more predictable
Go programmers can expect their code to be a little less predictable, not more: currently your code is guaranteed to run uninterrupted between two function calls, that will not be the case anymore.
In theory it should not make any difference, in practice it will probably uncover concurrency bug you're currently shielded from by the runtime's behaviour (though likely not that many as you can already have multiple routines running in parallel).
This is incorrect. Go has had preemptive scheduling (instead of cooperative) since at least 1.2 (possibly 1.1). The proposal here is to make it preempt at arbitrary points, not just at certain points.
The points at which it currently can preempt is far greater than simply function prologues, which is why full preemption has very little impact on the end user (it already appears to preempt at essentially arbitrary points).
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.
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.
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.
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)
}
(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.
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.
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-feat...
So I think Go code should be unaffected by this change.
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.
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.
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.
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?
DWARF appears to support mapping symbol locations to registers, but I’ve never seen a language environment/debugger that takes advantage of it for optimized binaries.
Are you able to step inside code running in a goroutine? with GDB? Because it's where GDB starts to become useless for debugging.
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.
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.
Well yeah that’s the difference I was talking about.
Which makes all the difference.
I think Linux can defer committing memory for the pages of the stack until they're used, but you need to reserve the entire virtual memory in the first place don't you? Otherwise how can you have the ability to dynamically allocate more stack virtual address space to an arbitrary thread, without relocating it? Or if you do relocate how do you update pointers to the stack?
Note that Go stacks can also shrink.
man PTHREAD_ATTR_SETSTACKSIZE(3) says:
> The stack size attribute determines the minimum size (in bytes) that will be allocated for threads created using the thread attributes object attr.
and:
> A thread's stack size is fixed at the time of thread creation. Only the main thread can dynamically grow its stack.
My understanding is that it is referring to virtual memory. The kernel would allocate a giant blob of RAM, [stacksize + heapsize + some other stuff] large. My reading of the manpage above is that the main thread can change this allocation, while other threads are stuck with what they started with.
But why would the kernel actually realize the stack portion of the allocation? Surely if I create a 1G stack child thread, it will not realize those stack pages until I actually use them?
The initial thread in a process, on every operating system that is still relevant today, uses guard pages to grow its virtual memory allocation for the stack segment. Physical memory for the stack segment's pages may or may not be mapped into the process address space (it will usually be mapped). This stack can't shrink, and also once the thread touches a page, it becomes commited memory and it will always stay commited.
Other threads in a process do not use guard pages and use fixed virtual memory allocation for their stacks. Their stacks are fixed in size and can't grow. Just like for the initial thread once a page is touched, it becomes commited memory and it will always stay that way.
In Go, stacks start small and use a variable amount of virtual memory. Go stacks can shrink, freeing both address space and physical memory.
It would be indeed a reimplementation of what OS does, but note that such a reimplementation is the very reason why quite straightforward Erlang code can easily handle hundreds of thousands active connections on modest hardware.
Preemption is good because it prevents bad processes from starving the rest of the system but it's far from efficient.
Have they changed it? Last I knew, processes get a "reduction count", which is basically "the number of opcodes in the VM this process gets to run before it gets suspended". Technically, this is exactly like what Go does, except instead of sticking pre-emption points at function calls, it places them at every opcode, which is to say, quite often multiple times per line of code. Technically, you can still freeze the interpreter (or a thread of it) by calling into some C code that counts as one "reduction" but never returns. In practice, this causes about as much trouble for Erlang programmers as it does Go programmers, namely, "it's something you should know but can literally go your entire career without hitting". (Depends on what kind of code you're writing. Someone trying to use Erlang or Go for heavy numerical processing has a good chance of hitting it, but if you're writing network code, you'd have to reeeaallly work at it in either environment.)
> Technically, you can still freeze the interpreter (or a thread of it) by calling into some C code that counts as one "reduction" but never returns.
Actually, you can't! (Or, well, at least as long as you've given a moment of thought while coding your NIF you can't.)
Avoiding this used to require explicit calls to the reduction budgeting functions in your native code. But as of recent ERTS releases, you just have to mark your NIF as "dirty" and it'll get offloaded to a separate scheduler-thread-pool that exists just to run dirty (i.e. long CPU-time) NIFs. There's no reason, today, to not just mark your NIF as dirty when you start writing it, and then take the dirty flag off only when you're ready to add the calls to the reduction-budgeting logic.
(If you flip it around in your head, having a dirty flag is essentially the same as having a "clean" flag—or, in other words, an "I know what I'm doing, I've guaranteed this has reduction-budgeting" flag. Which is no more and no less than something like Rust's unsafe{} blocks. To say you can freeze a runtime with unsafe{} code shouldn't be surprising ;) What's more surprising is that you can run native code within ERTS that's not unsafe{} in this sense! ...though, as every Erlang maintainer will tell you, "it's a last resort and you would probably have been fine with a port program, which provides much better isolation.")
But this means that the VM is entirely allowed to interrupt you halfway through a call to sorting a list obtained through a message. No qualms about it. You reach you function call limit, you're phased out and put back in the queue.
The three ways I know about to hog a scheduler for yourself are:
- write C code that misbehaves and stalls the scheduler (there is now a dirty scheduler if you want the code to run there)
- hardcode a sequence of arithmetic operations (which are not subject to reduction counts) that can take a very long time to execute -- something that never happens naturally in code
- set your process to the max priority and do busy looping while the rest of the system is at a lower priority. Your process will now have a higher priority and prevent others from running
That's about what you can do. It requires a kind of explicit effort to do and is very easy to spot from afar.
You can't easily spawn 10.000 OS threads.
> I would very much like for goroutines to remain cooperative. It is much simpler, naturally more performant, and quite easy to reason about.
Cooperative is less simple to reason about, as the proposal explains. Preemption fully delivers what the developer already expects of goroutines.
I just spawned 10.000 OS threads running separate mRuby instances in each thread on my laptop, to see if it'd cause any problems (because I happened to have an app sitting around that spawns separate threads; note: these are not Ruby threads, mRuby does not have built in threading). None at all. So yes, you can. I didn't check how much memory it'd take, however, or attempt to measure overheads in any way, so I'm not saying there aren't potential issues with it.
For example, in Go, they mark a goroutine's stack as "hasn't executed since the last time we marked", which makes GC with thousands of threads a lot faster.
"Mark termination does not have to rescan stacks that haven’t executed since the last scan"
With pre-emptive scheduling of OS threads, you potentially dirty a ton more stacks, and have to scan them all for pointers to heap memory. I'm not sure how VMs using lots of OS threads deal with this.
The "easily" part wasn't referring to feasibility, but to how effortless it is to do AND have performance and scalable code.
This is what I thought until last week, but it seems it's no big deal. 1M threads starts to be an issue.
Of course you can, without any problem at all. It's just more expensive than a green thread (they're full processes with stacks), and unlike green threads, it affects how processing time is sliced. It is, however, much cheaper than people tend to believe.
> Cooperative is less simple to reason about, as the proposal explains.
Cooperative scheduling is very simple to reason about. In the simplest form, you do not give up control unless you use I/O, a synchronization primitive, or explicitly give up control (runtime.Gosched() in Go).
As a Go developer, and as a developer in any other language, this is exactly what I expect from any green thread implementation. That's how M:N scheduling has always been implemented, and how green threads have been implemented in other languages.
Technically, preemptive is harder to reason about, but you save having to reason about it. However, if you expect preemption from goroutines, you have misunderstood the primitive.
This is not how Go works nowadays. There are other preemption points.
Of course you can. Go on, compile and run this program:
#include <pthread.h>
#include <stdlib.h>
void *f(void *arg) {
pthread_mutex_lock((pthread_mutex_t *)arg);
pthread_mutex_unlock((pthread_mutex_t *)arg);
return NULL;
}
int main() {
pthread_t threads[10000];
pthread_mutex_t mutexes[10000];
for (unsigned i = 0; i < 10000; i++) {
pthread_mutex_init(&mutexes[i], NULL);
pthread_mutex_lock(&mutexes[i]);
pthread_create(&threads[i], NULL, f, &mutexes[i]);
}
for (unsigned i = 0; i < 10000; i++)
pthread_mutex_unlock(&mutexes[i]);
for (unsigned i = 0; i < 10000; i++)
pthread_join(threads[i], NULL);
return 0;
}
From what I can see, you could theoretically "reason" about your code if you compile it with the optimizer output on, study it carefully, and understand it intimately, but it would be a dangerously fragile line of reasoning subject to change without notice.
And I say all this ignoring the fact that whatever you are reasoning about is almost certainly already a bug according to the spec and something the race detector will scream about. I would not feel confident running a program that has known race conditions in it, but that you feel like you've reasoned via intimate knowledge of the runtime that they can't actually happen. I'd much rather see you just write the code to be concurrently correct anyhow, and then I can do things like "upgrade to the next version of Go" or "cross-compile to another architecture that may do things that violate your fragile reasoning" without stark terror.
> It is much simpler, naturally more performant, and quite easy to reason about
That is, easy to reason about, not easier to reason about. Technically, preemptive scheduling is harder to reason about, but the point of it all is that you get to pretend it doesn't exist. Thus, from a high-level perspective, preemptive is easier than cooperative.
However, cooperative scheduling is very easy to reason about, like in the case of ECMAScript. In ECMAScript, most API's are async, but you can write "await" to preempt a task and wait for promise completion. In Go, things that cause blocking (I/O, synchronization primitives) automatically preempt.
And my point is that cooperative scheduling isn't Platonically easy to reason about. It is easy to reason about for specific, concrete reasons, reasons which do not apply to Go code. It makes no sense in your post to ask for goroutines to stay cooperative, because cooperative is easy to reason about, because the way Go does it is not easy to "reason" about. Which is why you're 99.9999% of the time better off pretending Go is already fully pre-emptive and writing your code that way, which is close enough to 100% to just go ahead and do it, as the effort of detecting when you may be in that less-than-once-per-career case exceeds just writing code to be preemptively-correct.
I suppose I'll concede that a very, very narrow reading of your text is technically correct, but in that case, that narrow technical reading consists of facts that make no sense to bring up in this context, so I'm not feeling all that guilty about my slightly more expansive reading.
(I also don't even particularly agree that cooperative threading is easy to reason about. In practice I have found that even if you know that your code isn't going to be pre-empted in the middle of a block, that is still very difficult to correctly turn into code that is correct in the face of high concurrency. I actually find it easier to write code with sensible concurrency constructs like channels or actors than to try to write correct code based on lots of assumptions about cooperative multithreading. Or, if you prefer, it is certainly academically easy (not easier, but easy) to reason about but in practice I'd take channels, actors, Clojure/Haskell STM, or any of a bunch of other sensible constructs any day. By which I mean, I do; my skin's in the game here, I'm not just abstractly pontificating.)
Your comment is rather empty without examples or elaboration. It also seems that all but one point is not actually related to cooperative vs. preemptive multitasking.
You claim that the reasons for cooperative multitasking being simple do not apply to Go code (from your previous post, I assume that you find them to apply to ECMAScript). However, you do not present any reasons for this. Would you mind elaborating?
Go is a little bit more magic than ECMAScript, but ECMAScript is for all intends and purposes a single-threaded language (Web workers exist, but they cannot share resources due to the memory problems it would create, and instead rely on a simple message passing mechanism). This makes it a very different beast from Go (read: simpler).
However, it is not very magic. You can basically just consider all I/O and synchronization primitives to be prefixed with "runtime.Gosched()", or the equivalent yielding function from other green thread implementations.
Elaboration of your comment about the difficulty of turning cooperative code into "correct code in the face of high concurrency" would be also nice. Some types of parallel code can be quite hairy to guarantee correctness of, but I don't see how this is related to cooperative vs. preemptive multitasking.
You are mentioning channels and actors as if that is mutually exclusive from the Go model, which I find odd considering that Go caters specifically to the use of channels and actors. They are also completely detached from the choice of multitasking model, and exist just fine in both preemptive and cooperative environments.
I do quite like the channel/actor model, but that is entirely unrelated to the discussion. I would also find the implication that all other primitives are not "sensible" to be a very, very large claim. And a broken one at that. :)
This proposal is about fixing some of the edge cases where the current implementation doesn't do what the interface is supposed to. It outlines another, simpler approach which just has the compiler add more yields, but apparently the performance impact of that is too high. But it's just a question of perf & implementation complexity, not semantics.
Is this true? The proposal seems to indicate that preemption is more performant? Or at least it says "no runtime overhead", which is presumably in contrast to the current implementation.