Coroutines (coroutines, coroutine) "what is it?"

Coroutines are code execution threads that are organized on top of hardware (system) threads.
A code execution flow is a sequence of operations that are executed one after the other. At the right moments, this sequence can be paused, and a part of another sequence of operations can start executing instead.

System threads consist of processor instructions, and can take turns running on a single processor core multiple system threads.
Coroutines operate at a higher level - multiple coroutines can take turns executing their code on a single system thread. (Depending on the implementation, a coroutine may not be bound to a specific system thread, but may run its code on a thread pool, for example.)

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

Let's denote the operations on the coroutine as follows:

• handle = spawn(СП); - start the coroutine,
• yield; - suspends the current coroutine,
• resume(handle); - resumes the coroutine.

Let's take two coroutines:

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

Then, if you run SP1 and then SP2 on one system thread, then the system thread will perform operations in the next deterministic all right:

// Системный поток  |  Выполняемый код
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 not possible in them, the code between yield is executed atomically (within this system thread).

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

Asynchronous operations

One of the main scenarios for using coroutines is asynchronous operations, such as I / O and animations in the UI. After starting an asynchronous operation, the coroutine can do yield and continue after the operation is completed. In this case, the system thread on which it was executed does not fall asleep together with the coroutine, but remains free for other coroutines.

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

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

Where callback is the function that will be called after the asynchronous write ends. As a callback, you can use a lambda function, for example, in the C++syntax:

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

Let's introduce the operation handle = get_coroutine_handle();, which will give the handle (context) of the coroutine in the code of the coroutine 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 up 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 use case for coroutines is "generators", coroutines that generate sequences of similar objects, such as sequences 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 issued by the generator.

Stackful coroutine implementations

As the name suggests, stackful (stackable) coroutines are coroutines that have their own stack, just like system threads. The main difference between such coroutines and regular system threads is that they are switched manually. Compared to the speed of switching system threads, switching coroutines is almost free (hundreds of CPU 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 the flow.

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

Running a stackful coroutine is no different from running a normal thread, and may look like this, for example:

handle = SpawnCoroutine(CoroutineFunc, STACK_SIZE);

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

Stackless coroutine implementations

Stackless (stack-free) coroutines do not depend on the operating system in any way, and are implemented exclusively by means of the compiler: the code of the coroutine is rewritten into an object-a finite automaton, local variables are allocated not 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();
                        |  }

As opposed to stackful coroutines, in a coroutine without a stack yield can only be in its body. You can't make yield from a function called by a coroutine.

Creating a stack-less coroutine is creating an object that stores its state (__fib), and usually looks like calling a function:

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