6 ms·

A hybrid thread / fiber task scheduler written in C++ 11

deleted 7y ago
[deleted]
aidos 7y ago
I’d not heard the term fiber before react reworked their framework around it. Is it a more general thing, and is there a good resource to learn about the theory?
- htfy96 7y ago
  Personally I recommend Distinguishing coroutines and fibers (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4024.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n402...) In short: - The key difference between fibers and kernel threads is that fibers use cooperative context switching - When a coroutine yields, it passes control directly to its caller (or, in the case of symmetric coroutines, a designated other coroutine). - When a fiber blocks, it implicitly passes control to the fiber scheduler. Coroutines have no scheduler because they need no scheduler
  - Waterluvian 7y ago
    Is that kind of like how gevent for Python works? I thought they were coroutines but there's a scheduler, I think.
    - icebraining 7y ago
      Fibers can be built (and according to the paper, in C++ Boost they are) on top of coroutines, and that's essentially what both gevent and asyncio do.
- scottlamb 7y ago
  I don't think "fiber" has a universally agreed definition, which makes these things super confusing to read without clarification. It's hard to come up with a good definition and stick to it because people keep coming up with new variations. An interesting case is a different Google fiber library, not open-sourced but described in a public talk. [1] Real kernel threads but (mostly) scheduled in userspace via new syscalls [2] that suspend the current thread and unsuspend a userspace-chosen other thread. The idea is that most of the overhead of kernel threads is the scheduling and userspace has the ability to make a quick good choice. [3] Thus you can get most of the CPU performance of an async implementation but the relatively easy-to-read callback-free code of a threaded implementation. Anyway, people can disagree on what to call such a combination. [1] https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw [2] the rseq stuff described in that talk has been upstreamed [4] but the switchto stuff still hasn't. [3] I'm not sure if the performance argument is as strong since the Meltdown/Spectre mitigations added to the performance cost of any syscall. [4] https://www.efficios.com/blog/2019/02/08/linux-restartable-sequences/ https://www.efficios.com/blog/2019/02/08/linux-restartable-s...
- magicalhippo 7y ago
  Not sure about the term, but I know Windows has had them for almost two decades[1], so hardly a newfangled concept. Here's[2] a fun/interesting 15 year old blog post explaining some of the use cases and pitfalls of using Win32 fibers. [1]: https://jeffpar.github.io/kbarchive/kb/128/Q128531/ https://jeffpar.github.io/kbarchive/kb/128/Q128531/ (CreateFiber) [2]: https://docs.microsoft.com/en-us/archive/blogs/larryosterman/why-does-win32-even-have-fibers https://docs.microsoft.com/en-us/archive/blogs/larryosterman...
- eps 7y ago
  "Fibers" is a term for manually-scheduled threads that was used in Windows at least since Windows 2000. Niche feature, but it was fully documented and all.
aninteger 7y ago
What advantages does this have over say, just using pthreads and the Linux kernel to handle the scheduling? I guess you can hit higher performance by not making extra system calls, right? What other benefits would there be?
- api 7y ago
  Mostly that and a lack of context switches. Async programming is really a fine grained hand written way to do fibers. Goroutines are basically fibers too and are incredibly cheap.
- headlessclayton 7y ago
  Author here. Marl was originally written for SwiftShader¹ a pure-software implementation of the Vulkan graphics API, which needs to run on desktop and embedded devices, with CPUs ranging from 2 to many cores. SwiftShader executes a number of parallel rasterization tasks which have complex blocking dependencies on one another. Marl attempts to simplify the problem of running and synchronizing tasks. It shamelessly borrows quite a few concepts from golang, simplifying fan-out, fan-in style problems. The main reason of why not just use pthreads / std::thread really comes down to blocking tasks. Using regular threads, you either need to know your dependency graph ahead of time to ensure tasks are executed in dependency order (blockless), or you likely end up spinning up many more threads than you actually need to allow things to block and wait on others to complete. SwiftShader has tight requirements on the number of threads we're allowed to create, so Marl was our solution. Marl is even capable of running single-threaded with no code changes to the tasks. It's worth mentioning we also evaluated other scheduler solutions using completion callbacks, but "callback hell" was something we were keen to avoid. I'm still looking into Marl optimizations, but it is already pretty fast. Fiber switching is notably faster than OS context switching for many of the benchmarks we've done. ¹ https://github.com/google/swiftshader https://github.com/google/swiftshader
  - vkaku 7y ago
    It's a lot of things (like tracing, defer etc), but for all practical purposes, the code is simple and straightforward to use. Thank you author. I wish you could create a version based setJmp/longJmp if instrinsics weren't available (say on a different processor, like AVR). That could really help!
m0zg 7y ago
Every time someone writes something like this, I just wish Google open sourced its Fibers - that thing is sublime. Unfortunately that's not going to happen as the niceties that implementation affords require a modified kernel. I think I saw a presentation describing Fibers a few years back by one of its authors, but it's darn near impossible to find because there's also "Google Fiber". If someone has a link, please share. Fibers sort of opened up my mind to what's possible in this space if you go deeper than people usually go. They're also a source of dissatisfaction with how this turns out when people don't go as deep as the authors of Fibers did. https://github.com/abseil/abseil-cpp/issues/5 https://github.com/abseil/abseil-cpp/issues/5
- xmo 7y ago
  Had a good experience using boost::fiber https://github.com/boostorg/fiber https://github.com/boostorg/fiber
- dvirsky 7y ago
  This is a Google project though. I haven't dug too deeply but maybe it does share something with the internal fibers? (Which I agree are just amazing)
- Blackthorn 7y ago
  It's hard to overemphasize just how amazing that fiber implementation really is. It's completely transformed my view of programming concurrency. That it's been described in a public paper but hasn't been able to be open sourced is a damn shame. This is the paper: https://www.linuxplumbersconf.org/2013/ocw/system/presentations/1653/original/LPC%20-%20User%20Threading.pdf https://www.linuxplumbersconf.org/2013/ocw/system/presentati...
- nwlieb 7y ago
  Could you describe what makes the Google Fibers so nice? I'm also really curious why they require modifications to the Linux kernel. My first guess would be stronger integration with the IO model at the syscall boundary (similar to io_uring). Edit: is this the talk your referring to? https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
cheez 7y ago
I don't particularly like the name defer. It seems to operate similarly to Boost ScopeExit but the name does not imply that.
- diath 7y ago
  The name is likely inspired by Go's defer statement which works in a similar fashion: https://blog.golang.org/defer-panic-and-recover https://blog.golang.org/defer-panic-and-recover
  - cheez 7y ago
    It is, but we are in C++
banachtarski 7y ago
C++11 is so 2011...
deleted 7y ago
[deleted]

deleted 7y ago

[deleted]

I’d not heard the term fiber before react reworked their framework around it. Is it a more general thing, and is there a good resource to learn about the theory?

htfy96 7y ago
Personally I recommend Distinguishing coroutines and fibers (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4024.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n402...) In short: - The key difference between fibers and kernel threads is that fibers use cooperative context switching - When a coroutine yields, it passes control directly to its caller (or, in the case of symmetric coroutines, a designated other coroutine). - When a fiber blocks, it implicitly passes control to the fiber scheduler. Coroutines have no scheduler because they need no scheduler
- Waterluvian 7y ago
  Is that kind of like how gevent for Python works? I thought they were coroutines but there's a scheduler, I think.
  - icebraining 7y ago
    Fibers can be built (and according to the paper, in C++ Boost they are) on top of coroutines, and that's essentially what both gevent and asyncio do.
scottlamb 7y ago
I don't think "fiber" has a universally agreed definition, which makes these things super confusing to read without clarification. It's hard to come up with a good definition and stick to it because people keep coming up with new variations. An interesting case is a different Google fiber library, not open-sourced but described in a public talk. [1] Real kernel threads but (mostly) scheduled in userspace via new syscalls [2] that suspend the current thread and unsuspend a userspace-chosen other thread. The idea is that most of the overhead of kernel threads is the scheduling and userspace has the ability to make a quick good choice. [3] Thus you can get most of the CPU performance of an async implementation but the relatively easy-to-read callback-free code of a threaded implementation. Anyway, people can disagree on what to call such a combination. [1] https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw [2] the rseq stuff described in that talk has been upstreamed [4] but the switchto stuff still hasn't. [3] I'm not sure if the performance argument is as strong since the Meltdown/Spectre mitigations added to the performance cost of any syscall. [4] https://www.efficios.com/blog/2019/02/08/linux-restartable-sequences/ https://www.efficios.com/blog/2019/02/08/linux-restartable-s...
magicalhippo 7y ago
Not sure about the term, but I know Windows has had them for almost two decades[1], so hardly a newfangled concept. Here's[2] a fun/interesting 15 year old blog post explaining some of the use cases and pitfalls of using Win32 fibers. [1]: https://jeffpar.github.io/kbarchive/kb/128/Q128531/ https://jeffpar.github.io/kbarchive/kb/128/Q128531/ (CreateFiber) [2]: https://docs.microsoft.com/en-us/archive/blogs/larryosterman/why-does-win32-even-have-fibers https://docs.microsoft.com/en-us/archive/blogs/larryosterman...
eps 7y ago
"Fibers" is a term for manually-scheduled threads that was used in Windows at least since Windows 2000. Niche feature, but it was fully documented and all.

aninteger 7y ago

What advantages does this have over say, just using pthreads and the Linux kernel to handle the scheduling? I guess you can hit higher performance by not making extra system calls, right? What other benefits would there be?

api 7y ago
Mostly that and a lack of context switches. Async programming is really a fine grained hand written way to do fibers. Goroutines are basically fibers too and are incredibly cheap.
headlessclayton 7y ago
Author here. Marl was originally written for SwiftShader¹ a pure-software implementation of the Vulkan graphics API, which needs to run on desktop and embedded devices, with CPUs ranging from 2 to many cores. SwiftShader executes a number of parallel rasterization tasks which have complex blocking dependencies on one another. Marl attempts to simplify the problem of running and synchronizing tasks. It shamelessly borrows quite a few concepts from golang, simplifying fan-out, fan-in style problems. The main reason of why not just use pthreads / std::thread really comes down to blocking tasks. Using regular threads, you either need to know your dependency graph ahead of time to ensure tasks are executed in dependency order (blockless), or you likely end up spinning up many more threads than you actually need to allow things to block and wait on others to complete. SwiftShader has tight requirements on the number of threads we're allowed to create, so Marl was our solution. Marl is even capable of running single-threaded with no code changes to the tasks. It's worth mentioning we also evaluated other scheduler solutions using completion callbacks, but "callback hell" was something we were keen to avoid. I'm still looking into Marl optimizations, but it is already pretty fast. Fiber switching is notably faster than OS context switching for many of the benchmarks we've done. ¹ https://github.com/google/swiftshader https://github.com/google/swiftshader
- vkaku 7y ago
  It's a lot of things (like tracing, defer etc), but for all practical purposes, the code is simple and straightforward to use. Thank you author. I wish you could create a version based setJmp/longJmp if instrinsics weren't available (say on a different processor, like AVR). That could really help!

m0zg 7y ago

Every time someone writes something like this, I just wish Google open sourced its Fibers - that thing is sublime. Unfortunately that's not going to happen as the niceties that implementation affords require a modified kernel. I think I saw a presentation describing Fibers a few years back by one of its authors, but it's darn near impossible to find because there's also "Google Fiber". If someone has a link, please share. Fibers sort of opened up my mind to what's possible in this space if you go deeper than people usually go. They're also a source of dissatisfaction with how this turns out when people don't go as deep as the authors of Fibers did. https://github.com/abseil/abseil-cpp/issues/5 https://github.com/abseil/abseil-cpp/issues/5

xmo 7y ago
Had a good experience using boost::fiber https://github.com/boostorg/fiber https://github.com/boostorg/fiber
dvirsky 7y ago
This is a Google project though. I haven't dug too deeply but maybe it does share something with the internal fibers? (Which I agree are just amazing)
Blackthorn 7y ago
It's hard to overemphasize just how amazing that fiber implementation really is. It's completely transformed my view of programming concurrency. That it's been described in a public paper but hasn't been able to be open sourced is a damn shame. This is the paper: https://www.linuxplumbersconf.org/2013/ocw/system/presentations/1653/original/LPC%20-%20User%20Threading.pdf https://www.linuxplumbersconf.org/2013/ocw/system/presentati...
nwlieb 7y ago
Could you describe what makes the Google Fibers so nice? I'm also really curious why they require modifications to the Linux kernel. My first guess would be stronger integration with the IO model at the syscall boundary (similar to io_uring). Edit: is this the talk your referring to? https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw

cheez 7y ago

I don't particularly like the name defer. It seems to operate similarly to Boost ScopeExit but the name does not imply that.

diath 7y ago
The name is likely inspired by Go's defer statement which works in a similar fashion: https://blog.golang.org/defer-panic-and-recover https://blog.golang.org/defer-panic-and-recover
- cheez 7y ago
  It is, but we are in C++

banachtarski 7y ago

C++11 is so 2011...

deleted 7y ago

[deleted]