Is there actually some profound research material or experience from larger projects on whether stackful [g|c]oroutines or stackless ones performs better? I'm wondering about this for quite some time and would be very interested in some more facts about this.
During the last years the stackless style in form of eventloops with promises, continuations and async/await sugar got a lot of traction. Often the authors argue that it's better for performance, since no stacks need to be allocated, switched or resized and the only overhead is the object which is allocated for the statemachines - which is true for sure. However these systems have still lots of dynamic allocations, often one or more for each point where a suspension happens. With goroutines in contrast there should be no need for dynamic allocations in general. And also less need for dynamic allocations in general, since lots of state can be put on the stack instead of being stored in various statemachine objects in the heap. I guess data locality might also be a plus for goroutines, instead of having state possibly spread all over the heap it's in a smaller region which is the goroutines stack. But of course the downside is that these stacks need to be allocated and sometimes resized (however I think for lots of goroutines that either won't happen or won't happen often).
> However these systems have still lots of dynamic allocations, often one or more for each point where a suspension happens. And also less need for dynamic allocations in general, since lots of state can be put on the stack instead of being stored in various statemachine objects in the heap. I guess data locality might also be a plus for goroutines, instead of having state possibly spread all over the heap it's in a smaller region which is the goroutines stack
Rust's futures-rs library seems to only require a single allocation for a whole "task", rather than at every suspension point. This implies that that all of the relevant persistent-across-suspensions data is in one object on the heap, in a contiguous allocation that is reused for the whole processing (similar to a goroutine's stack).
> - None of the future combinators impose any allocation. When we do things like chain uses of and_then, not only are we not allocating, we are in fact building up a big enum that represents the state machine. (There is one allocation needed per “task”, which usually works out to one per connection.)
It's certainly true that Rusts future model (which is readiness and not completion based) is the one that requires fewer allocations - e.g. compared to JS promises or C# Tasks. There seem to be some in the Task structure for parking/unparking. I don't have any idea how often these happen as I don't have a deep understanding of that code. Besides that I think most more complex scenarios will use boxed futures, as combining the raw futures yields more and more complex future types which at some point won't combine anymore unless there's some type erasure (through boxing) - or probably with intense effort and knowledge that the average user won't have. The comparable thing to lots of these combinators with goroutines would just be normal control flow (loops, conditions, etc.), which will not allocate. Then there's some things where I'm not certain about how they work out with Rusts approach: E.g. let's say I have some kind of parser with 20 input states that, and for the duration of each state I would need some temporary variable of 500bytes. With the stackful approach I would enter a new scope (maybe in form of a function call), put the temp variable and the stack, work with it in the blocking call, exit the stack and the memory is freed. My understanding is that with Rusts state machine approach where everything is allocated upfront I would need to reserve the 500bytes in each of the child futures which handles the step and the total future would combine those, which results in 20*500bytes. Or are these coalesced since the combined future can be represented as an enum/union?
It's still using callbacks, though. So while there may be a single allocation, code conciseness suffers.
Using Rust futures' and_then, or_else, etc interfaces, try writing a parser that consumes data byte-by-byte, where reading each input byte might block. (Similar to using fgetc() in a C state machine.) It won't be very easy to understand, especially compared to threaded code.[1] Doing that with coroutines, even stackless coroutines, would be much more clear.
That's the problem with futures. If futures were so great, we'd use them for all control flow. There's a reason we don't, just like there's a reason we don't use purely functional languages everywhere. But at least purely functional languages are consistent, and usually have other features (like lexical binding and garbage collection) to make alternative control flow patterns easier and more concise.
Ask yourself this: if resizeable, relocatable stacks were a freebie (i.e. already provided, or because there was 0 desire to support a pre-existing calling convention and most of the instrumentation needed for moving stacks was preordained by exceptions), would you ever not implement stackful coroutines? The future pattern API could be easily implemented as a library for when it made sense. Decorating calls with "async" would become superflous, but people would still be free to do that. Message passing and consumer/producer inversions would become free and natural coding patterns. Stackful coroutines are clearly the more powerful abstraction. But implementing them is difficult, especially in the context of legacy environments (e.g. C runtimes) and so people compromise and often choose a less powerful abstraction.
[1] In reality you're likely to use a mismash of patterns and language features because futures will just be too intrusive of a construct for fine-grained control flow manipulation. All of that adds to the complexity of a language and to the solutions you implement in the language.
Back when C10K was first written, the big debate was between threaded vs asynchronous (implicitly callback based) code. In terms of performance asynchronous won the day, but I think the threading proponents were always correct that threaded code was more natural, more clear, and less buggy (ignoring preemptive multithreading). Even though I've spent over 15 years writing asynchronous I/O networking code, I think the threading proponents were correct. For control flow, threading is the best default model and should be the gold standard. Stackful coroutines are similar to threads in terms of how they relate to normal calling conventions and function types. When it comes to the theoretical code conciseness and performance possibilities that's no coincidence.
Once you have callbacks, it's not hard to wrap it in some nice syntax sugar that makes it look like regular code, more or less. Or did you mean something else?
Yes, I agree that it's a matter of "legacy environments". But the thing about it is that they will remain non-legacy for as long as the purported successor is not determined. The C model that everyone currently uses as the lowest common denominator persists precisely because of that - it's what everyone has been able to agree on so far. Beyond that, not so much. So Go-style coroutines may well be awesome, but it doesn't matter because of all the other languages that have incompatible models.
Futures, on the other hand, work for this purpose, because you can represent them even on C ABI level. Granted, it's a fairly expensive abstraction then, but it works. Look at WinRT, where futures are pervasive in platform APIs and code that consumes them, and it all works across .NET, C++ and JS, with a single future ABI underneath all three.
> Ask yourself this: if resizeable, relocatable stacks were a freebie (i.e. already provided, or because there was 0 desire to support a pre-existing calling convention and most of the instrumentation needed for moving stacks was preordained by exceptions), would you ever not implement stackful coroutines?
Don't stackful coroutines necessarily mean you need a runtime (with a GC) that is able to grow the stack ? Or am I missing something ?
To allow for stack growing, the compiler would insert a small number of additional instructions into function entries that either do nothing or call out to a runtime library function that handles stack growing.
Nothing conceptually new in here, that isn't already done by compilers to deal with exception handling, initialize variables or perform division on machines that don't do it natively.
Sure, it requires some runtime support but so does almost every C or C++ program in existence.
FWIW, Rust used to use split stacks, as implemented by LLVM, but they had problems like unpredictable performance (if one happened happened to be unlucky and end up repeatedly calling functions across the split boundary, each of those calls ends up doing far more work than desireable). Relocating stacks is a whole other issue, and almost impossible in the model of languages like C/C++/Rust where there's no precise tracking of pointer locations: the information in exception handlers (approximately) tells you were things are, but nothing about where pointers to those things are.
Yes, copying stacks are unsuitable for unrestricted C or C++ code. Segmented stacks might have problems (Go also switched away from them for the same hard-to-predict performance reason) but when you can't do stack moving I still think they're attractive.
During the last years the stackless style in form of eventloops with promises, continuations and async/await sugar got a lot of traction. Often the authors argue that it's better for performance, since no stacks need to be allocated, switched or resized and the only overhead is the object which is allocated for the statemachines - which is true for sure. However these systems have still lots of dynamic allocations, often one or more for each point where a suspension happens. With goroutines in contrast there should be no need for dynamic allocations in general. And also less need for dynamic allocations in general, since lots of state can be put on the stack instead of being stored in various statemachine objects in the heap. I guess data locality might also be a plus for goroutines, instead of having state possibly spread all over the heap it's in a smaller region which is the goroutines stack. But of course the downside is that these stacks need to be allocated and sometimes resized (however I think for lots of goroutines that either won't happen or won't happen often).