Python-style generators in C++ (part 1)

boost.context

Since version 1.51 Boost includes a new, very cool library: Boost.Context, a low-level library for manual switching of execution context within single thread. It allows for implementing corountines and similar constructs. Boost.Context is indeed used to implement Boost.Corountine.
The library provides only one data structure and two functions.

• fcontext_t

  is an opaque structure which encapsulates execution context: CPU registers and stack

• fcontext_t * make_fcontext( void * sp, std::size_t size, void(* fn)(intptr_t) )

  creates new context

• intptr_t jump_fcontext( fcontext_t * old_context, fcontext_t const* new_context, intptr_t vp, bool preserve_fpu = true)

  switches to new_context, preserving the old one in old_context

This is how these can be used to implement very basic coroutines:

#include <boost/context/all.hpp>

#include <iostream>

boost::context::fcontext_t main_context; // will hold the main execution context

boost::context::fcontext_t* new_context = nullptr; // will point to the new context

static const int STACK_SIZE= 64*1024; // completely arbitrary value

void fun(intptr_t) // the singature has to be like this

{

    for(intptr_t i = 0;; i++)

    {

        std::cout <<"fun, i=" << i << std::endl;

        boost::context::jump_fcontext(new_context, &main_context, i*10); // switch back to the main context

    }

    // jump_fcontext MUST be the last executed statement. The function can not return, nor throw an exception!

}

int main(int , char** )

{

    // allocate stack for new context

    char* stack = new char[STACK_SIZE];

    // make a new context. The returned fcontext_t is created on the new stack, so there is no need to delete it

    new_context = boost::context::make_fcontext(

                stack + STACK_SIZE, // new stack pointer. On x86/64 it hast be the TOP of the stack (hence the "+ STACK_SIZE")

                STACK_SIZE,

                fun);

    // switch to the new context several times

    for(intptr_t i = 0; i < 5; i++)

    {

        intptr_t ret = boost::context::jump_fcontext(&main_context, new_context, 0);

        std::cout << "ret=" << ret << std::endl;

    }

    // cleanup

    delete[] stack;

}

And the output is:

fun, i=0
ret=0
fun, i=1
ret=10
fun, i=2
ret=20
fun, i=3
ret=30
fun, i=4
ret=40

In the above example the functions main and fun are executed simultaneously, and the state of one is frozen when the other is running.
This is very basic example. Let's now try to use Boost.Context to create something similar to Python's generators.

Python generators

Python's yield statement allows for execution function in a private context, just like in the C++ example above.

#!/usr/bin/env python

def fibonacci():

    last = 1

    current = 1

    while(True):

        yield current

        nxt = last + current

        last = current

        current = nxt

N = 10

print('first %d numbers of fibonacci sequence:' % N)

generator = fibonacci()

for i in range(N):

    print(generator.next())

The output is:

first 10 numbers of fibonacci sequence:
1
2
3
5
8
13
21
34
55
89

C++ implementation, phase 1

Let's try to make the code from the first C++ example look and behave similar to the python code. I'll start by hiding all the ugly details of Boost.Context behind simple functions.

#include <boost/context/all.hpp>

#include <iostream>

boost::context::fcontext_t main_context; // will hold the main execution context

boost::context::fcontext_t* new_context = nullptr; // will point to the new context

static const int STACK_SIZE= 64*1024; // completely arbitrary value

char* stack = nullptr;

void init(void(* fun)(intptr_t))

{

    // allocate stack for new context

    char* stack = new char[STACK_SIZE];

    // make a new context. The returned fcontext_t is created on the new stack, so there is no need to delete it

    new_context = boost::context::make_fcontext(

                stack + STACK_SIZE, // new stack pointer. On x86/64 it hast be the TOP of the stack (hence the "+ STACK_SIZE")

                STACK_SIZE,

                fun);

}

void cleanup()

{

    delete stack;

    stack = nullptr;

    new_context = nullptr;

}

intptr_t next()

{

    return boost::context::jump_fcontext(&main_context, new_context, 0); // switch to function context

}

void yield(intptr_t value)

{

    boost::context::jump_fcontext(new_context, &main_context, value); // switch back to the main context

}

void fibonacci(intptr_t) // the singature has to be like this

{

    intptr_t last = 1;

    intptr_t current = 1;

    for(;;)

    {

        yield(current);

        intptr_t nxt = last + current;

        last = current;

        current = nxt;

    }

}

int main(int , char** )

{

    init(fibonacci);

    const int N = 10;

    std::cout << "first " << N << " numbers of fibonacci sequence:" << std::endl;

    for(int i = 0; i < N; i++)

    {

        std::cout << next() << std::endl;

    }

    cleanup();

}

The code is still unusable in real life, but the C++ fibonacci function looks almost identical to the python equivalent, and it produces exactly the same output!

In part 2 I'm turning in into working, usable, almost-production-ready C++ code!