Is this new approach different because instead of stack frames you just have dynamically allocated callback state?
In the M:N approach you have to allocate stack space for each goroutine that you spawn. This requires that you either know the size of the stack up front (generally not possible without being conservative and requesting a large allocation) or that you start small and grow (resulting in a lot of memory traffic and pauses in the growth case, and much harder to do in C).
By contrast, with the zero-cost futures approach we statically know exactly how much per-goroutine size we will ever need, and we can allocate precisely that amount. Furthermore, we only save the data that's absolutely needed across blocking calls. This results in much smaller per-connection state, and as a result it's quicker to allocate.
It's the difference between static and dynamic control flow. Full M:N requires us to give up static knowledge of what a goroutine will do and try to do the best we can at runtime. With futures, we have a lot more static knowledge, and as a result we can optimize more aggressively.
Well, you are writing the compiler. Sure you'd be up against the halting problem, but relatively few functions are (non-tail) recursive.
Perhaps the unwieldiness of a large stack is better attributed to the feature of unbounded recursion (and FFI into "uncharted territory") than the feature of green threads.
I appreciate that Rust has already been down the road of lightweight threads. This statement just struck me as an assumption that deserved to be questioned.
The futures library is the control flow analysis. Because it uses the type system instead of higher order control flow analysis, it actually achieves precision.
- is not recursive
- does not call function pointers (ie trait objects)
- allocates only fixed-sized objects on the stack
- only calls functions with known stack requirements
then its stack requirement should be known, no? It feels like with these requirements, one can still write many programs (threads, really). And if one goes beyond the restrictions, then they just pay the cost of having to guess a large stack size.
Stack size analysis would be helpful for other applications as well, like embedded platforms.
And a whole program doesn't need to conform, only individual threads. Presumably the ones you want to make a lot of.
(And if a little dynamicism was required, its expense could be paid for at the use, by creating a fresh necessary-sized stack at that point. But I'm probably opening up old split-stack wounds, sorry)
While your general objection is good to always keep in mind, it is a tradeoff. There is no perfect solution when you're up against the halting problem (unless you're proposing to change the language to only bounded recursion).
What I'm arguing for here is for more than the single problem the OP is solving, so it's not a case of choosing one or the other and calling it a day.
But the main point is that code in a high-level programming language looks very different from C or even Rust code. Sparks in Haskell, or processes in Erlang, or even individual goroutines in Go, are typically executing comparatively tiny programs. If the call graph of the program in question is acyclic, then it should be easy to get a bound on the maximum stack size.
To be clear, I agree with you that a 1:1 threading model is the better design for Rust, simply because it's the only design where you can guarantee zero overhead and don't need a complicated runtime. What I don't agree with is that the M:N threading model is inherently inferior. Especially for a high-level programming language, I would assume that you can reduce the overhead significantly through static analysis and a good implementation.
You can actually do a pretty good job without k-CFA.
First, and i know you know this, when you say "fail to produce a bounded stack size", you really mean "a reasonable bounded stack size".
A bounded stack size of easy, and does not require context sensitive analysis: The stack size is just max sum of stack sizes of of meet over all paths in an acyclic graph :)
The cycles, you either can statically calculate the recurrence count or you can't.
Bounded heap size is pretty much impossible, but stack size is pretty easy.
Recursion is also not hard. You form strongly connected components. You try to prove how often the component is cycled. If you can, victory. If you can't, you can bound it unless it's truly dynamic.
More to the point, here's a paper on doing it with ADA in GCC in 2009 (IE with sticks and fire):
http://www.adacore.com/uploads/technical-papers/Stack_Analys...
Note they are within 2% on most cases, and can detect whether it's statically knowable, bounded, or dynamically changing.
Regarding stack vs. dynamically allocated state (in a future) I'm not convinced what's better. Yes, the allocated stack most likely has an overhead. But at least the data will be stored there in linear fashion and accessing the state will be super cheap once the stack is loaded. In case of futures that hold dynamically allocated data the state might be spread over much more memory locations, so it might be slower to access. I however haven't any more scientific data on this.
In my real-world applications I'm getting about the same performance from a Go based and a boost asio (uses no futures but dynamically allocated callback closures for storing state) networking application. However the programming style is completely different.
This makes it comparable to using a stack. In an M:N solution, the stack is usually (but not always) allocated similarly (e.g. using malloc).