On 9/25/07, Daniel Gutson <danielgutson@gmail.com> wrote:

Hi Mathias, thanks for answering.

I found such library in Vault, so it´s not in another place, right?

You mean boost-coroutine in the concurrency folder of the vault? [http://tinyurl.com/278qca] You can also find the documentation here: http://www.crystalclearsoftware.com/soc/coroutine/index.html And access the SVN here: http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/coroutine Note that the name is misleading. Boost.Coroutine is not yet a boost library. I haven't even submitted it for review yet (even if it is practically finished and the documentation almost done) for lack of time.

I found also the continuation namespace, but as far as I saw, yes this is a generalization of the concept, but focused in coroutines, and somehow (as far as I understand) in concurrent programming.

Well, coroutines and one-shot continuations are dual as there is a simple transformation from one to the other [1]. On the other hand, the word 'continuation' alone in computer science usually refers to true restartable continuations which are *extremely* hard to do in C++ (you would need a way to copy the stack reliably). The UNIX fork() syscall is what get closer to true continuations in the C world (except that it also copy the global state, but you can get around that). What you are showing in your example are simple stack less (you can't yield from inside a call stack) coroutines. My coroutine library supports the stackfull variant of coroutines. It cannot be implemented within the standard C++, so it uses a range of OS specific services (make_context and Win32 Fibers) or custom assembler. They could also be implemented fairly portably on top of boost.thread, but I haven't done so yet. I expect such an implementation to be fairly slow. Boost.coroutine is definitely not focused on concurrent programming. In fact the documentation states clearly that often coroutines are mistaken for poor man threads, which they are not. Threads and coroutines are orthogonal. One of the library example is in fact the classic factorial and it looks like this (namespaces stripped for simplicity): typedef coroutine<double()> coroutine_type; size_t factorial(coroutine_type::self& self) { double n = 0; double n_bang = 1; self.yield(n_bang); while(true) { n_bang = n_bang * ++n; self.yield(n_bang); } } int main() { coroutine_type fact(factorial); for(int i = 0; i <100; i++) std::cout <<i<<"!= "<<fact()<<"\n"; }

The concept I´m referring here (which, of course could be incorrect) is not related with concurrent programming, multithreading or iterators, but the ability to specify an execution flow without using a stack (I´m somewhat messed with embedding programming), and a neat support for iterative algorithms implementations.

Boost.Coroutine provides yield_next which is the equivalent of your set_next, but that is just syntactic sugar, because a coroutine library without yield_next is just as powerful one without. Yield_next could be emulated by just returning the next coroutine to jump to. I provide it in the library because it is slightly more efficient to be implement natively (you save a stack switch and an indirect call). BTW, yield next is just a more powerful variant of goto, which means that you are more likely of shooting yourself in the foot :) gpd [1] http://www.inf.puc-rio.br/~roberto/docs/corosblp.pdf

On 9/27/07, Daniel Gutson <danielgutson@gmail.com> wrote:

Hi Giovanni, thanks for answering too.

Sorry I don´t quote on your text, it´s easier for me to write simple conclusions.

- one of the goals of the small program I showed as example, was, as you mentioned, to be ´stack-less´, since this is thought for small embedded devices.

If with stack-less you mean you do not have a per-coroutine stack [1], yes, this might be a worthy goal. There upsides and downsides. The upsides are: - can be implemented with standard c++. - might give compilers a better chance to optimize (could in principle inline across yields). - better control over 'local object allocation' Downsides: - code inside the coroutine must be written with a coroutine in mind. With my coroutine library this isn't necessary. Think for example of running regex_match in a coroutine passing it an iterator that yields when there isn't enough data instead of blocking. This way you can use boost.regex in a non blocking fashion (i.e with asio), while with your approach you need to modify boost regex to handle this case. - you can't yield from inside a call stack. - manual local object allocation. You can't allocate objects that span the whole coroutine lifetime in the stack. You need to allocate them in a special area. If some of these objects have overlapping lifetimes, the compiler has a very hard job optimizing them, while it would be much easier if they where allocated on the stack.

- the most similar feature that you describe is the yield_next, since one of the things I wanted to avoid (in the ´client´ part) is the loop control (i.e. the ´while´), leaving it to the library part. That being said, is there any implementation sample of the factorial using yield_next?

No, I do not have one at the moment, but it is pretty straight forward. It would look similar to your example. I see that in this case you *really* want to do without a stack. Probably boost.coroutine is not for you.

- what are the ´overheads´ and (O.S.) dependencies of yield_next?

On the optimal assembler implementation, a bouch of push and pops and an indirect function call (wich is the most expensive instruction of the lot). The fiber implementation might or might not be slightly higher. The makecontext implementation is hopeless as it need to call into the kernel to change the sigmask (many order of magnitude slower).

- maybe the term ´continuation´ was not the best one for describing what I was trying to do.

Actually I think yes, it is, In a certain sense what are you trying to do is continuation passing style for control flow, using a function pointer + state as a continuation, and doing tail call optimization by hand. HTH, gpd [1] Just to clarify: I usually use the terms stackful and stackles terms to refer to coroutine that can or can't respectively yield from inside a call stack. You seem to use the term in the stackless-python sense, that is, emulating the local object stack outside of the C++ native stack.