Coroutines - Some Theory

In my previous post Couroutines Part 1. I explained one of why the C++ language will benefit from coroutines and why I am excited about them. Here I want to go into some of the theory behind the.

As far as a computer is concerned, memory is memory. Some is read-only and some is read-write. A CPU will fetch the content of its Program Counter (PC) and then execute it. In most cases the PC is then incremented, ready for the next instruction.

Sometimes we will have a branch (or jump) instruction that fills the PC with an instruction that is not the next instruction. In C this would be the equvalent of a goto. This branch or jump can be conditional on a previous comparison.

But that is it. Just memory. No heaps, stacks or static memory etc, just what we in C would call global memory.

With such a flat memory model a subroutines will assign the address of the next instruction to some address before jumping and the look up the stored address to return.

Corutines are just a bit more complicated, with two addresses, we can jump back and forth between two coroutines. All fast and simple.

So why do most languages have subroutines AKA functions but few languages have coroutines? The reason is that modern languages like Algol and later C introduced the stack.

In C when we enter a function, all local variables are push onto the stack. When the function exits, these variables are popped of the stack. This works great for subroutines/functions becuase subroutines are essentially FIFO structures.

Pushing and popping the stack is as simple as decrementing and incrementing a single stack pointer. Local variables then are relative to the stack pointer register. We can even call the same function recursively because each instance of variables used by our function are relative to the stack pointer.

Coroutines however are not nearly as neat. Given that coroutines can be suspended and resumed, we cannot use a simple stack pointer to create storage for our coroutine.

One approach to allowing coroutines is for each coroutine to have its own stack. When we switch from one coroutine to another all we need to do is swap stack pointers just to our resume point and all is good.

This incidentally is what our operating system scheduler does. Each thread has its own stack and when one thread is suspended and another resumed, the OS will swap out one stack with another.

Many language use the stackful coroutines also known as green threads or fibres. These include D fibres, Go Goroutines or Haskell forkIO. Boost Coroutines uses Boost Context to create stackful coroutines.

The C++ 20 stackless coroutines all run on the same stack. No change to the stack pointer other than normal pushing and popping is make.

Our C++ compiler breaks up our coroutine into independent subroutines. It then places any variables that straddle these independent subroutines into a context object that lives on the heap. This still requires some heap memory allocation but not nearly as much as a heap per coroutine.

So stay tuned for the next installment where you will get to see a Hello World coroutine example.