tag:blogger.com,1999:blog-5246987755651065286.post5093085452842229910..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 12-21-12 - Coroutine-centric Architecturecbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-5246987755651065286.post-48839282826884662392013-01-29T23:26:20.924-08:002013-01-29T23:26:20.924-08:00boost.context is part of boost-libraries since 1.5...boost.context is part of boost-libraries since 1.51 (boost.org).<br />boost.coroutine will be released with boost-1.53 (next week).<br />boost.fiber is available at github.com/olk/boost-fiber (but not ready yet, need some fixes and docu).Oliverhttps://www.blogger.com/profile/03216114170999450165noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-66903057292377218302013-01-29T11:21:37.509-08:002013-01-29T11:21:37.509-08:00Cool. Where can I download boost.context and boos...Cool. Where can I download boost.context and boost.fiber ?<br /><br />"boost.fiber does not require something like a GC."<br /><br />I didn't meant that implementing coroutines requires GC. I meant that I believe a realistic/usable larger application that is coroutine-centric should use GC, otherwise the lifetime management in micro-coroutines is too heinous.<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-70139009564566793792013-01-29T10:51:43.158-08:002013-01-29T10:51:43.158-08:00Interestingly I'm currently working on such a ...Interestingly I'm currently working on such a library - it's called boost.fiber.<br /><br />I would describe coroutines as a language feature and fibers as resource related (similar to threads).<br /><br />boost.fiber uses boost.context (context swapping/switching) and provides an interface similar to boost.thread, e.g. the library contains classes like mutex, condition, future<>, unique_lock etc. (but does not use pthread or Windows-thread related stuff).<br /><br />boost.fiber does not require something like a GC.<br /><br />Synchronizing fibers running in different threads is possible too.<br /><br />Work-steeling (usually used in thread-pools) can be done via fiber-steeling, e.g. one thread can steel (migrate) fibers from another thread.<br /><br />If I get split-stack managed then we have an go-pedant in C++ too.Oliverhttps://www.blogger.com/profile/03216114170999450165noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-23835457641510056402012-12-22T11:54:03.196-08:002012-12-22T11:54:03.196-08:00Most co-routine implementations I've seen lack...Most co-routine implementations I've seen lack the ability to carefully set up and share data between the "scheduler" and the coroutine itself.<br /><br />What I mean is - you can always make coroutines function by saving the entire execution context of the coroutine every time you switch away, and restoring it every time you switch back. But if you're switching between coroutines that share a lot of state, it's not necessarily very efficient.<br /><br />Ideally you'd have some notion of "sibling" coroutines - and the notion that when you yield you're only going to yield to a sibling, not to just any coroutine anywhere in the entire program. In 99% of cases the sibling is exactly the same code, just in a different instance. That allows the compiler to make certain assumptions about which registers are live, which will be dirtied, etc.<br /><br />It also allows the compiler to schedule coroutines into each other. For example - you know that whenever you start a coroutine of this family, the first thing it does is run a prologue that loads the top four stack entries into registers r0-r3 - this happens on every entry point to the coroutine. OK, so if you're somewhere that you know is heading for a switch to this type of coroutine, you can do this there, rather than wait until you're actually in the coroutine wanting to use those registers as addresses or whatever.<br /><br />In functions there's already some of the above functionality in function signatures (i.e. a particular signature makes a family of functions - you don't know which one you're going to call, but it's one of only a few) - but it seems like the same concept would be useful in coroutines.<br /><br />The above was all learned doing pixel shaders as coroutines of course - you get a substantial perf increase.Tom Forsythhttps://www.blogger.com/profile/01368434932814120414noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-6016349416361197332012-12-22T09:55:58.587-08:002012-12-22T09:55:58.587-08:00Talk on Concurrency in Go that shows off the primi...Talk on Concurrency in Go that shows off the primitives <a href="http://www.youtube.com/watch?v=f6kdp27TYZs" rel="nofollow">here</a>.Fabian 'ryg' Giesenhttps://www.blogger.com/profile/13685994980026854143noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-18661340833129933832012-12-22T04:27:42.604-08:002012-12-22T04:27:42.604-08:00On the non-functional side, there's a few new ...On the non-functional side, there's a few new imperative languages with that kind of design too, most prominently Go (www.golang.org) and Rust (www.rust-lang.org). Both check pretty much every point on your check list, with one distinction: both don't automatically promote return values to futures. They do both have built-in communication primitives though: Go has channels and Rust pipes, and the idiomatic way to handle this in both languages is to pass in a channel/pipe end point to the coroutine and send a value once it's done. (Both also have lambdas so it's easy to wrap a function that doesn't send its return value that way).<br /><br />Both don't have batch-starting (that I've seen) or any explicit dependency tracking between coroutines; again they instead phrase this in terms of the communication primitives: If you're waiting for something to finish before you start a dependent event, make it send you a dummy value on completion. Both do have async waits for multiple events at once (usually wait-any, not wait-all).<br /><br />Both have proper coroutines with stack-saving and small default stack size (~4k). Both use segmented stacks that grow dynamically and aren't necessarily contiguous (so there's no need to reserve large amounts of address space per coroutine).<br /><br />Neither will expose any of the OS threading primitives by default, and instead use proper async versions that yield instead of blocking.<br /><br />Both are GC'ed; Rust has a peculiar but interesting model where everything defaults to stack allocated (with compiler-verified memory safety, i.e. pointers to stack variables may not escape their assigned lifetime) and there's two separate heaps: the "managed heap", which is per-coroutine and fully GC'ed (the compiler enforces that such values don't become visible to other coroutines), and the "exchange heap", which is shared but may only contain objects that have exactly one pointer to them (similar to std::unique_ptr). Because the managed heaps are all separate, they can be GCed on a per-coroutine basis without problems. Interesting model, but I have no idea how well it works in practice. Go is just "GC everything that can't be on the stack", which is less efficient but also a lot simpler to reason about :)<br /><br />Both don't have any locks per object, and instead emphasize using the built-in comm primitives over shared memory. Seems like the right call for normal usage. Go now also comes with a built-in race checker courtesy of Dmitry Vyukov for the parts that do use shared memory.<br /><br />Both express dependencies by arguments and/or explicit passing of comm channels (which are value types).<br /><br />Haven't done anything with Rust yet. I've done some simple stuff with Go and really like it so far.Fabian 'ryg' Giesenhttps://www.blogger.com/profile/13685994980026854143noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-25831324696628887382012-12-22T03:27:19.757-08:002012-12-22T03:27:19.757-08:00Also, look at Racket (for example) which has a nic...Also, look at Racket (for example) which has a nice (but not usually efficient unfortunately due to GC issues) and consistent way to do multi-threaded computations all along with continuations basically mixing future/touch to off-load expressions in other threads and call/cc to emulate coroutine (and exceptions, return...)<br /><br />At least, it is a good inspiration :-) and syntactically beautiful.<br /><br />bouliiiihttps://www.blogger.com/profile/05579514597684961397noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-22892966959735475802012-12-22T03:16:39.323-08:002012-12-22T03:16:39.323-08:00CPS code transformation is basically what you want...CPS code transformation is basically what you want here.<br /><br />CPS is basically the way code is transformed (by the compiler not a human :-)) in most Scheme compilers. Each function is given the next function to execute. This make call/cc free and therefore one shot continuation (coroutine) also free.<br /><br />Note that this requires proper tail-call recursion optimization but you do not need to save the stack.<br /><br />However, while it is pretty straightforward in scheme where you only have expressions and only very few primary constructs (lambda, if, set!, defime mostly), I am not sure CPS transform is doable in C which has statement and expressions.bouliiiihttps://www.blogger.com/profile/05579514597684961397noreply@blogger.com