Re: [boost] Continuations in C++

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2007-09-28 04:38:16

On 9/27/07, Daniel Gutson <danielgutson_at_[hidden]> 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.