Fiber in C++: Understanding the Basics
agraphicsguynotes.com
agraphicsguynotes.com
However, later in the article (after a long and apparently irrelevant digression about stack management), they describe Windows API functions that are required for using fibers and seem to suggest that fibers are OS-level, and not application-managed.
Am I missing something?
[edit: typo]
Doing it correctly isn't hard, and has been done many times in bullet-proof libs (notably boost::context), but MS would maybe rather you not.
[1]: https://devblogs.microsoft.com/oldnewthing/20080215-00/?p=23...
[2]: https://en.wikipedia.org/wiki/Win32_Thread_Information_Block
...and this causes problems, because it can't guarantee that all fields are initialized or switched successfully: https://lists.boost.org/boost-bugs/2014/10/38476.php
Microsoft continually adds and changes fields in the TIB with each new release of Windows. Attempting to implement fibers manually is a ticking time bomb that should never be used in production.
I already said "MS would rather you not", obviously, otherwise they would have documented the TIB.
The fact remains that tons of production systems rely on officially-unofficial elements of NT's architecture and this is one such element that is heavily relied on by everyone who uses boost stackful coroutines. Hyrum's Law in action.
And yes, those fields do now have to be maintained for backwards compatibility -- because libraries like Boost.Context hardcoded this into applications, unbeknownst to the users of that library.
Only downside of the technique is that it cannot be implemented in WASM (and maybe some other esoteric runtime environments), because WASM has separate data- and call-stacks and the call stack is not accessible from within the WASM virtual machine (while 'async-await' which relies on code transformation done by the compiler can be implemented in WASM just fine).
There is a 'stack-switching proposal' for WASM though, but I don't know what's the state of that:
There isn't much sandboxing value (WASM shouldn't be able to touch addresses outside the sandbox anyways). Was the reason ease of compilation/optimization for arbitrary architectures? Easier to run inside an interpreter?
The default idea for WASM feels like it should have been more like RISC-V (but with enough wiggle-room to allow easy JITing to x86/ARM).
Or are most of WASM's quirks just because it has ASM.js in its lineage?
Implementation is left as an exercise for the reader.
I guess it raises the philosophical question of what is a stack switch, anyway? If you end up cooperatively running multiple "green threads" within a single "OS thread" does it matter that what you actually switched was the entire execution environment?
Kernel Threads (aka threads): OS-Level and preemptive.
Green Threads (aka lightweight threads, virtual threads or goroutines): User-level and preemptive.
Fibers: User-level (sometimes OS-level or offered as a OS library, like in Windows) and cooperative.
Coroutines: User-level and cooperative.
Fibers are distinct in that they have no scheduling and are code being run on a thread - if the thread is preempted, it will resume on that same thread. Unlike cooperative threading, they must explicitly yield.
Coroutines have such varying implementations that you would need to define requirements to know if they count as fibers or not - for instance, whether you mandate a C-compatible stack.
If you're not using a scheduler with fibers then I'd argue you shouldn't be calling it a fibers system (and rather coroutines), since otherwise it's a distinction without a difference.
They’re distinct from CPU threads.
When I last dived into fibers I discovered windows was trying to make them a thing quite a while ago which is why we have things like [0].
Fibers being virtual threads, are recursive. In the same way you can run a VM inside a VM, you could build fibers on top of fibers (which sounds like a recipe for unpredictable performance).
[0] https://learn.microsoft.com/en-us/windows/win32/procthread/u...
On Windows, many things exist in user-space that are managed by the OS. This is in contrast to linux where the Linux kernel is its own thing with its own stable API.
Fibers are an OS-level concept that exists in user-space.
It was designed for MS SQL Server. It have a very confusing API and did not gain much use in 3rd party applications.
Today you have quad cores even on a cheap phone and 16 on a desktop and 60+ on a server and OS and some runtimes make it pretty easy to get large speed ups on many tasks even when subtasks are closely coordinated. (One thing I like about Java is that it has low-level thread primitives that really scale as opposed to many systems have have a small set of low-level primitives that in theory let you do everything but not scale.)
Contrast that to fibers and similar things (JS and Python async) that do a great job of keeping a CPU busy when you are waiting for network activity but are limited to one CPU.
1. You can implement "stack-free coroutines" in C with some really entertaining macros https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
2. Does anyone remembers Cilk? Its still the fastest stackful coroutine models I know of.
Having implemented and used both before (for different purposes), I like both, but with a mild preference for the stackful version. Largely because you don't have function coloring problems, and you can actually get a proper stack trace and is so significantly easier to debug when things go wrong.
It is also good to differentiate coroutines from async (they seem to be very interleaved these days). Coroutines are a mechanic to achieve mutual recursion / generators. And that is fine for expressing certain algorithms and systems in a much cleaner fashion. Note that parallelism is not necessarily implied by "coroutine".
Async is a mechanic to "doing something else" while waiting for IO. Fibers or state machines are both different solutions to this problem. Certain coroutine implementations can help with this, but I think it is massively overused. Rust due to the function coloring problem, ends up requiring almost everything to be marked "async". And some golang code I have read seems to overuse goroutines unecessarily. I think use of async should be narrow and minimized, and localized to only the places where it makes sense.
Yes! It's a shame it never gained traction and Intel abandoned it, eventually getting dropped from icc and gcc.
[0] https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=10...
[0] http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2018/p136...
Apparently the 2018 paper table only covered top 10 languages in the TIOBE index, I wished it can be updated and extended further to top 50 languages.
Another popular compiled language with GC (by default) namely D language (TIOBE ranked 37 as of Sept 2023) does support fiber and it's implemented in its vibe.d web framework [1],[2].
Gor also mentioned about significant 160 ns overhead for stackful fiber in Go (goroutine) to interact with a C library i.e. cost of switching between Go's goroutines and C threads (as of 2018). It will be interesting to know the fiber overhead in D language since C compilation is now natively supported by D compiler [3].
[1] Fibers in Programming in D:
https://ddili.org/ders/d.en/fibers.html
[2] Fibers, what for:
https://forum.dlang.org/thread/eowfajvnzqnncmfnjhnf@forum.dl...
[3] Adding ANSI C11 C compiler to D so it can import and compile C files directly:
Fibers have their own problems: you need to allocate stacks (and that may be expensive), you can't switch fibers between system threads (compilers cache thread local addresses, unfortunately with x86 linux tls often uses fs: segment addressing, so it may appear to work until it doesn't, and weirdly this problem existed in c++20 coroutines too until recent clang versions), widely used open source implementations (e.g. boost context / boost coroutine / boost fiber) are not even exception safe, because you need to save/restore exception globals when switching fibers, and nobody seems to care. :-/
One huge upside to fibers is that a function call is just a normal function call, and it's fast as a result. I wish c++ taken fibers more seriously and added steps for making them safe to use (portable way to handle global state, portable way to mark switching functions as invalidating tls addresses, etc.), we could have something similar to java virtual threads or go goroutines then.
Do you have more details about this issue? What exception globals? And for which ABI? You mean some sort of current pending exception when switching during unwinding?
[I'm a huge fan of stackful coroutines and I wish were blessed by the standard]
https://github.com/llvm/llvm-project/blob/b05f1d93469fbd6451...
These need to be saved/restored when switching fibers, otherwise fiber switches from catch clauses (and destructors!) are unsafe, throw without argument may rethrow incorrect exception, code that commits/rollbacks based on uncaught exceptions counter will not work correctly, etc.
One example I know where this save/restore is implemented is the userver framework, but it seems to be unexpectedly rare in fiber implementations last time I looked.
It is another reason for having this built into the language/standard library so that it can be implemented optimally.
https://www.scs.stanford.edu/~dm/blog/c++-coroutines.html
but I was unpleasantly surprised by much extra code it required to make it run.
The Tiny Fiber library in the article looks pretty hacky right now and the amount of x64/arm specific code might cause trouble with portability, but the concept itself is intriguing. Thank you for the details.
Advantage: Fast switching. Switching between fibers is done by swapping in new values for the program counter and stack pointer. Compare with async, where yielding only takes you up one level of stack, so your code ends up walking a stack of coroutine invocations to get all the way back to the scheduler.
Disadvantage: Expensive setup - each fiber needs its own pre-allocated stack.
Disadvantage: Operating systems don't provide I/O systems readymade to work with fiber schedulers, so if you want to yield to a different fiber during blocking I/O, then you need to invent your own system to handle that.
PS about naming: "Fiber" is the Microsoft Windows name for their implementation of full stack coroutines, but the proper platform-independent name for it is actually "coroutine". I've kept with the word "fiber" here to avoid misunderstandings.
PS about C++: This is based on async like you find it in C# or Python, I don't really know about C++ coroutines.
I’ve programmed both fiber based systems and coroutines. I even created my own fiber libraries for Python (https://github.com/geertj/gruvi) and C++ (https://github.com/geertj/cgreenlet, mostly an experiment, and incorrectly named coroutines for C++ while it’s really fibers). In the Python version I experimented with some features to help you know whether a nested function might switch.
In the end, for me and for the problem domains I worked in, the explicit async/await co-routine style wins over fibers. It gives you most of the performance benefits of user mode switching, all of the memory benefits, while keeping your code mostly lock free.
Most problems can be recast in to that form, only a small subset are better handled by mutable shared state (and hence explicit locks. In those cases one should probably be modelling the updates as 'Compare and Swap' / 'Compare and Set' types of mutable operation, hence avoiding the situation where unexpected preemption can occur while holding a lock.
From my perspective, having use both forms (manually and with language support), I generally find the coroutine (plus Actor/CSP) scheme to be easier to work with and reason about.
In practice in most real world applications in C++, absence of async calls is not enough to guard against re-entrancy. Shared state might still be mutated by callbacks, by recursively re-entering the event loop or by other threads. So you need to either document explicitly all the assumptions you are making and vet every single function you are calling in your implicit critical section, or you need some other mechanism that is going to look like a critical section anyway.
I agree that using explicitly switched coroutines is not sufficient for mostly “lockless” programming (but I do think it’s necessary). I was coming from a thread per core perspective where you run one event loop per core and limit cross core communications (like in the Seastar framework). With this you should be able to perform most state manipulations without locks.
But if you treat fiber-style coroutines like threads, and use locks and message queues exactly the same as you would with threads (although differently implemented, of course), then coroutines are basically better-behaved, and nicely deterministic, threads. It's a wonderful programming model, with the one big drawback that you can't take advantage of multiple cores.
Technically, they're may well be almost the same thing, but practically, they're used very differently.
Fast switching between fibers is mainly what got me interested, of course. Thank you for the explanations.
I am a less than a C++ beginner but I asked Stack Overflow how to run C++ coroutines in a thread pool. It seems coroutines in C++20 are unfinalised but don't quote me on that but I did get some sourcecode for older versions of the C++20 standard.
I used Marce's Coll's excellent blog post about how to create coroutines in assembly by adjusting the RSP register.
https://blog.dziban.net/posts/coroutines/
I extended Marce's code to run the coroutines in kernel threads:
https://github.com/samsquire/assembly (see threadedcoroutines.S)
I have been thinking of coroutines in terms of query compilation for database engines and the volcano query model and this article:
https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
Tying together two pieces of code that call eachother in push or pull driven style is really powerful. Or if you're running multiple independent tasks that need their own state. This as I understand it is the original intent of object orientation that Alan Kay wanted and is represented by Erlang and partly Go.
Specifically, I am thinking of compiler created coroutines where code can be interleaved at compile time rather than at runtime.
So, at least at that time, M:N and scheduler activation was a solution in search of a problem. It might still see a resurgence on one way or another.
Even with N:N architecture, if one kernel thread blocks (say, on I/O), the point is for the user-space scheduler to decide which thread should run next. The point was that the kernel scheduler cannot/should not understand the application thread scheduling requirements, and that when a kernel thread allocated to the task blocks, only user space can (correctly) decide what to do.
Can someone explain what the "stackful coroutine" term means (ideally with an example)? And how can one implement it?
A fiber isn't to some degree a stackful coroutine, it is a stackful coroutine.
A stackless coroutine does not have a its own stack, it uses the calling context's stack and therefore can only yield to the calling context from the top-level coroutine function. A stackful coroutine has its own stack, and so can yield to the calling context from anywhere.
As far as how to implement, I always liked Malte Skarupke's blog post on the subject: https://probablydance.com/2013/02/20/handmade-coroutines-for...
In Python, coroutines cannot yield from within another function call: if coroutine A calls function B, B cannot yield. In Lua, it's possible to yield a coroutine at any function depth: B can yield.
To implement something like this in a compiled language, you just need multiple stacks instead of the usual 1. Most architectures, such as x86, have a stack pointer register; when yielding a coroutine, just change the sp register to point to some other stack -- when resuming, restore the sp.
This is not a new concept. Pokémon on the gameboy did this for its UI fiber, for example.
I know you likely know this, but just for context. This is technically correct of course, B cannot yield, but not how you would use it in real life. If B needs to yield because it calls C which need to yield, then B needs to be a coroutine itself. This allows for a ‘nested yield’ where A, B, and C are all paused by yielding to their direct parent. Python made this explicit before async/await as you had to use “yield from” instead of just yield. With async/await that became “await”.
This does lead to what’s typically mentioned as the biggest disadvantage of stackless coroutines which is that you get parallel sets of functions, one async and one sync. This mostly means that IO and networking libraries end up being either sync or async but not both.
Some readers may have a question by now. What is the rationale behind the choices of the registers that need to be stored?
How do we write the "Applications own scheduler"?
Can someone tell me the difference from those to fibres?
But people have been playing with stackful coroutines in C++ for decades.
Fibres, goroutines, promises, futures, job queues, etc, are poor substitutes for Actors.
They are not necessarily substitutes, they are lower level primitives that allow more complex models, like Actors, to be implemented.
All execution models have trade offs; and sometimes we might prefer an execution model without deadlock, livelock and starvation. So for a general purpose language, a complex model like Actors is ideally a library and not enforced as the only way of achieving concurrency.
Just like with FP and LP, I rather have something close enough, than nothing at all.