Probably Dance

Coroutines are a way of doing cooperative multithreading where each context has it’s own stack. And they can be incredibly useful for games. (I’ll use the word context as the coroutine equivalent of a thread) The basic idea of a coroutine is that you can yield from a context in the middle of a function, and then you will continue exactly at that point when the coroutine gets called the next time.
Imagine that you want something to happen in a sequence, for example you want to spawn an enemy, show a text for two seconds, then kill the enemy and show another text for two seconds. A trivial implementation would be this:

void sudden_exploding_unit(const Vector3 & pos)
{
    std::unique_ptr<Entity> guy = spawn_entity(pos, "grunt.entity");
    sleep(1.0f);
    show_text(pos, "oh no he is exploding!", 2.0f);
    sleep(0.5f);
    explode(*guy);
    sleep(1.0f);
    show_text(pos, "well that was underwhelming", 2.0f);
}

Even though this code is simple, you would probably have a large amount of pain to implement this in a game engine, because a game can never block, and this code is sleeping all over the place. You’d probably end up writing some kind of state machine (maybe using a kismet-like scripting system) or if you’re a terrible person you’d use asynchronous callbacks. State machines can be a fine solution, but they introduce way too much infrastructure for such a trivial piece of code.

Enter coroutines. If your engine has coroutines, you can write exactly the above code. With very little downsides. Because you could just sleep like this:

void sleep(float seconds)
{
    while (seconds >= 0.0f)
    {
        yield(); // resume here next frame
        seconds -= global_dt;
    }
}

With the assumption that your coroutine gets called every frame.

The power of this is that you keep your callstack and your instruction pointer. Dijkstra wrote an article in 1968 about why the goto statement is harmful: The problem is, that it makes it difficult to determine the current state of the program. And as the this article points out, you can replace the word “goto” in that article with the term “asynchronous callback” and it would still be relevant. Basically it comes down to this: If you put a breakpoint in your code, how much information will you have? Asynchronous callbacks and state machines are only mildly better than the goto statement in this regard, in that it can be difficult to determine where the current state comes from.

Coroutines have less of a problem there because you are using the right tools to keep the information on how far along you are in the process: the instruction pointer and the callstack. The downside is that one function could have had many different entry points in it’s lifetime, but I don’t consider that a big problem.

Here’s a video where Nat Goodspeed of Linden Lab explains how they untangled their streaming code using coroutines. The issue with streaming code is that you typically have a update function which gets called every frame that looks like this:

void updated_request(stream_request & request)
{
    switch(request.status)
    {
    case NOT_STARTED:
        send_request(request);
        break;
    case WAITING_FOR_SERVER:
        if (request.start_time - global_currenttime > timeout)
        {
            cancel_request(request);
        }
        break;
    case RECEIVED:
        load_data(request);
        break;
    case LOADING:
        break;
    case LOADED:
        instantiate_object(request);
        break;
    }
}

Which still looks simple enough, but this function will grow forever. Sending a request to the server probably requires authentication. And you’ll have to decrypt and decompress the data. None of which must happen in the main thread. Of course you also have to be able to cancel your request at any moment.

Nat Goodspeed says that this function grew to 1800 lines in their codebase. Which is not too unlikely. And which is an unmaintainable mess, because it is much less clear than a 1800 line function which gets executed in order. At 16:23 in the video he explains a situation where they realized that a call inside of a loop was actually blocking. They were able to transition to a non-blocking equivalent by introducing a new state. Except since they were inside a loop they had to store the loop control variable somewhere and introduce even more complexity.

With coroutines you can rewrite the above function like this:

void handle_request(stream_request & request)
{
    if (send_request(request, timeout) == TIMED_OUT)
    {
        return;
    }
    load_data(request);
    instantiate_object(request);
}

And you just say that it is the responsibility of send_request to yield until it is finished or times out, which is a reasonable requirement.

Linden Lab uses boost::coroutine which offers a coroutine implementation for C++. The issue is that it is aiming to be a typical boost library.

For example here are all the includes you get merely for including “boost/coroutine/coroutine.hpp”:

include_only.o:include_only.cpp
boost/coroutine/coroutine.hpp
boost/coroutine/detail/default_context_impl.hpp
/usr/include/boost/config.hpp
/usr/include/boost/config/user.hpp
/usr/include/boost/config/select_compiler_config.hpp
/usr/include/boost/config/compiler/gcc.hpp
/usr/include/boost/config/select_stdlib_config.hpp
/usr/include/c++/4.7/cstddef
/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h
/usr/include/features.h
/usr/include/x86_64-linux-gnu/bits/predefs.h
/usr/include/x86_64-linux-gnu/sys/cdefs.h
/usr/include/x86_64-linux-gnu/bits/wordsize.h
/usr/include/x86_64-linux-gnu/gnu/stubs.h
/usr/include/x86_64-linux-gnu/gnu/stubs-64.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h
/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h
/usr/include/boost/config/no_tr1/utility.hpp
/usr/include/c++/4.7/utility
/usr/include/c++/4.7/bits/stl_relops.h
/usr/include/c++/4.7/bits/stl_pair.h
/usr/include/c++/4.7/bits/move.h
/usr/include/c++/4.7/bits/concept_check.h
/usr/include/c++/4.7/type_traits
/usr/include/c++/4.7/initializer_list
/usr/include/boost/config/stdlib/libstdcpp3.hpp
/usr/include/unistd.h
/usr/include/x86_64-linux-gnu/bits/posix_opt.h
/usr/include/x86_64-linux-gnu/bits/environments.h
/usr/include/x86_64-linux-gnu/bits/types.h
/usr/include/x86_64-linux-gnu/bits/typesizes.h
/usr/include/x86_64-linux-gnu/bits/confname.h
/usr/include/getopt.h
/usr/include/boost/config/select_platform_config.hpp
/usr/include/boost/config/platform/linux.hpp
/usr/include/c++/4.7/cstdlib
/usr/include/stdlib.h
/usr/include/x86_64-linux-gnu/bits/waitflags.h
/usr/include/x86_64-linux-gnu/bits/waitstatus.h
/usr/include/endian.h
/usr/include/x86_64-linux-gnu/bits/endian.h
/usr/include/x86_64-linux-gnu/bits/byteswap.h
/usr/include/xlocale.h
/usr/include/x86_64-linux-gnu/sys/types.h
/usr/include/time.h
/usr/include/x86_64-linux-gnu/sys/select.h
/usr/include/x86_64-linux-gnu/bits/select.h
/usr/include/x86_64-linux-gnu/bits/sigset.h
/usr/include/x86_64-linux-gnu/bits/time.h
/usr/include/x86_64-linux-gnu/sys/sysmacros.h
/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h
/usr/include/alloca.h
/usr/include/boost/config/posix_features.hpp
/usr/include/boost/config/suffix.hpp
boost/coroutine/detail/context_linux.hpp
boost/coroutine/detail/context_posix.hpp
/usr/include/boost/assert.hpp
/usr/include/assert.h
/usr/include/c++/4.7/iostream
/usr/include/c++/4.7/ostream
/usr/include/c++/4.7/ios
/usr/include/c++/4.7/iosfwd
/usr/include/c++/4.7/bits/stringfwd.h
/usr/include/c++/4.7/bits/postypes.h
/usr/include/c++/4.7/cwchar
/usr/include/wchar.h
/usr/include/stdio.h
/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h
/usr/include/x86_64-linux-gnu/bits/wchar.h
/usr/include/c++/4.7/exception
/usr/include/c++/4.7/bits/atomic_lockfree_defines.h
/usr/include/c++/4.7/bits/exception_ptr.h
/usr/include/c++/4.7/bits/exception_defines.h
/usr/include/c++/4.7/bits/nested_exception.h
/usr/include/c++/4.7/bits/char_traits.h
/usr/include/c++/4.7/bits/stl_algobase.h
/usr/include/c++/4.7/bits/functexcept.h
/usr/include/c++/4.7/bits/cpp_type_traits.h
/usr/include/c++/4.7/ext/type_traits.h
/usr/include/c++/4.7/ext/numeric_traits.h
/usr/include/c++/4.7/bits/stl_iterator_base_types.h
/usr/include/c++/4.7/bits/stl_iterator_base_funcs.h
/usr/include/c++/4.7/bits/stl_iterator.h
/usr/include/c++/4.7/debug/debug.h
/usr/include/c++/4.7/cstdint
/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdint.h
/usr/include/stdint.h
/usr/include/c++/4.7/bits/localefwd.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h
/usr/include/c++/4.7/clocale
/usr/include/locale.h
/usr/include/x86_64-linux-gnu/bits/locale.h
/usr/include/c++/4.7/cctype
/usr/include/ctype.h
/usr/include/c++/4.7/bits/ios_base.h
/usr/include/c++/4.7/ext/atomicity.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h
/usr/include/pthread.h
/usr/include/sched.h
/usr/include/x86_64-linux-gnu/bits/sched.h
/usr/include/x86_64-linux-gnu/bits/timex.h
/usr/include/x86_64-linux-gnu/bits/setjmp.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h
/usr/include/c++/4.7/bits/locale_classes.h
/usr/include/c++/4.7/string
/usr/include/c++/4.7/bits/allocator.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h
/usr/include/c++/4.7/ext/new_allocator.h
/usr/include/c++/4.7/new
/usr/include/c++/4.7/bits/ostream_insert.h
/usr/include/c++/4.7/bits/cxxabi_forced.h
/usr/include/c++/4.7/bits/stl_function.h
/usr/include/c++/4.7/backward/binders.h
/usr/include/c++/4.7/bits/range_access.h
/usr/include/c++/4.7/bits/basic_string.h
/usr/include/c++/4.7/ext/string_conversions.h
/usr/include/c++/4.7/cstdio
/usr/include/libio.h
/usr/include/_G_config.h
/usr/include/x86_64-linux-gnu/bits/stdio_lim.h
/usr/include/x86_64-linux-gnu/bits/sys_errlist.h
/usr/include/c++/4.7/cerrno
/usr/include/errno.h
/usr/include/x86_64-linux-gnu/bits/errno.h
/usr/include/linux/errno.h
/usr/include/x86_64-linux-gnu/asm/errno.h
/usr/include/asm-generic/errno.h
/usr/include/asm-generic/errno-base.h
/usr/include/c++/4.7/bits/functional_hash.h
/usr/include/c++/4.7/bits/hash_bytes.h
/usr/include/c++/4.7/bits/basic_string.tcc
/usr/include/c++/4.7/bits/locale_classes.tcc
/usr/include/c++/4.7/streambuf
/usr/include/c++/4.7/bits/streambuf.tcc
/usr/include/c++/4.7/bits/basic_ios.h
/usr/include/c++/4.7/bits/locale_facets.h
/usr/include/c++/4.7/cwctype
/usr/include/wctype.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h
/usr/include/c++/4.7/bits/streambuf_iterator.h
/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h
/usr/include/c++/4.7/bits/locale_facets.tcc
/usr/include/c++/4.7/bits/basic_ios.tcc
/usr/include/c++/4.7/bits/ostream.tcc
/usr/include/c++/4.7/istream
/usr/include/c++/4.7/bits/istream.tcc
/usr/include/boost/current_function.hpp
/usr/include/ucontext.h
/usr/include/x86_64-linux-gnu/sys/ucontext.h
/usr/include/signal.h
/usr/include/x86_64-linux-gnu/bits/signum.h
/usr/include/x86_64-linux-gnu/bits/siginfo.h
/usr/include/x86_64-linux-gnu/bits/sigaction.h
/usr/include/x86_64-linux-gnu/bits/sigcontext.h
/usr/include/x86_64-linux-gnu/bits/sigstack.h
/usr/include/x86_64-linux-gnu/bits/sigthread.h
/usr/include/boost/noncopyable.hpp
boost/coroutine/exception.hpp
/usr/include/c++/4.7/typeinfo
boost/coroutine/detail/posix_utility.hpp
/usr/include/c++/4.7/cstring
/usr/include/string.h
/usr/include/boost/type_traits.hpp
/usr/include/boost/type_traits/add_const.hpp
/usr/include/boost/type_traits/detail/type_trait_def.hpp
/usr/include/boost/type_traits/detail/template_arity_spec.hpp
/usr/include/boost/mpl/int.hpp
/usr/include/boost/mpl/int_fwd.hpp
/usr/include/boost/mpl/aux_/adl_barrier.hpp
/usr/include/boost/mpl/aux_/config/adl.hpp
/usr/include/boost/mpl/aux_/config/msvc.hpp
/usr/include/boost/mpl/aux_/config/intel.hpp
/usr/include/boost/mpl/aux_/config/gcc.hpp
/usr/include/boost/mpl/aux_/config/workaround.hpp
/usr/include/boost/detail/workaround.hpp
/usr/include/boost/mpl/aux_/nttp_decl.hpp
/usr/include/boost/mpl/aux_/config/nttp.hpp
/usr/include/boost/mpl/aux_/integral_wrapper.hpp
/usr/include/boost/mpl/integral_c_tag.hpp
/usr/include/boost/mpl/aux_/config/static_constant.hpp
/usr/include/boost/mpl/aux_/static_cast.hpp
/usr/include/boost/preprocessor/cat.hpp
/usr/include/boost/preprocessor/config/config.hpp
/usr/include/boost/mpl/aux_/template_arity_fwd.hpp
/usr/include/boost/mpl/aux_/preprocessor/params.hpp
/usr/include/boost/mpl/aux_/config/preprocessor.hpp
/usr/include/boost/preprocessor/comma_if.hpp
/usr/include/boost/preprocessor/punctuation/comma_if.hpp
/usr/include/boost/preprocessor/control/if.hpp
/usr/include/boost/preprocessor/control/iif.hpp
/usr/include/boost/preprocessor/logical/bool.hpp
/usr/include/boost/preprocessor/facilities/empty.hpp
/usr/include/boost/preprocessor/punctuation/comma.hpp
/usr/include/boost/preprocessor/repeat.hpp
/usr/include/boost/preprocessor/repetition/repeat.hpp
/usr/include/boost/preprocessor/debug/error.hpp
/usr/include/boost/preprocessor/detail/auto_rec.hpp
/usr/include/boost/preprocessor/tuple/eat.hpp
/usr/include/boost/preprocessor/inc.hpp
/usr/include/boost/preprocessor/arithmetic/inc.hpp
/usr/include/boost/mpl/aux_/config/lambda.hpp
/usr/include/boost/mpl/aux_/config/ttp.hpp
/usr/include/boost/mpl/aux_/config/ctps.hpp
/usr/include/boost/mpl/aux_/config/overload_resolution.hpp
/usr/include/boost/mpl/aux_/lambda_support.hpp
/usr/include/boost/type_traits/detail/type_trait_undef.hpp
/usr/include/boost/type_traits/add_cv.hpp
/usr/include/boost/type_traits/add_lvalue_reference.hpp
/usr/include/boost/type_traits/add_reference.hpp
/usr/include/boost/type_traits/is_reference.hpp
/usr/include/boost/type_traits/config.hpp
/usr/include/boost/type_traits/is_lvalue_reference.hpp
/usr/include/boost/type_traits/detail/bool_trait_def.hpp
/usr/include/boost/type_traits/integral_constant.hpp
/usr/include/boost/mpl/bool.hpp
/usr/include/boost/mpl/bool_fwd.hpp
/usr/include/boost/mpl/integral_c.hpp
/usr/include/boost/mpl/integral_c_fwd.hpp
/usr/include/boost/type_traits/detail/bool_trait_undef.hpp
/usr/include/boost/type_traits/is_rvalue_reference.hpp
/usr/include/boost/type_traits/ice.hpp
/usr/include/boost/type_traits/detail/yes_no_type.hpp
/usr/include/boost/type_traits/detail/ice_or.hpp
/usr/include/boost/type_traits/detail/ice_and.hpp
/usr/include/boost/type_traits/detail/ice_not.hpp
/usr/include/boost/type_traits/detail/ice_eq.hpp
/usr/include/boost/type_traits/add_pointer.hpp
/usr/include/boost/type_traits/remove_reference.hpp
/usr/include/boost/type_traits/broken_compiler_spec.hpp
/usr/include/boost/type_traits/add_rvalue_reference.hpp
/usr/include/boost/type_traits/is_void.hpp
/usr/include/boost/type_traits/add_volatile.hpp
/usr/include/boost/type_traits/aligned_storage.hpp
/usr/include/boost/aligned_storage.hpp
/usr/include/boost/type_traits/alignment_of.hpp
/usr/include/boost/type_traits/intrinsics.hpp
/usr/include/boost/type_traits/is_same.hpp
/usr/include/boost/type_traits/is_volatile.hpp
/usr/include/boost/type_traits/detail/cv_traits_impl.hpp
/usr/include/boost/type_traits/detail/size_t_trait_def.hpp
/usr/include/boost/mpl/size_t.hpp
/usr/include/boost/mpl/size_t_fwd.hpp
/usr/include/boost/type_traits/detail/size_t_trait_undef.hpp
/usr/include/boost/type_traits/type_with_alignment.hpp
/usr/include/boost/mpl/if.hpp
/usr/include/boost/mpl/aux_/value_wknd.hpp
/usr/include/boost/mpl/aux_/config/integral.hpp
/usr/include/boost/mpl/aux_/config/eti.hpp
/usr/include/boost/mpl/aux_/na_spec.hpp
/usr/include/boost/mpl/lambda_fwd.hpp
/usr/include/boost/mpl/void_fwd.hpp
/usr/include/boost/mpl/aux_/na.hpp
/usr/include/boost/mpl/aux_/na_fwd.hpp
/usr/include/boost/mpl/aux_/lambda_arity_param.hpp
/usr/include/boost/mpl/aux_/arity.hpp
/usr/include/boost/mpl/aux_/config/dtp.hpp
/usr/include/boost/mpl/aux_/preprocessor/enum.hpp
/usr/include/boost/mpl/aux_/preprocessor/def_params_tail.hpp
/usr/include/boost/mpl/limits/arity.hpp
/usr/include/boost/preprocessor/logical/and.hpp
/usr/include/boost/preprocessor/logical/bitand.hpp
/usr/include/boost/preprocessor/identity.hpp
/usr/include/boost/preprocessor/facilities/identity.hpp
/usr/include/boost/preprocessor/empty.hpp
/usr/include/boost/preprocessor/arithmetic/add.hpp
/usr/include/boost/preprocessor/arithmetic/dec.hpp
/usr/include/boost/preprocessor/control/while.hpp
/usr/include/boost/preprocessor/list/fold_left.hpp
/usr/include/boost/preprocessor/list/detail/fold_left.hpp
/usr/include/boost/preprocessor/control/expr_iif.hpp
/usr/include/boost/preprocessor/list/adt.hpp
/usr/include/boost/preprocessor/detail/is_binary.hpp
/usr/include/boost/preprocessor/detail/check.hpp
/usr/include/boost/preprocessor/logical/compl.hpp
/usr/include/boost/preprocessor/list/fold_right.hpp
/usr/include/boost/preprocessor/list/detail/fold_right.hpp
/usr/include/boost/preprocessor/list/reverse.hpp
/usr/include/boost/preprocessor/control/detail/while.hpp
/usr/include/boost/preprocessor/tuple/elem.hpp
/usr/include/boost/preprocessor/facilities/overload.hpp
/usr/include/boost/preprocessor/variadic/size.hpp
/usr/include/boost/preprocessor/tuple/rem.hpp
/usr/include/boost/preprocessor/variadic/elem.hpp
/usr/include/boost/preprocessor/arithmetic/sub.hpp
/usr/include/boost/preprocessor/list/for_each_i.hpp
/usr/include/boost/preprocessor/repetition/for.hpp
/usr/include/boost/preprocessor/repetition/detail/for.hpp
/usr/include/boost/preprocessor/tuple/to_list.hpp
/usr/include/boost/preprocessor/list/transform.hpp
/usr/include/boost/preprocessor/list/append.hpp
/usr/include/boost/type_traits/is_pod.hpp
/usr/include/boost/type_traits/is_scalar.hpp
/usr/include/boost/type_traits/is_arithmetic.hpp
/usr/include/boost/type_traits/is_integral.hpp
/usr/include/boost/type_traits/is_float.hpp
/usr/include/boost/type_traits/is_enum.hpp
/usr/include/boost/type_traits/is_pointer.hpp
/usr/include/boost/type_traits/is_member_pointer.hpp
/usr/include/boost/type_traits/is_member_function_pointer.hpp
/usr/include/boost/type_traits/detail/is_mem_fun_pointer_impl.hpp
/usr/include/boost/type_traits/remove_cv.hpp
/usr/include/boost/static_assert.hpp
/usr/include/boost/mpl/eval_if.hpp
/usr/include/boost/mpl/identity.hpp
/usr/include/boost/type_traits/common_type.hpp
/usr/include/boost/utility/declval.hpp
/usr/include/boost/type_traits/conditional.hpp
/usr/include/boost/type_traits/decay.hpp
/usr/include/boost/type_traits/is_array.hpp
/usr/include/boost/type_traits/is_function.hpp
/usr/include/boost/type_traits/detail/false_result.hpp
/usr/include/boost/type_traits/detail/is_function_ptr_helper.hpp
/usr/include/boost/type_traits/remove_bounds.hpp
/usr/include/boost/type_traits/extent.hpp
/usr/include/boost/type_traits/floating_point_promotion.hpp
/usr/include/boost/type_traits/function_traits.hpp
/usr/include/boost/type_traits/has_new_operator.hpp
/usr/include/boost/type_traits/has_nothrow_assign.hpp
/usr/include/boost/type_traits/has_trivial_assign.hpp
/usr/include/boost/type_traits/is_const.hpp
/usr/include/boost/type_traits/has_nothrow_constructor.hpp
/usr/include/boost/type_traits/has_trivial_constructor.hpp
/usr/include/boost/type_traits/has_nothrow_copy.hpp
/usr/include/boost/type_traits/has_trivial_copy.hpp
/usr/include/boost/type_traits/has_nothrow_destructor.hpp
/usr/include/boost/type_traits/has_trivial_destructor.hpp
/usr/include/boost/type_traits/has_operator.hpp
/usr/include/boost/type_traits/has_bit_and.hpp
/usr/include/boost/type_traits/detail/has_binary_operator.hpp
/usr/include/boost/type_traits/is_base_of.hpp
/usr/include/boost/type_traits/is_base_and_derived.hpp
/usr/include/boost/type_traits/is_class.hpp
/usr/include/boost/type_traits/is_convertible.hpp
/usr/include/boost/type_traits/is_abstract.hpp
/usr/include/boost/type_traits/is_fundamental.hpp
/usr/include/boost/type_traits/remove_pointer.hpp
/usr/include/boost/type_traits/has_bit_and_assign.hpp
/usr/include/boost/type_traits/has_bit_or.hpp
/usr/include/boost/type_traits/has_bit_or_assign.hpp
/usr/include/boost/type_traits/has_bit_xor.hpp
/usr/include/boost/type_traits/has_bit_xor_assign.hpp
/usr/include/boost/type_traits/has_complement.hpp
/usr/include/boost/type_traits/detail/has_prefix_operator.hpp
/usr/include/boost/type_traits/has_dereference.hpp
/usr/include/boost/type_traits/has_divides.hpp
/usr/include/boost/type_traits/has_divides_assign.hpp
/usr/include/boost/type_traits/has_equal_to.hpp
/usr/include/boost/type_traits/has_greater.hpp
/usr/include/boost/type_traits/has_greater_equal.hpp
/usr/include/boost/type_traits/has_left_shift.hpp
/usr/include/boost/type_traits/has_left_shift_assign.hpp
/usr/include/boost/type_traits/has_less.hpp
/usr/include/boost/type_traits/has_less_equal.hpp
/usr/include/boost/type_traits/has_logical_and.hpp
/usr/include/boost/type_traits/has_logical_not.hpp
/usr/include/boost/type_traits/has_logical_or.hpp
/usr/include/boost/type_traits/has_minus.hpp
/usr/include/boost/type_traits/has_minus_assign.hpp
/usr/include/boost/type_traits/has_modulus.hpp
/usr/include/boost/type_traits/has_modulus_assign.hpp
/usr/include/boost/type_traits/has_multiplies.hpp
/usr/include/boost/type_traits/has_multiplies_assign.hpp
/usr/include/boost/type_traits/has_negate.hpp
/usr/include/boost/type_traits/has_not_equal_to.hpp
/usr/include/boost/type_traits/has_plus.hpp
/usr/include/boost/type_traits/has_plus_assign.hpp
/usr/include/boost/type_traits/has_post_decrement.hpp
/usr/include/boost/type_traits/detail/has_postfix_operator.hpp
/usr/include/boost/type_traits/has_post_increment.hpp
/usr/include/boost/type_traits/has_pre_decrement.hpp
/usr/include/boost/type_traits/has_pre_increment.hpp
/usr/include/boost/type_traits/has_right_shift.hpp
/usr/include/boost/type_traits/has_right_shift_assign.hpp
/usr/include/boost/type_traits/has_unary_minus.hpp
/usr/include/boost/type_traits/has_unary_plus.hpp
/usr/include/boost/type_traits/has_virtual_destructor.hpp
/usr/include/boost/type_traits/is_complex.hpp
/usr/include/c++/4.7/complex
/usr/include/c++/4.7/cmath
/usr/include/math.h
/usr/include/x86_64-linux-gnu/bits/huge_val.h
/usr/include/x86_64-linux-gnu/bits/huge_valf.h
/usr/include/x86_64-linux-gnu/bits/huge_vall.h
/usr/include/x86_64-linux-gnu/bits/inf.h
/usr/include/x86_64-linux-gnu/bits/nan.h
/usr/include/x86_64-linux-gnu/bits/mathdef.h
/usr/include/x86_64-linux-gnu/bits/mathcalls.h
/usr/include/c++/4.7/sstream
/usr/include/c++/4.7/bits/sstream.tcc
/usr/include/boost/type_traits/is_compound.hpp
/usr/include/boost/type_traits/is_empty.hpp
/usr/include/boost/type_traits/is_floating_point.hpp
/usr/include/boost/type_traits/is_member_object_pointer.hpp
/usr/include/boost/type_traits/is_object.hpp
/usr/include/boost/type_traits/is_polymorphic.hpp
/usr/include/boost/type_traits/is_signed.hpp
/usr/include/boost/type_traits/is_stateless.hpp
/usr/include/boost/type_traits/is_union.hpp
/usr/include/boost/type_traits/is_unsigned.hpp
/usr/include/boost/type_traits/is_virtual_base_of.hpp
/usr/include/boost/mpl/and.hpp
/usr/include/boost/mpl/aux_/config/use_preprocessed.hpp
/usr/include/boost/mpl/aux_/nested_type_wknd.hpp
/usr/include/boost/mpl/aux_/include_preprocessed.hpp
/usr/include/boost/mpl/aux_/config/compiler.hpp
/usr/include/boost/preprocessor/stringize.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/and.hpp
/usr/include/boost/mpl/not.hpp
/usr/include/boost/type_traits/make_unsigned.hpp
/usr/include/boost/type_traits/make_signed.hpp
/usr/include/boost/type_traits/rank.hpp
/usr/include/boost/type_traits/remove_extent.hpp
/usr/include/boost/type_traits/remove_all_extents.hpp
/usr/include/boost/type_traits/remove_const.hpp
/usr/include/boost/type_traits/remove_volatile.hpp
/usr/include/boost/type_traits/integral_promotion.hpp
/usr/include/boost/type_traits/promote.hpp
/usr/include/x86_64-linux-gnu/sys/mman.h
/usr/include/x86_64-linux-gnu/bits/mman.h
boost/coroutine/detail/swap_context.hpp
/usr/include/boost/preprocessor/repetition.hpp
/usr/include/boost/preprocessor/repetition/deduce_r.hpp
/usr/include/boost/preprocessor/repetition/deduce_z.hpp
/usr/include/boost/preprocessor/repetition/enum.hpp
/usr/include/boost/preprocessor/repetition/enum_binary_params.hpp
/usr/include/boost/preprocessor/repetition/enum_params.hpp
/usr/include/boost/preprocessor/repetition/enum_params_with_a_default.hpp
/usr/include/boost/preprocessor/facilities/intercept.hpp
/usr/include/boost/preprocessor/repetition/enum_params_with_defaults.hpp
/usr/include/boost/preprocessor/repetition/enum_shifted.hpp
/usr/include/boost/preprocessor/repetition/enum_shifted_binary_params.hpp
/usr/include/boost/preprocessor/repetition/enum_shifted_params.hpp
/usr/include/boost/preprocessor/repetition/enum_trailing.hpp
/usr/include/boost/preprocessor/repetition/enum_trailing_binary_params.hpp
/usr/include/boost/preprocessor/repetition/enum_trailing_params.hpp
/usr/include/boost/preprocessor/repetition/repeat_from_to.hpp
/usr/include/boost/tuple/tuple.hpp
/usr/include/boost/ref.hpp
/usr/include/boost/utility/addressof.hpp
/usr/include/boost/tuple/detail/tuple_basic.hpp
/usr/include/boost/type_traits/cv_traits.hpp
/usr/include/boost/utility/swap.hpp
/usr/include/c++/4.7/algorithm
/usr/include/c++/4.7/bits/stl_algo.h
/usr/include/c++/4.7/bits/algorithmfwd.h
/usr/include/c++/4.7/bits/stl_heap.h
/usr/include/c++/4.7/bits/stl_tempbuf.h
/usr/include/c++/4.7/bits/stl_construct.h
/usr/include/c++/4.7/ext/alloc_traits.h
/usr/include/c++/4.7/bits/alloc_traits.h
/usr/include/c++/4.7/bits/ptr_traits.h
/usr/include/c++/4.7/random
/usr/include/c++/4.7/limits
/usr/include/c++/4.7/bits/random.h
/usr/include/c++/4.7/vector
/usr/include/c++/4.7/bits/stl_uninitialized.h
/usr/include/c++/4.7/bits/stl_vector.h
/usr/include/c++/4.7/bits/stl_bvector.h
/usr/include/c++/4.7/bits/vector.tcc
/usr/include/c++/4.7/bits/random.tcc
/usr/include/c++/4.7/numeric
/usr/include/c++/4.7/bits/stl_numeric.h
/usr/include/c++/4.7/functional
/usr/include/c++/4.7/tuple
/usr/include/c++/4.7/bits/uses_allocator.h
/usr/include/boost/utility/enable_if.hpp
/usr/include/boost/mpl/vector.hpp
/usr/include/boost/mpl/limits/vector.hpp
/usr/include/boost/mpl/vector/vector20.hpp
/usr/include/boost/mpl/vector/vector10.hpp
/usr/include/boost/mpl/vector/vector0.hpp
/usr/include/boost/mpl/vector/aux_/at.hpp
/usr/include/boost/mpl/at_fwd.hpp
/usr/include/boost/mpl/vector/aux_/tag.hpp
/usr/include/boost/mpl/aux_/config/typeof.hpp
/usr/include/boost/mpl/long.hpp
/usr/include/boost/mpl/long_fwd.hpp
/usr/include/boost/mpl/void.hpp
/usr/include/boost/mpl/aux_/type_wrapper.hpp
/usr/include/boost/mpl/vector/aux_/front.hpp
/usr/include/boost/mpl/front_fwd.hpp
/usr/include/boost/mpl/vector/aux_/push_front.hpp
/usr/include/boost/mpl/push_front_fwd.hpp
/usr/include/boost/mpl/vector/aux_/item.hpp
/usr/include/boost/mpl/next_prior.hpp
/usr/include/boost/mpl/aux_/common_name_wknd.hpp
/usr/include/boost/mpl/vector/aux_/pop_front.hpp
/usr/include/boost/mpl/pop_front_fwd.hpp
/usr/include/boost/mpl/vector/aux_/push_back.hpp
/usr/include/boost/mpl/push_back_fwd.hpp
/usr/include/boost/mpl/vector/aux_/pop_back.hpp
/usr/include/boost/mpl/pop_back_fwd.hpp
/usr/include/boost/mpl/vector/aux_/back.hpp
/usr/include/boost/mpl/back_fwd.hpp
/usr/include/boost/mpl/vector/aux_/clear.hpp
/usr/include/boost/mpl/clear_fwd.hpp
/usr/include/boost/mpl/vector/aux_/vector0.hpp
/usr/include/boost/mpl/vector/aux_/iterator.hpp
/usr/include/boost/mpl/iterator_tags.hpp
/usr/include/boost/mpl/plus.hpp
/usr/include/boost/mpl/aux_/arithmetic_op.hpp
/usr/include/boost/mpl/aux_/largest_int.hpp
/usr/include/boost/mpl/aux_/numeric_op.hpp
/usr/include/boost/mpl/numeric_cast.hpp
/usr/include/boost/mpl/apply_wrap.hpp
/usr/include/boost/mpl/aux_/has_apply.hpp
/usr/include/boost/mpl/has_xxx.hpp
/usr/include/boost/mpl/aux_/yes_no.hpp
/usr/include/boost/mpl/aux_/config/arrays.hpp
/usr/include/boost/mpl/aux_/config/has_xxx.hpp
/usr/include/boost/mpl/aux_/config/msvc_typename.hpp
/usr/include/boost/preprocessor/array/elem.hpp
/usr/include/boost/preprocessor/array/data.hpp
/usr/include/boost/preprocessor/array/size.hpp
/usr/include/boost/mpl/aux_/config/has_apply.hpp
/usr/include/boost/mpl/aux_/msvc_never_true.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/apply_wrap.hpp
/usr/include/boost/mpl/tag.hpp
/usr/include/boost/mpl/aux_/has_tag.hpp
/usr/include/boost/mpl/aux_/numeric_cast_utils.hpp
/usr/include/boost/mpl/aux_/config/forwarding.hpp
/usr/include/boost/mpl/aux_/msvc_eti_base.hpp
/usr/include/boost/mpl/aux_/is_msvc_eti_arg.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/plus.hpp
/usr/include/boost/mpl/minus.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/minus.hpp
/usr/include/boost/mpl/advance_fwd.hpp
/usr/include/boost/mpl/distance_fwd.hpp
/usr/include/boost/mpl/next.hpp
/usr/include/boost/mpl/prior.hpp
/usr/include/boost/mpl/vector/aux_/O1_size.hpp
/usr/include/boost/mpl/O1_size_fwd.hpp
/usr/include/boost/mpl/vector/aux_/size.hpp
/usr/include/boost/mpl/size_fwd.hpp
/usr/include/boost/mpl/vector/aux_/empty.hpp
/usr/include/boost/mpl/empty_fwd.hpp
/usr/include/boost/mpl/vector/aux_/begin_end.hpp
/usr/include/boost/mpl/begin_end_fwd.hpp
/usr/include/boost/mpl/vector/aux_/include_preprocessed.hpp
/usr/include/boost/mpl/vector/aux_/preprocessed/typeof_based/vector10.hpp
/usr/include/boost/mpl/vector/aux_/preprocessed/typeof_based/vector20.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/vector.hpp
/usr/include/boost/call_traits.hpp
/usr/include/boost/detail/call_traits.hpp
boost/coroutine/detail/arg_max.hpp
boost/coroutine/detail/coroutine_impl.hpp
/usr/include/boost/optional.hpp
/usr/include/boost/optional/optional.hpp
/usr/include/boost/type.hpp
/usr/include/boost/detail/reference_content.hpp
/usr/include/boost/none.hpp
/usr/include/boost/none_t.hpp
/usr/include/boost/utility/compare_pointees.hpp
/usr/include/boost/utility/in_place_factory.hpp
/usr/include/boost/utility/detail/in_place_factory_prefix.hpp
/usr/include/boost/preprocessor/punctuation/paren.hpp
/usr/include/boost/preprocessor/iteration/iterate.hpp
/usr/include/boost/preprocessor/slot/slot.hpp
/usr/include/boost/preprocessor/slot/detail/def.hpp
/usr/include/boost/preprocessor/iteration/detail/iter/forward1.hpp
/usr/include/boost/preprocessor/iteration/detail/bounds/lower1.hpp
/usr/include/boost/preprocessor/slot/detail/shared.hpp
/usr/include/boost/preprocessor/iteration/detail/bounds/upper1.hpp
/usr/include/boost/utility/detail/in_place_factory_suffix.hpp
/usr/include/boost/optional/optional_fwd.hpp
boost/coroutine/detail/argument_unpacker.hpp
/usr/include/boost/utility/result_of.hpp
/usr/include/boost/mpl/or.hpp
/usr/include/boost/mpl/aux_/preprocessed/gcc/or.hpp
/usr/include/boost/utility/detail/result_of_iterate.hpp
boost/coroutine/detail/index.hpp
boost/coroutine/detail/coroutine_accessor.hpp
boost/coroutine/detail/context_base.hpp
/usr/include/boost/detail/atomic_count.hpp
/usr/include/boost/smart_ptr/detail/atomic_count.hpp
/usr/include/boost/smart_ptr/detail/sp_has_sync.hpp
/usr/include/boost/smart_ptr/detail/atomic_count_gcc_x86.hpp
/usr/include/boost/intrusive_ptr.hpp
/usr/include/boost/smart_ptr/intrusive_ptr.hpp
/usr/include/boost/smart_ptr/detail/sp_convertible.hpp
/usr/include/boost/config/no_tr1/functional.hpp
/usr/include/boost/smart_ptr/detail/operator_bool.hpp
boost/coroutine/detail/noreturn.hpp
boost/coroutine/detail/is_callable.hpp
/usr/include/boost/mpl/logical.hpp
boost/coroutine/detail/argument_packer.hpp
boost/coroutine/detail/signature.hpp
boost/coroutine/detail/coroutine_traits.hpp
boost/coroutine/tuple_traits.hpp
boost/coroutine/detail/yield_result_type.hpp
boost/coroutine/detail/make_tuple_traits.hpp
boost/coroutine/move.hpp
/usr/include/boost/preprocessor/seq/seq.hpp
/usr/include/boost/preprocessor/seq/elem.hpp
boost/coroutine/detail/has_swap.hpp
boost/coroutine/detail/fix_result.hpp
boost/coroutine/detail/self.hpp
boost/coroutine/detail/signal.hpp
boost/coroutine/detail/future_impl.hpp

Which is more than 600 includes. The preprocessed file of just including the header has almost 75000 lines.

The reason for this is that boost makes almost no compromises. Boost code has to compile on all machines and on all compilers. It has to be easy to use and support all use cases. It must be exception safe and thread safe. And finally it also must have as little runtime cost as possible. The only thing that a boost library will compromise on is compilation time.

I think that that is a bad compromise. Compilation time is one of those things that will come back to bite you if you’re not paying attention to it. I’m convinced that you can improve your runtime performance more if you speed up your compilation time than if you do all the metaprogramming tricks that they use, simply because you can iterate better. And boost simply takes it too far.

So how do you actually implement coroutines in C++? On POSIX compliant systems you use ucontext.h:

#include <ucontext.h>
#include <cstdint>
#include <memory>
#include <functional>

struct coroutine
{
    coroutine(const std::function<void (coroutine &)> func, size_t stack_size = SIGSTKSZ)
        : stack{new unsigned char[stack_size]}, func{func}
    {
        getcontext(&callee);
        callee.uc_link = &caller;
        callee.uc_stack.ss_size = stack_size;
        callee.uc_stack.ss_sp = stack.get();
        makecontext(&callee, reinterpret_cast<void (*)()>(&coroutine_call), 2, reinterpret_cast<size_t>(this) >> 32, this);
    }
    coroutine(const coroutine &) = delete;
    coroutine & operator=(const coroutine &) = delete;
    coroutine(coroutine &&) = default;
    coroutine & operator=(coroutine &&) = default;

    void operator()()
    {
        if (returned) return;
        swapcontext(&caller, &callee);
    }

    operator bool() const
    {
        return !returned;
    }

    void yield()
    {
        swapcontext(&callee, &caller);
    }

private:
    ucontext_t caller;
    ucontext_t callee;
    std::unique_ptr<unsigned char[]> stack;
    std::function<void (coroutine &)> func;
    bool returned = false;

    static void coroutine_call(uint32_t this_pointer_left_half, uint32_t this_pointer_right_half)
    {
        coroutine & this_ = *reinterpret_cast<coroutine *>((static_cast<size_t>(this_pointer_left_half) << 32) + this_pointer_right_half);
    	this_.func(this_);
        this_.returned = true;
    }
};

There you go. A complete coroutine implementation in 51 lines. The constructor allocates a stack for the coroutine and sets the context up so that it returns to the caller context after it returns. I also pass in the this pointer as the argument for the function, except I have to split it up into two integers. The coroutine_call function of the coroutine reconstructs the this pointer and calls the stored function. And then it’s just about calling swapcontext at the right time.
Here’s how to use it:

#include <coroutine.h>
#include <iostream>
int main()
{
    coroutine test{[](coroutine & self)
    {
        for (int i = 0; i < 5; ++i)
        {
            std::cout << "coroutine " << i << std::endl;
            self.yield();
        }
    }};
    while(test)
    {
        std::cout << "main" << std::endl;
        test();
    }
    return 0;
}

This will print

main
coroutine 0
main
coroutine 1
main
coroutine 2
main
coroutine 3
main
coroutine 4
main

This is not thread-safe, not exception-safe and it only supports void functions without arguments. You could probably work well with this in more than 90% of the cases where you’d want coroutines.

This doesn’t run on Windows because Windows doesn’t provide the ucontext.h header. There are equivalent functions on Windows though, and boost.coroutine uses them. So if you are a Windows user you might want to use boost.coroutine, or you can rewrite the above code to use the Windows functions. I think you’d want to use fibers, but I haven’t looked into it at all.

In my next post I’ll also provide a coroutine implementation which supports arguments and return values and which is exception safe.