Coroutines (coroutines, coroutine) - what is it?

Coroutines (coroutines, coroutine) are code execution threads that are organized on top of hardware (system) threads.
The code execution flow is a sequence of operations that are performed one after another. At the right moments, this sequence may be suspended, and instead of it, part of another sequence of operations may begin to be performed.

System threads are made up of processor instructions, and several system threads can operate in turn on one processor core.
Coroutines operate at a higher level — several coroutines can in turn execute their code on one system thread. (Depending on the implementation, the coroutine may not be tied to a specific system thread, for example, it may execute its code on the thread pool).

Unlike system threads, which are switched by the system at arbitrary points in time (preemptive multitasking), coroutines are switched manually at the places specified by the programmer (cooperative multitasking).

We denote coroutine operations as follows:

• handle = spawn(СП); - launch coroutine,
• yield; - suspension of the current coroutine,
• resume(handle); - resumption of coroutine.

Take two coroutines:

 // СП1 | // СП2 { | { f1(); | g1(); f2(); | yield; yield; | g2(); f3(); | g3(); f4(); | yield; yield; | g4(); f5(); | g5(); } | } 

Then, if SP1 is run on one system thread, and then SP2, then the system thread will perform operations in the following deterministic order:

 // Системный поток | Выполняемый код c1 = spawn(СП1); | f1(); | f2(); c2 = spawn(СП2); | g1(); resume(c1); | f3(); | f4(); resume(c2); | g2(); | g3(); resume(c1); | f5(); resume(c2); | g4(); | g5(); 

Since both coroutines are executed on the same system thread, data races are impossible in them, the code between the yield is performed atomically (within this system thread).

But if you run each coroutine in a separate system thread, then they will not differ from normal system streams - they will switch where the system says, synchronization is necessary so that there are no data races.

Asynchronous operations

One of the main coroutine use cases is asynchronous operations, such as I / O and animations in the UI. After the start of an asynchronous operation, the coroutine can yield and continue after the operation has completed. At the same time, the system thread on which it was running does not fall asleep with the coroutine, but remains free for other coroutines.

Traditional asynchronous code implies the use of callbacks, both function parameters and together with future / promise:

 async_write(buffer, callback); -- или -- async_write(buffer).then(callback); 

Where callback is a function that will be called after the end of asynchronous writing. You can use a lambda function as a callback, for example, in the C ++ syntax:

 async_write(buffer, [=]{ on_write_completed(); }); 

We introduce the operation handle = get_coroutine_handle(); which will produce the coroutine handle (context) in the coroutine code itself.
Then inside the coroutine you can write:

 handle = get_coroutine_handle(); async_write(buffer, [=]{ resume(handle); }); yield; 

For convenience, many languages ​​use the await operator, which shortens this code to

 await async_write(buffer); 

More detailed example:

 // Использование коллбеков | // Использование сопрограмм | Socket src, dst; | void copy(Socket src, Socket dst) { byte buffer[1024]; | byte buffer[1024]; void copy() { | for (;;) { async_read(src, buffer, on_read); | int n = await async_read(src, buffer); } | if (n <= 0) return; void on_read(int n) { | await async_write(dst, buffer, n); if (n <= 0) return; | } async_write(dst, buffer, n, copy); | } } | 

Generators

Another scenario of using coroutines is "generators", coroutines that generate sequences of objects of the same type, for example, a sequence of numbers:

 generator<int> fib() { int a = 0, b = 1; for (;;) { yield a; a = a + b; yield b; b = a + b; } } int main() { generator<int> g = fib(); // печатаем первые 5 for (int i = 0; i != 5; ++i) { g.next(); print(g.value()); } } 

Here, yield in addition to stopping the generator, also takes the values ​​that are generated by the generator.

Stackful implementation of coroutines

As the name implies, stackful coroutines are coroutines that have their own stack, just like system threads. The main difference between such coroutines from ordinary system streams is that they are switched manually. Compared to the speed of switching system streams, switching coroutines is practically free (hundreds of processor cycles). However, due to the fact that for each coroutine it is necessary to allocate a separate stack and other service data structures - their creation and existence is not cheaper than creating a system flow.

In Windows, stackful coroutines are built into the system and are called fibers (fibers, fibers). Fibers are tied to the system thread on which they are created, switching ( yield / resume ) is implemented via the SwitchToFiber(fiber_handle) function SwitchToFiber(fiber_handle) .

Running a stackful of coroutines is no different from running a regular stream, and it may look, for example, like this:

 handle = SpawnCoroutine(CoroutineFunc, STACK_SIZE); 

Having your own stack allows you to yield from nested function calls.
However, since stackful coroutines are quite expensive; they cannot be used to create simple generators.

Stackless implementation coroutines

Stackless (stemless) coroutines do not depend on the operating system in any way, and are implemented exclusively by the compiler: the coroutine code is rewritten into an object-state machine, local variables are not allocated on the stack, but become members of this object.

 // сопрограмма | // код, генерируемый компилятором generator<int> fib() { | struct __fib { int a = 0, b = 1; | int a, b; for (;;) { | int __result; yield a; | int __state = 0; a = a + b; | void next() { yield b; | for (;;) switch (__state) { b = a + b; | case 0: a = 0; } | b = 1; } | case 3: __result = a; | __state = 1; | return; | case 1: a = a + b; | __result = b; | __state = 2; | return; | case 2: b = a + b; | __state = 3; | break; // loop | } | } | int value() { return __result; } | }; | generator<int> fib() { | return __fib(); | } 

Unlike stackful coroutines, in a coroutine without a stack, the yield can only be in its body. You cannot make a yield from a function called coroutine.

The creation of a stringless coroutine is the creation of an object that stores its state ( __fib ), and usually looks like a function call:

 generator<int> gen = fib(); gen.next(); int val = gen.value();