Coroutines

Coroutines are functions that can suspend and resume their execution while keeping their state. The evolution in C++20 goes one step further.

What I present in this post as a new idea in C++20 is quite old. Melvin Conway coins the term coroutines. He used it in his publication of compiler construction in 1963. Donald Knuth called procedures a particular case of coroutines. Sometimes, it just takes a bit longer.

Although I know coroutines from Python, it was quite challenging for me to understand the new concept in C++20. Hence, before I dive into the details, here is the first contact.

A first contact

With the new keywords co_await and co_yield, C++20 will extend the concept of a function.

Thanks to  co_await expression, it is possible to suspend and resume the execution of the expression. If you use co_await expression in a function func, the call  auto getResult = func() has not to be blocked, if the function result is unavailable. Instead of resource-consuming blocking, you have resource-friendly waiting.

co_yield expression enables it to write a generator function. The generator function returns on request each time a new value is. A generator function is a data stream from which you can pick values. The data stream can be infinite; therefore, we are at the center of lazy evaluation with C++.

A simple example

The program is as simple as possible. The function getNumbers returns all integers from begin to end incremented by inc. begin has to be smaller than end, and inc has to be positive.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// greedyGenerator.cpp

#include <iostream>
#include <vector>

std::vector<int> getNumbers(int begin, int end, int inc= 1){
  
  std::vector<int> numbers;
  for (int i= begin; i < end; i += inc){
    numbers.push_back(i);
  }
  
  return numbers;
  
}

int main(){

  std::cout << std::endl;

  auto numbers= getNumbers(-10, 11);
  
  for (auto n: numbers) std::cout << n << " ";
  
  std::cout << "\n\n";

  for (auto n: getNumbers(0,101,5)) std::cout << n << " ";

  std::cout << "\n\n";

}

Of course, I reinvented the wheel with getNumbers because since C++11, that job can be done with  std::iota.

For completeness, here is the output.

Two observations about the program are essential. On the other hand, the vector numbers in line 8 always get all values. That even holds if I'm only interested in the first five elements of a vector with 1000 elements. On the other hand, it's quite easy to transform the function getNumbers into a generator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// lazyGenerator.cpp

#include <iostream>
#include <vector>

generator<int> generatorForNumbers(int begin, int inc= 1){
  
  for (int i= begin;; i += inc){
    co_yield i;
  }
  
}

int main(){

  std::cout << std::endl;

  auto numbers= generatorForNumbers(-10);
  
  for (int i= 1; i <= 20; ++i) std::cout << numbers << " ";
  
  std::cout << "\n\n";

  for (auto n: generatorForNumbers(0, 5)) std::cout << n << " ";

  std::cout << "\n\n";

}

While the function getNumbers in the file greedyGenerator.cpp returns a std::vector<int>, the coroutine generatorForNumbers in lazyGenerator.cpp returns a generator. The generator numbers in line 18 or generatorForNumbers(0, 5) in line 24 return on request a new number. The range-based for-loop triggers the query. To be precise. The query of the coroutine returns the value i via co_yield i and immediately suspends its execution. If a new value is requested, the coroutine resumes its execution precisely at that place.

The expression getForNumber(0, 5) in line 24 may look slightly weird. This is a just-in-place usage of a generator.

I want to stress one point explicitly. The coroutine generatorForNumbers creates an infinite data stream because the for-loop in line 8 has no end condition. That is no problem if I only ask for a finite number of values, such as in line 20. That will not hold for line 24. There is no end condition.

As promised. Here are the details of the coroutines. I will answer the following questions:

• What are the typical use cases for coroutines?
• What are the concepts used by coroutines?
• What are the design goals for coroutines?
• How does a function become a coroutine?
• What are the characteristics of the two new keywords co_await and co_yield?

More details

At first, the simpler questions?

What are the typical use cases for coroutines?

Coroutines are the natural way to write event-driven applications. This can be simulations, games, servers, user interfaces, or algorithms. Coroutines are typically used for cooperative multitasking. The key to cooperative multitasking is that each task takes as much time as it needs. That is in contrast to pre-emptive multitasking. Here we have a scheduler that decides how long each task gets the CPU.

There are different versions of coroutines.

What are the concepts used by coroutines?

Coroutines in C++20 are asymmetric, first-class, and stackless.

The workflow of an asymmetric coroutine goes back to the caller. That must not hold for a symmetric coroutine. An asymmetric coroutine can delegate its workflow to another coroutine.

First-class coroutines are similar to First-Class Functions because coroutines behave like data. That means you can use them as an argument, return a function's value, or store them in a variable.

A stackless coroutine enables it to suspend and resume the top-level coroutine. But this coroutine can not invoke another coroutine.

Proposal n4402 describes the design goals of coroutines.

What are the design goals for coroutines?

Coroutines should be

• Highly scalable (to billions of concurrent coroutines).
• Highly efficient resume and suspend operations comparable in cost to a function call overhead.
• Seamless interaction with existing facilities with no overhead.
• Open-ended coroutine machinery allows library designers to develop coroutine libraries exposing various high-level semantics, such as generators, goroutines, tasks, and more.
• Usable in environments where exceptions are forbidden or not available

There are four reasons a function becomes a coroutine.

How does a function become a coroutine?

A function becomes a coroutine if it uses

• co_return, or
• co_await, or
• co_yield, or
• a co_await expression in a range-based for-loop.

The answer to this question was from proposal n4628.

Finally, I come to the new keywords  co_return, co_yield, and co_await.

co_return, co_yield and co_await

co_return: A coroutine returns from its function body with co_return.

co_yield: Thanks to co_yield,  you can implement a generator. Therefore, you can create a generator  (lazyGenerator.cpp) generating an infinite data stream from which you can successively query values. The return type of the generator generator<int> generatorForNumbers(int begin, int inc = 1) is, in this case, generator<int>. generator<int> internally holds a particular promise p such that a call co_yield i is equivalent to a call co_await p.yield_value(i). co_yield i can be arbitrarily often called.  Immediately after the call, the execution of the coroutine will be suspended. 

co_await: co_await eventually causes the execution of the coroutine to be suspended and resumed. The expression exp in co_await exp has to be a so-called awaitable expression. exp has to implement a specific interface. This interface consists of three functions e.await_ready, e.await_suspend, and e.await_resume.

The typical use case for co_await is a server that waits in a blocking fashion for events.

1
2
3
4
5
6
7

Acceptor acceptor{443};
while (true){
  Socket socket= acceptor.accept();              // blocking
  auto request= socket.read();                   // blocking
  auto response= handleRequest(request);     
  socket.write(response);                        // blocking  
}

The server is quite simple because it sequentially answers each request in the same thread. The server is listening on port 443 (line 1), accepts its connections (line 3), reads the incoming data from the client (line 4), and write its answer to the client (line 6). The calls in line 3, 4, and 6 are blocking.

Thanks to co_await, the blocking calls can now be suspended and resumed.

1
2
3
4
5
6
7

Acceptor acceptor{443};
while (true){
  Socket socket= co_await acceptor.accept();           
  auto request= co_await socket.read();              
  auto response= handleRequest(request);     
  co_await socket.write(responste);                 
}

What's next?

The idea of transactional memory is based on transactions from the database theory. A transaction is an action that provides the properties Atomicity, Consistency, Isolation, and Durability (ACID). Transactional memory will be the topic of my next post.