nimforum mirror - Coroutine support?

Russ (orginal) [2013-05-21T17:02:08+02:00] view original

Hi,

I'm evaluating Nimrod for possible use on a project. I see that it has yield with generators, but does it have proper coroutine support? Or something similar for lightweight threads/fibers?

Best regards, Russ

Araq (orginal) [2013-05-21T18:05:54+02:00] view original

The manual contains an example how to setup a tasking system: http://nimrod-code.org/manual.html#first-class-iterators

We also have C#-like async/await macros in the works which provide a nicer syntax than iterator x {.closure.} but it didn't make it into 0.9.2.

Russ (orginal) [2013-05-21T18:39:18+02:00] view original

Thanks for the fast reply! This is great, but it still seems more like a generator instead of a coroutine, since it only supports one level of recursion. I'm thinking of something like Lua coroutines or boost context/coroutine, where you can yield inside of (potentially nested) functions and it freezes the stack and does a context switch (or similar). Would something like that be possible?

Araq (orginal) [2013-05-21T19:29:04+02:00] view original

Not in the short-term. Stack capturing is expensive to do (in a portable way at least) and it needs support from the GC. But Nimrod's generators are good enough for a lot of use cases, ymmv of course.

Russ (orginal) [2013-05-22T09:59:58+02:00] view original

Ok, so what if I try to do it from the other direction. I could have Nimrod target C++ and use Boost::Context as an external library from Nimrod for switching between coroutines (or just port Context to C, it's a really simple lib). If you're not familiar with it, it creates a separate stack for each coroutine and saves/loads registers and stack frames on switch. However, if it's creating stacks, will I run into problems with the GC? I assume the GC does a stack scan for references.

Araq (orginal) [2013-05-22T23:30:38+02:00] view original

Indeed that's the missing piece: The GC needs to know about every living stack. This also effectively means that the stack is not contiguous anymore for the write barrier which causes some headaches. There are essentially 3 solutions:

Use the mark&sweep GC which doesn't require any write barrier. I wouldn't take this route, but it is the easiest to get started. However even this GC needs to know about your additional stacks.

Mark the stack that's switched from and thus to become inactive, that is call GC_ref for every slot in the stack that looks like a traced pointer. If this stack is deallocated GC_unref needs to be invoked for every slot in the stack that has been GC_ref'ed. This solution makes stack switching an O(stack size) operation.

Modify the write barrier so that it traverses the list of active stacks. This looks much preferable than solution (2) but whether it is faster really depends on the amount of context switches that you perform per GC run.

Most helpful would be if all of your stacks live in a single contiguous block of memory. Then things become much easier.

I'm willing to provide you all the necessary GC hooks to make it work. Things would be easier if you join the IRC channel, but in any case, just tell me what route you want to try.

Russ (orginal) [2013-05-24T09:16:12+02:00] view original

Thanks, seems like 3 would be the best. It's possible that the stacks could be placed in a contiguous block of memory using some kind of pooling, but within each stack there would likely be a large chunk of dead space. I think it would probably make the most sense performance-wise to give the GC a range for each stack to scan (pointer to bottom and top, or something like that). I would defer to you on that, though, I'm not at all familiar with your GC internals. I'll head over to the IRC channel this weekend.

bibhas (orginal) [2013-05-28T14:21:49+02:00] view original

Any updates on this guys? I'm looking to use this coroutine library https://github.com/mikewei/micoro but I'm not sure how I could go about doing that without screwing up with the GC.

Araq (orginal) [2013-05-28T22:27:19+02:00] view original

Sorry, no further progress has been made. (Russ didn't show up in the channel). The way to get this feature is to join the channel and nag me about it.

kt (orginal) [2013-06-08T12:06:26+02:00] view original

I've successfuly used posix makecontext/swapcontext (fairly portable, no need for crazy custom libraries) in Nimrod, however only refcounting gc seems to work reasonably.

Options:

use boehm and allocate coro stacks on stack of your main thread

use reference cycles, wait until it explodes and nag Araq in github issue you need API for additing custom GC roots :)

Araq (orginal) [2013-06-08T18:42:19+02:00] view original

I've successfuly used posix makecontext/swapcontext (fairly portable, no need for crazy custom libraries) in Nimrod, however only refcounting gc seems to work reasonably.

That sounds you got lucky, it can't work reliably without write barrier modifications.

kt (orginal) [2013-06-08T23:52:34+02:00] view original

Indeed I lucked out. Calling GC_fullCollect explicitly will trigger crash with all gc (ie choice of gc only modifies the likelyhood of something bad happening).

https://github.com/Araq/Nimrod/issues/472

rndbit (orginal) [2013-08-15T10:31:46+02:00] view original

some time ago i came across very crafty coroutine implementation in c++ - boost asio coroutines: http://www.boost.org/doc/libs/1_54_0_beta1/boost/asio/coroutine.hpp this intrigued me a lot because this implementation does not use any expensive context switching, jong jumps, assembly, is 100% portable and has tiny tiny overhead of 1 integer to keep coroutine state. as i needed more features i extended it to have coroutines called automatically and added sleep support. http://paste2box.com/s/#/file/0KHVsFa-ehXFTxPhFoIdOaDgRcc/frAQBc8Wsa.h/?p=0eBouBE2zxVdbSCrxHxBuG2RAIgX disclaimer: its crude and hasty implementation of things i needed and its no longer cross-platform, but then again i needed it on windows. this is just an example.

so.. cant nimrod do something like this too? the only ugly thing is that programmer has to manually call reenter(coroutine_context){} and it should contain coroutine code. and only limitation - local variables can be declared before reenter(), but not inside. essentially reenter() is a switch and each yeld() is case, so thats the reason.

Araq (orginal) [2013-08-15T12:29:20+02:00] view original

That's pretty much how closure iterators are implemented. Try to yield from a recursive function to see the limits of this approach.

zahary (orginal) [2013-08-15T17:24:26+02:00] view original

Besides the 3 solutions proposed on the first page, we have discussed at least 2 other possible solutions (in increasing level of craziness):

Getting rid of UnsureAsgnRef by compiling 2 copies of some "var ref" functions or propagating the necessary information in additional flags to the procs.

Allocating stack frames on the heap in a fashion that will allow you to maintain stack "top" and "bottom" in an efficient way.

Mirror of forum.nim-lang.org

155 :: Coroutine support?