> Are libmill and Go's approach the same? I.e. Holding concurrent state in multiple stack frames? What causes that to have degraded performance?
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.
> This requires that you either know the size of the stack up front ... generally not possible without being conservative
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.
It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program.
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.
I was thinking of a much lighter analysis, based on some optional restrictions. If a function:
- 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.
No program beyond the most trivial will meet these requirements. The moment you call any function indirectly you lose.
Yes, but indirectly means "&Fn", but not "&F where F: Fn".
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)
The problem with an optimization like this is that the current approach always gives you a guarantee on runtime cost. Heuristic based optimizations make performance harder to ensure, not to mention recovering performance when you fall outside the valid subset much more difficult. You can obviously provide another static analysis to warn you about violations, but this seems is more complex, and less flexible then the current approach.
Actually the "current approach" gives you no bound on the stack size. You guess, hope, and test (or do this analysis manually).
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.
Are you sure about that? First, many higher-order constructs boil down to simple first-order control flow after partial evaluation (see e.g. AnyDSL https://anydsl.github.io/#publications). Inferring stack size bounds in the presence of higher-order programming features is also possible, and was implemented (as the "static region optimization") in MLkit.
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't get around page fault blocking with user-space M:N threading. It will be approximate until there is a way to do that.
"It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program."
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.