Fibers under the magnifying glass [pdf](open-std.org)
open-std.org
Fibers under the magnifying glass [pdf]
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1364r0.pdf
7 comments
Section 2.1.1 talks about fixed stack sizes though, so you only get to do 1 allocation, and in general it is not possible to precisely compute the necessary transitive stack size given a function due to recursion/indirect calls.
Stackless coroutines do not have this requirement, it is enough to be able to know the required frame size locally, without considering recursion/indirection. And fallback heap allocations are not surprising since we do not statically know the required frame size at the call site. Segmented stacks have their own tradeoffs too, checking if you have enough stack space at every function entry is not cheap.
Stackless coroutines do not have this requirement, it is enough to be able to know the required frame size locally, without considering recursion/indirection. And fallback heap allocations are not surprising since we do not statically know the required frame size at the call site. Segmented stacks have their own tradeoffs too, checking if you have enough stack space at every function entry is not cheap.
> Stackless coroutines do not have this requirement, it is enough to be able to know the required frame size locally, without considering recursion/indirection.
If stackless coroutines only consider local frame size requirements, then you're back to heap allocating every call or we're only talking about using coroutines as leaves in the call graph. But if coroutines are only at the leaves, then they're definitely not fit for the purpose of concurrent programming--I've never written an asynchronous I/O program in C where my logical call depth of resuming functions is 1. If you graph all the callbacks and what they'd look like as normal function calls, it's definitely not 1.
Rust has "stackless" coroutines, but naturally they're not restricted to a call depth of 1. The compiler analyzes the call graph from the point of entry to the first resumable function and attempts to allocate space for all the persistent state necessary.
> Segmented stacks have their own tradeoffs too, checking if you have enough stack space at every function entry is not cheap.
In a world where the compiler can and is statically analyzing calls as deep as possible to optimize memory allocation patterns, that exact same facility could be used to optimize the points at which a segmented stack would check for and jump stacks. Which is my point--fundamentally these are the same things. A stack is a stack is a stack. We end up with the same data structures and they can be optimized the same. But in debates surrounding concurrency, people keep stating points layered on unstated assumptions. For example, that stackless coroutines will have a super amazing optimizing compiler for packing the call state, whereas for the segmented stack alternative universe somehow this technique wouldn't be used, and because it wouldn't be used then segmented stacks are therefore worse. That's circular logic.
The whole debate around concurrency techniques is muddled by these implicit assumptions. Some assumptions are defensible, but others not so much. It's difficult to identify and discuss which assumptions are defensible or not because these assumptions sit in the background. They come out as cudgels to defend a particular choice and are then quickly glossed over. Take, for example, the paper's mention of the incompatibility of fibers and thread-local storage facilities. The assumption here is that if C++ adopted fibers, the TLS issue wouldn't be remedied. That's ridiculous. If C++ adopted fibers, of course they'd work just fine with TLS. The whole reason the incompatibility exists, such as it does, is precisely because the compiler and language runtime aren't part of the equation--once they become part of the equation, then TLS semantics would naturally be addressed as a matter of course. If this was a real stumbling block, TLS could never have even been added to C++ in the first place.
I'm not trying to say that C++ or Rust should have adopted fibers or segmented stacks. Just that you can't draw any meaningful conclusions from these debates and these language design choices without understanding the self-imposed limitations and paths not explored. For example, the paper says that Rust tried and abandoned segmented stacks. Yes, but it did that long before it added async/await, and some of the language and compiler changes required for async/await could have (in principle) benefited segmented stacks.
So the fact that Rust abandoned segmented stacks tells us very little about segmented stacks. Rather, it speaks far more to the process by which languages and compilers are developed these days, where the path of least resistance is to put features at the only layer you completely control, even if it means severely compromising functionality. Contrast that with earlier languages like Java, where the evolution of platform threading facilities, especially on Linux and *BSD, where shaped by Java, rather than Java being shaped by the limitations of those facilities.
If stackless coroutines only consider local frame size requirements, then you're back to heap allocating every call or we're only talking about using coroutines as leaves in the call graph. But if coroutines are only at the leaves, then they're definitely not fit for the purpose of concurrent programming--I've never written an asynchronous I/O program in C where my logical call depth of resuming functions is 1. If you graph all the callbacks and what they'd look like as normal function calls, it's definitely not 1.
Rust has "stackless" coroutines, but naturally they're not restricted to a call depth of 1. The compiler analyzes the call graph from the point of entry to the first resumable function and attempts to allocate space for all the persistent state necessary.
> Segmented stacks have their own tradeoffs too, checking if you have enough stack space at every function entry is not cheap.
In a world where the compiler can and is statically analyzing calls as deep as possible to optimize memory allocation patterns, that exact same facility could be used to optimize the points at which a segmented stack would check for and jump stacks. Which is my point--fundamentally these are the same things. A stack is a stack is a stack. We end up with the same data structures and they can be optimized the same. But in debates surrounding concurrency, people keep stating points layered on unstated assumptions. For example, that stackless coroutines will have a super amazing optimizing compiler for packing the call state, whereas for the segmented stack alternative universe somehow this technique wouldn't be used, and because it wouldn't be used then segmented stacks are therefore worse. That's circular logic.
The whole debate around concurrency techniques is muddled by these implicit assumptions. Some assumptions are defensible, but others not so much. It's difficult to identify and discuss which assumptions are defensible or not because these assumptions sit in the background. They come out as cudgels to defend a particular choice and are then quickly glossed over. Take, for example, the paper's mention of the incompatibility of fibers and thread-local storage facilities. The assumption here is that if C++ adopted fibers, the TLS issue wouldn't be remedied. That's ridiculous. If C++ adopted fibers, of course they'd work just fine with TLS. The whole reason the incompatibility exists, such as it does, is precisely because the compiler and language runtime aren't part of the equation--once they become part of the equation, then TLS semantics would naturally be addressed as a matter of course. If this was a real stumbling block, TLS could never have even been added to C++ in the first place.
I'm not trying to say that C++ or Rust should have adopted fibers or segmented stacks. Just that you can't draw any meaningful conclusions from these debates and these language design choices without understanding the self-imposed limitations and paths not explored. For example, the paper says that Rust tried and abandoned segmented stacks. Yes, but it did that long before it added async/await, and some of the language and compiler changes required for async/await could have (in principle) benefited segmented stacks.
So the fact that Rust abandoned segmented stacks tells us very little about segmented stacks. Rather, it speaks far more to the process by which languages and compilers are developed these days, where the path of least resistance is to put features at the only layer you completely control, even if it means severely compromising functionality. Contrast that with earlier languages like Java, where the evolution of platform threading facilities, especially on Linux and *BSD, where shaped by Java, rather than Java being shaped by the limitations of those facilities.
Response to "Fibers under the magnifying glass"
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p086...
Response to response to "Fibers under the magnifying glass" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p152...
Response to response to "Fibers under the magnifying glass" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p152...
Based on the title, I was expecting something quite different...
I've certainly had situations where 'fibers' made more sense - a verilog runtime system with literally millions of them (where the compiler can figure out exactly how much space 99% of the fibers need - so stack sizes of 12 bytes, run-time contexts of similar sizes, 10 instruction dispatch times ....)
Ok, so I guess we can just completely ignore the countless lisp implementations with continuation support (which makes implementing fibers trivial).
"We looked at one programming language with fibers and it has poor performance when calling C." Is what I read in the last section.
"We looked at one programming language with fibers and it has poor performance when calling C." Is what I read in the last section.
Even then, though, the analysis in the paper is still poor. Take section 2.2.1, for example:
> This is approach allows fibers to use very small stacks (less than a typical memory page size of 4K), but, at the cost that the developer must have complete knowledge of how big activation frames are for every function that can be called directly/transitively from the fiber. This is a very precarious approach to be used with extreme caution as the smallest mistake can lead to memory corruption and security exploits.
It characterizes the problem of determining stack size as being so intractable as to be unsafe. And yet this task--precisely calculating activation record size--is exactly what the compiler must do to implement stackless coroutines, the author's preferred solution (and the one adopted by Rust and eventually adopted by C++).
In reality, the compiler can't always do this, and so stackless coroutines in these languages don't permit things like recursive function invocations or calling through function pointers (e.g. virtual methods), at least not without falling back to dynamic heap allocation. And yet elsewhere in the paper the author discusses and dismisses segmented stacks, without it apparently occurring to the author that segmented stacks is precisely what a C++ stackless coroutine implementation must end up implementing in any call chain that cannot be statically determined, which can be quite a common (even pervasive) situation in an object oriented language or in environments with dynamic linking.