• Entwicklung/Architektur
  • Methoden
  • Programmiersprachen
• Betrieb
  • Datenbanken
  • Server
  • IT-Security
  • Speicher
  • Netzwerke
  • Virtualisierung
  • Verfügbarkeit
  • Künstliche Intelligenz
• Management und Recht
  • Projektmanagement
  • Digitalisierung
  • IT-Recht
  • IT-Selbständige
• Aktuelles
• Termine
• IT-Jobs

☰

• Entwicklung/Architektur
• Betrieb
• Management und Recht
• News
• IT-Jobs
• Newsletter

Detlef Wilkening 07. November 2017

Coroutinen in C++ mit Boost.Coroutine2

Was sind aber nun Coroutinen?

Ausgabe:

main(1) - doit(2) - main(3) - doit(4) - main(5) - doit(6) - main(7)

Hierbei ist die Klasse boost::coroutine<> ein sogenannter Sammeltyp, der zwei innere Typen – push_type und pull_type – zur Verfügung stellt. Mit diesen beiden Typen können Werte zwischen den Coroutinen ausgetauscht werden – dies wird in unserem ersten Beispiel noch nicht genutzt, d. h. auch das Template-Argument void für die Klasse coroutine<>.

Um nun main und doit als gegenseitige Coroutinen nutzen zu können, müssen nur zwei Dinge umgesetzt werden:

• Die Funktion doit wird durch den Parameter coroutine<void>::push_type& zu einer Funktion, die als Coroutine genutzt werden kann.
• In main erzeugen wir ein coroutine<void>::pull_type-Objekt mit der Funktion doit als Argument – dies erlaubt den Aufruf zurück in die Funktion doit mit dem alten Status.

Was passiert nun zur Laufzeit:

1. Die Funktion main wird aufgerufen und gibt als erstes main(1) -  aus.
2. Mit Erzeugung des Objekts coro wird dann direkt die übergebene Funktion doit aufgerufen – sie gibt doit(2) -  aus.
3. Mit dem Aufruf von yield() wird die Funktion doit verlassen, ohne dass der Status von doit verlorengeht. Der Ausführungspfad wird an main zurückübertragen und das Programm gibt main(3) -  aus.
4. Der Aufruf coro() wiederum setzt den Ausführungspfad zurück in die Funktion doit. Achtung, dabei wird die Funktion doit nicht neu aufgerufen, sondern der Ausführungspfad setzt direkt an der Stelle in doit wieder auf, wo die Funktion vorher verlassen wurde. Daher ist die nächste Ausgabe doit(4) -.
5. Der erneute Aufruf von yield() verlässt doit wieder und springt zurück zur Funktion main – aber eben auch wieder an die Stelle der letzten Ausführung – das Programm gibt nun also main(5) -  aus.
6. Der erneute Aufruf von coro() in main, springt zurück in die Funktion doit an den letzten Ausführungspunkt und gibt dann dort doit(6) -  aus.
7. Das Ende der Funktion doit sorgt für einen letzten Rücksprung in die Funktion main – auch hier an den letzten Ausführungspunkt – und führt dann zu der letzten Ausgabe main(7).

Fibonacci-Generator mit Coroutinen

Unser erstes Beispiel zeigt, dass man mit "Boost.Coroutine2" Coroutinen implementieren kann und mit diesen zwischen Funktionen hin- und herspringen kann. Dass hierbei der gesamte Status der Funktion zwischengespeichert und restauriert wird – also z. B. auch die lokalen Variablen – konnte man hierbei noch nicht sehen. Dies, und auch die Übergabe von Werten zwischen den Funktionen, zeigt das zweite Beispiel in dem wir einen Generator für die Zahlen der Fibonacci-Folge bauen. Da wir nun aus der Funktion fib_coro Int-Werte an main zurückgeben wollen, müssen wir den Sammeltyp entsprechend zu coroutine<int> modifizieren. Außerdem ist es hier nun wichtig, dass in main der Pull-Typ und in fib_coro der Push-Typ verwendet wird – man kann bei Boost.Coroutine2 nur Werte vom Push-Typ zum Pull-Typ übergeben.

Listing 2:

#include <iostream>
#include <boost/coroutine2/all.hpp>
 
using namespace std;
using namespace boost::coroutines2;
 
void fib_coro(coroutine<int>::push_type& yield)
{
   int i1 = 0, i2 = 1;
   for (;;)
   {
      yield(i2);
      int temp = i1 + i2;
      i1 = i2;
      i2 = temp;
   }
}
 
int main()
{
   coroutine<int>::pull_type fib(fib_coro);
   for (int i = 0; i < 10; ++i)
   {
      cout << fib.get() << ", ";
      fib();
   }
   cout << endl;
}  

Ausgabe:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

In diesem Beispiel enthält die Funktion fib_coro eine Schleife mit Schleifenzähler und mehrere lokale Variablen.

• Im Prinzip werden hier nur endlos die Fibonacci-Zahlen erzeugt – dank des Aufrufs von yield(i2) springen wir nach jeder Berechnung aus der Funktion und liefern hierbei die nächste Fibonacci-Zahl (i2) zurück, und haben nicht nur eine Endlos-Schleife erzeugt.
• In main verzweigt jeder Aufruf von fib() weiterhin in die Coroutine fib_coro, während der Aufruf von fib.get() den Wert der Coroutine zurückgibt.

Coroutinen, die bei jedem Aufruf einen Wert zurückliefern, werden in vielen Sprachen auch "Generatoren" genannt, z. B. in C#.

Coroutinen können lazy unendliche Mengen produzieren

Im Prinzip stellt die Coroutine fib eine unendliche Menge dar, die lazy berechnet wird. Wenn wir in C++ mit Mengen operieren, dann denken wir typischerweise an Iteratoren, Algorithmen und Ranges. Da solche Generatoren eine typische Anwendung von Coroutinen sind, unterstützt Boost.Coroutine2 Iteratoren für Coroutinen-Aufrufe – das folgende Beispiel zeigt einen einfachen Coroutinen-Generator und die Nutzung mit Iteratoren (Listing 3).

Listing 3:

#include <iostream>
#include <numeric>
#include <boost/coroutine2/all.hpp>
 
using namespace std;
using namespace boost::coroutines2;
 
void doit(coroutine<int>::push_type& yield)
{
   for (int i = 0; i < 10; ++i)
   {
      yield(i);
   }
}
 
int main()
{
   coroutine<int>::pull_type doit1(doit);
   for (int i : doit1)
   {
      cout << i << " - ";
   }
   cout << endl;
 
   coroutine<int>::pull_type doit2(doit);
   auto sum = accumulate(begin(doit2), end(doit2), 0);
   cout << "Summe: " << sum << endl;
}

Ausgabe:

0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 –
Summe: 45

Achtung: man muss aufpassen, dass die Anzahl der Generator-Aufrufe irgendwie begrenzt wird (entweder im Generator oder beim Aufrufer) – der Generator liefert ja unendlich viele Werte und endet nie. In diesem Beispiel begrenzt der Generator selbst die Iteration, da die Schleife eine Abbruch-Bedingung enthält.

Generatoren ohne Coroutinen

Natürlich lassen sich Generatoren in C++ auch ohne Coroutinen implementieren – man kann einfach ein Funktionsobjekt nutzen und den Status der Coroutine über die Attribute des Funktionsobjekts simulieren – s. Listing 4 für einen Fibonacci-Generator ohne Coroutinen. Aber zum einen ist der Code mit Coroutine der einfachere Code (wenn man Coroutinen verstanden hat) – zum anderen liegt das auch an der Einfachheit des Beispiels. Wir werden gleich ein komplexeres Beispiel sehen, wo die Sache ganz anders aussieht.

Listing 4:

#include <iostream>
using namespace std;
 
class Fib
{
public:
   int operator()()
   {
      if (first)
      {
         first = false;
         return 1;
      }
      int tmp = i2;
      i2 = i1 + i2;
      i1 = tmp;
      return i2;
   }
 
private:
   int i1 = 0, i2 = 1;
   bool first = true;
};
 
int main()
{
   Fib fib;
   for (int i = 0; i < 10; ++i)
   {
      cout << fib() << ", ";
   }
   cout << endl;
}  

Ausgabe:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

Boost Coroutinen retten den gesamten Stackframe

Sogenannte "stackfull coroutines" sind Coroutinen, die den gesamten Aufrufstack sichern und daher über mehrere Funktions-Aufrufe hinweg funktionieren – Coroutinen auf Basis von Boost.Coroutine2 sind "stackfull coroutines". Das folgende Listing 5 zeigt dies erstmal an einem einfachen Beispiel. Der push_type wird über mehrere Funktions-Aufrufe durchgeschleppt, das yield springt dann aus allen diesen Funktionen heraus und das doit() wieder in alle hinein.

Listing 5:

#include <iostream>
#include <boost/coroutine2/all.hpp>
 
using namespace std;
using namespace boost::coroutines2;
 
void doit_coro3(coroutine<int>::push_type& yield)
{
   for (int i = 1; true; i += 2)
   {
      yield(i);
   }
}
 
void doit_coro2(coroutine<int>::push_type& yield)
{
   doit_coro3(yield);
}
 
void doit_coro1(coroutine<int>::push_type& yield)
{
   doit_coro2(yield);
}
 
int main()
{
   coroutine<int>::pull_type doit(doit_coro1);
   cout << doit.get() << " - ";
   doit();
   cout << doit.get() << " - ";
   doit();
   cout << doit.get() << endl;
}

Ausgabe:

1 – 3 - 5

Mit dieser Fähigkeit sind Coroutinen eine einfache Lösung für manche komplexen Situationen. Stellen Sie sich z. B. eine "Türme von Hanoi"-Simulation vor, wie sie in Listing 6 zu sehen ist – mit einer typisch rekursiven Lösung.

Listing 6:

#include <iostream>
#include <limits>
#include <vector>
#include <string>
 
using namespace std;
 
//-------------------------------------------------------------------------------
 
class hanoi
{
public:
   void play(int count);
 
private:
   typedef vector<int> tower;
   typedef tower::size_type size;
 
   void move_tower(size layer, tower& source, tower& dest, tower& help);
   void move_slice(tower& source, tower& dest);
 
   void print() const;
   void print_tower_layer(tower const& t, int layer) const;
 
   tower start_tower_, middle_tower_, end_tower_;
   int count_;
   int move_;
};
 
//-------------------------------------------------------------------------------
 
void hanoi::play(int count)
{
   count_ = count;
   start_tower_.clear();
   middle_tower_.clear();
   end_tower_.clear();

   for (int i = count_; i > 0; --i)
   {
      start_tower_.push_back(i);
   }

   move_ = 1;
   print();
   move_tower(0, start_tower_, end_tower_, middle_tower_);
}

//-------------------------------------------------------------------------------

void hanoi::print_tower_layer(tower const& t, int layer) const
{
   size l = static_cast<size>(layer);
   int sw = t.size() <= l ? 0 : t[l];

   string::size_type space_count = static_cast<string::size_type>(count_ - sw);
   string::size_type slice_width = static_cast<string::size_type>(sw);

   string spaces(space_count, ' ');
   string half_slice(slice_width, '-');
   cout << spaces << half_slice << '|' << half_slice << spaces;
}

//-------------------------------------------------------------------------------

void hanoi::print() const
{
   cout << '\n' << move_ << ".\n";
   for (int layer = count_ - 1; layer >= 0; --layer)
   {
      cout << ' ';
      print_tower_layer(start_tower_, layer);
      cout << ' ';
      print_tower_layer(middle_tower_, layer);
      cout << ' ';
      print_tower_layer(end_tower_, layer);
      cout << '\n';
   }
   cout << string(6 * count_ + 7, '*') << '\n';
}

//-------------------------------------------------------------------------------

void hanoi::move_slice(tower& source, tower& dest)
{
   int slice = source.back();
   source.pop_back();
   dest.push_back(slice);
   ++move_;
   print();
}

//-------------------------------------------------------------------------------

void hanoi::move_tower(size layer, tower& source, tower& dest, tower& help)
{
   // Wenn die zu bewegende Ebene die oberste ist, 
   // dann kann die Scheibe direkt bewegt werden.
   if (layer == source.size() - 1)
   {
      move_slice(source, dest);
      return;
   }

   // Um den gesamten Haufen von Scheiben ab der angegebenen Ebene
   // zu bewegen, muss:
   // - zuerst der Haufen Scheiben ueber der Ebene zum Hilfs-Turm bewegt werden,
   // - dann die Scheibe zum Ziel-Turm bewegt werden, und dann
   // - der verschobene Haufen auf die bewegte Scheibe bewegt werden.
   size help_layer = help.size();
   move_tower(layer + 1, source, help, dest);
   move_slice(source, dest);
   move_tower(help_layer, help, dest, source);
}

//-------------------------------------------------------------------------------

int main()
{
   int count;
   for (;;)
   {
      cout << "Mit wie vielen Scheiben sollen die Tuerme von Hanoi gespielt werden: ";
      cin >> count;
      if (!cin.fail() && count > 0) break;
      cout << "\nEingabe-Fehler\n\n";
      cin.clear();
      cin.ignore(numeric_limits<streamsize>::max(), '\n');
   }

   hanoi h;
   h.play(count);
}

Ausgabe:

Mit wie vielen Scheiben sollen die Tuerme von Hanoi gespielt werden: 3

1.
   -|-      |       |
  --|--     |       |
 ---|---    |       |
*************************

2.
    |       |       |
  --|--     |       |
 ---|---    |      -|-
*************************

3.
    |       |       |
    |       |       |
 ---|---  --|--    -|-
*************************

4.
    |       |       |
    |      -|-      |
 ---|---  --|--     |
*************************

5.
    |       |       |
    |      -|-      |
    |     --|--  ---|---
*************************

6.
    |       |       |
    |       |       |
   -|-    --|--  ---|---
*************************

7.
    |       |       |
    |       |     --|--
   -|-      |    ---|---
*************************

8.
    |       |      -|-
    |       |     --|--
    |       |    ---|---
*************************

Die Ausgabe nach jeder Scheibenbewegung und das Incrementieren des Zug-Zählers passiert hier in der Funktion move_slice, die eine einzelne Scheibe bewegt. Denn jede Bewegung einer Scheibe entspricht einem Zug. Möchten wir es jetzt für einen Nutzer ermöglichen, dass er festlegt, was bei jeder Scheibenbewegung passiert – dann hätten wir ein kleines Problem. Wenn wir aus unseren Funktionen rausspringen, verlieren wir den Rekursions-Status. Eine mögliche Lösung ist die Parametrierung der Hanoi-Klasse mit einem Callable, das wir dann in move_slice  aufrufen. Für viele Situationen reicht diese Lösung – sie hat aber den Nachteil, dass die Flußkontrolle in der Hanoi-Klasse bleibt. Eine andere Lösungs-Alternative ist die händische Verwaltung des Stacks und der Verzicht auf die einfache rekursive Implementierung. Diese Lösung ist weitaus aufwändiger zu implementieren – ermöglicht es aber, die Flußkontrolle aus der Hanoi-Klasse zu entfernen. Eine dritte Lösung nutzt Coroutinen – mit denen wir aus einer Funktions-Aufrufkette herausspringen können, ohne dass der Status verloren geht, und auch wieder zurückspringen können. Diese Lösung finden Sie in Listing 7 – da sie in den meisten Teilen dem Listing 6 entspricht, hier nur die modifizierten Code-Stellen.

Listing 7:

using call_type = coroutine<int>::pull_type;
using back_type = coroutine<int>::push_type;
 
class hanoi
{
public:
   hanoi(int count);
   void play(back_type& yield);
 
private:
   typedef vector<int> tower;
   typedef tower::size_type size;
 
   void move_tower(back_type& yield, size layer, tower& source, tower& dest, tower& help);
   void move_slice(back_type& yield, tower& source, tower& dest);
 
   void print() const;
   void print_tower_layer(tower const& t, int layer) const;
 
   tower start_tower_, middle_tower_, end_tower_;
   int count_;
   int move_;
};
 
void hanoi::play(back_type& yield)
{
   move_ = 1;
   print();
   move_tower(yield, 0, start_tower_, end_tower_, middle_tower_);
}
 
void hanoi::move_slice(back_type& yield, tower& source, tower& dest)
{
   yield(move_);
   int slice = source.back();
   source.pop_back();
   dest.push_back(slice);
   ++move_;
   print();
}

void hanoi::move_tower(back_type& yield, size layer, tower& source, tower& dest, tower& help)
{
   if (layer == source.size() - 1)
   {
      move_slice(yield, source, dest);
      return;
   }

   size help_layer = help.size();
   move_tower(yield, layer + 1, source, help, dest);
   move_slice(yield, source, dest);
   move_tower(yield, help_layer, help, dest, source);
}

Wie Sie sehen, entspricht diese Lösung quasi exakt unserer ersten einfachen rekursiven Lösung in Listing 6, bis auf den zusätzlichen Boost Coroutinen-Parameter und den Aufruf von yield() in der Move-Funktion. Damit kehrt die Flußkontrolle an den Aufrufer zurück, der dann problemlos Schritt für Schritt die Simulation ablaufen lassen kann.

Zwischenfazit

• Coroutinen erlauben es uns, eine Funktion (oder mehrere) zu verlassen, ohne dass der Status der Funktion (der Stackframe) verloren geht, und den Rücksprung an die letzte Ausführungsstelle ohne dass der Kontext verloren geht.
• Eine typische Anwendung von Coroutinen sind z. B. Generatoren, die z. B. lazy berechnete unendliche Menge darstellen können. Boost.Coroutine2 bietet hierfür zusätzlich ein Iterator-Interface an, das die Verbindung von Coroutinen mit vielen C++-Features wie z. B. den STL-Algorithmen auf sehr einfache Art ermöglicht.
• Eine andere Anwendung sind Sprünge zwischen Kontexten – wie wir im "Türme von Hanoi"-Beispiel gesehen haben. Mit Coroutinen müssen wir hier z. B. nicht auf rekursive Lösungen verzichten – können die Flußkontrolle aber problemlos abgeben und zurückbekommen.
  Überhaupt zeichnet sich Coroutinen-Code dadurch aus, dass er eigentlich wie ganz normaler Code aussieht – d. h. einfach und verständlich ist, wenn man die Idee der Coroutinen verstanden hat.

Praxis

Was treibt Boost.Coroutine2 da eigentlich, um Coroutinen zu implementieren? Wie wird der gesamte Funktions-Kontext denn gesichert? Nun, es ist wirklich so, dass das Erzeugen einer Coroutine den kompletten Stack sichert. Und beim Aufruf wird der aktuelle Stack gegen den gesicherten Stack ausgetauscht. Was so aufwändig klingt, ist intern ganz einfach – es muss ja nur der Stackpointer (d. h. ein Register des Prozessors) gesetzt werden. Boost.Coroutine2 macht dies nicht selber, sondern nutzt dafür die Boost.Context. Hierbei ist die Bibliothek Boost.Context nicht portabel, da sie systemspezifische Elemente nutzt – sie funktioniert also nicht auf allen Plattformen. In der Boost.Context-Dokumentation [3] finden Sie alle von Boost.Context unterstützten Architekturen – nur dort können Sie auch Boost.Coroutine2 nutzen.

Coroutinen in ISO C++ und der Stand einiger aktueller Compiler

Noch einmal zurück zur Sprache C++: selbst wenn Coroutinen nicht Teil von C++17 geworden sind und auch nicht klar ist, wie sie vielleicht in C++20 oder später aussehen werden – so gibt es heute doch schon Möglichkeiten, Coroutinen direkt in C++ zu nutzen. Einige aktuelle Compiler unterstützen Coroutinen schon – wobei sich die Implementierungen unterscheiden und auch nicht klar ist, ob sich in C++20 oder später nicht noch was in der Schnittstelle oder dem Verhalten ändert. Man sollte solchen Code also vielleicht nicht in produktiver Umgebung einsetzen oder sich zumindest über das Problem im klaren sein.

• Microsoft Visual Studio 2015 und 2017
  Coroutinen müssen mit /await aktiviert werden
• LLVM / Clang 5
  Coroutinen müssen mit –enable-coroutines aktiviert werden

Mit einem dieser Compiler und aktivierten Coroutinen sieht dann ein Fibonacci-Generator, wie wir ihn in Listing 2 kennengelernt haben, ungefähr aus wie in Listing 8 [4][5].

Listing 8:

#include <iostream>
#include <generator>
 
std::generator<int> fib()
{
   int a = 0;
   int b = 1;
   for (;;) 
   {
      co_yield a;
      auto next = a + b;
      a = b;
      b = next;
   }
}
 
int main()
{
   for (auto v : fib()) 
   {
      if (v > 50) break;
      std::cout << v << ' ';
   }
   std::cout << std::endl;
}

Ausgabe:

0 1 1 2 3 5 8 13 21 34

Coroutinen und Multithreading

Aber halt – stopp! Das kann doch nicht alles gewesen sein! Häufig wenn man von Coroutinen hört, dann passiert das im Umfeld von Multithreading. Und von MT haben wir hier bislang nichts gehört. Das ist richtig, denn erstmal haben Coroutinen selber nichts mit MT zu tun. Zusammen mit dem neuen Schlüsselwort co_await wird das in C++20 oder später vielleicht anders aussehen – aber erstmal nicht. Trotzdem kann man mit Coroutinen natürlich eine Art "kooperatives Multithreading" simulieren. Denn das Springen zwischen zwei oder mehr Funktionen (vergleiche nochmal Abb.1) ist ja eine Art Multithreading, nur dass der Wechsel zwischen den Coroutinen nicht automatisch passiert, sondern händisch getriggert werden muss – halt "kooperatives Multithreading".

Die großen Vorteile von Coroutinen gegenüber Threads sind hierbei die Performancekosten und die Skalierbarkeit – ein Threadwechsel ist viel teurer als ein Coroutinen-Wechsel und Coroutinen können so viele erzeugt werden, wie Speicher vorhanden ist. Wenn man jetzt komfortabel kooperatives Multithreading mit Coroutinen nutzen möchte, dann musste man sich bisher meist selbst einen Coroutinen-Scheduler und einige andere Infrastruktur-Elemente schreiben. Seit Boost 1.63.0 gibt es in Boost eine Fiber-Bibliothek, die diese Aufgaben übernimmt. Aber das sprengt den Rahmen dieses einführenden Artikels über Coroutinen am Beispiel von Boost.Coroutine2. Ein weiterer Artikel über kooperatives Multithreading mit Coroutinen und Boost.Fiber wird folgen.

Autor

Das könnte Sie auch interessieren