greedyGenerator

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";

}

 

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

    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.

    greedyGenerator

    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.

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, moon, Philipp Lenk, Hobsbawm, and Charles-Jianye Chen.

    Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

    I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

    Standard Seminars (English/German)

    Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    0 replies

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *