Prinzipielle Frage über Coroutinen



  • Hi!

    Es gab ja schon mal eine Diskussion hier über Coroutinen und hier und da höre ich auch von ihrer Verwendung. Mir erschließt sich leider noch nicht wirklich ihre Daseinsberechtigung, außer als syntaktischer Zucker.
    In diesem Video, in dem jemand die Fibers, also User-Mode-Threads mit kooperativem Scheduling, vorstellt, wird behauptet, sie seien besser als Threads, z.B. weil man sich Kernel-Mode-Kontextwechsel erspart und dadurch tausende von Fibers haben kann. Das finde ich irgendwie manchmal haltlos oder ich verstehe es nicht ganz.

    Zum einen sind Threads nicht nur von einem preemptiven Scheduler gesteuert, sondern man kann ebenso kooperativ den Thread schlafen legen, wenn er nichts zu tun hat, sodass der Scheduler einen Kontextwechsel in einen anderen Thread macht. Wieso sollte das viel teurer als ein Coroutine/Fiber-yield() sein, der genauso irgendeine Form von Kontextwechsel durchführt (und insbesondere auch noch mit einem Mutex synchronisiert werden muss, da Fibers zwischen Threads wandern können)? Es ist selten eine gute Idee, mehr logische als echte Threads zu haben, die etwas anderes tun als Schlafen. Und falls doch, dann verhindert der preemptive Scheduler, dass sie verhungern und man kann die Zahl wieder herunterregeln. Fibers sind, wie ich es verstehe, rein kooperativ, also sollten sie doch sehr anfällig gegen Starvation sein?

    Weiß da jemand was?



  • Jodocus schrieb:

    Es gab ja schon mal eine Diskussion hier über Coroutinen und hier und da höre ich auch von ihrer Verwendung. Mir erschließt sich leider noch nicht wirklich ihre Daseinsberechtigung, außer als syntaktischer Zucker.
    In diesem Video, in dem jemand die Fibers, also User-Mode-Threads mit kooperativem Scheduling, vorstellt, wird behauptet, sie seien besser als Threads, z.B. weil man sich Kernel-Mode-Kontextwechsel erspart und dadurch tausende von Fibers haben kann. Das finde ich irgendwie manchmal haltlos oder ich verstehe es nicht ganz.

    Mit nem Context-Switch aka. Thread-Wechsel ist die CPU halt einige Zeit beschäftigt. Das entfällt völlig, wenn du Pseudo-Threads in Form von Fibers oder Coroutines verwendest.

    Hat man allerdings mehrere CPUs/Kerne, ist echtes Multithreading besser, da Coroutines eben nur eine Simulation sind.



  • Ich glaube, in diesem Artikel recht gute Antworten gefunden zu haben, zumindest auf Windows:

    1. Kontextwechsel von Threads sind nur durch den Übergang in den Kernel-Mode und das Acquire/Release eines Spin-Locks teurer als Fibers und letzteres ist (so Stand 2005) nicht mehr nennenswert. Insbesondere sind Cache-Zugriffszeiten sehr viel relevanter als früher, wo Fibers keine Vorteile bringen.
    2. Speziell auf Windows sind Thread-Pools und IOCPs, also Konstrukte, um die Anzahl der Kontextwechsel zu minimieren, mindestens genau so gut. Performance-Technisch könnten sie also höchstens etwas auf Linux bringen, wo es sowas nicht gibt.
    3. Coroutinen nur dafür zu benutzen, um eine Callback-Hell zu vermeiden und asynchronen Code sequentiell aussehen zu lassen, ist schon leicht fahrlässig, da man, wenn man nur selten einen Kontextwechsel erlaubt, bei Oversubscription Probleme mit Starvation bekommt, wohingegen man bei zu vielen den hohen Preis von Kontextwechseln bezahlt und der Code nun mehr alles andere als schick aussieht, wenn überall zufällige "yields" stehen. Was Multithreading angeht, scheinen mir Coroutinen eher nicht das Mittel der Wahl zu sein.



  • Ich habe bisher Coroutinen nicht als Mittel für Multithreading verstanden, sondern wirklich als syntaktischer Zucker bzw. als neue Kontrollkonstrukte. Also für sowas wie Generatoren in Python, mit denen man viele Iteratoren deutlich angenehmer implementieren kann. Aber schlussendlich so, dass die Kontextwechsel quasi ein Implementierungsdetail sind und trotzdem alles sequenziell abläuft.

    Also wozu werden sie verwendet? Einfach für schöneren Code. Als weitere Möglichkeit, die Programmlogik zu strukturieren. In Sprachen wie Python ist das offensichtlich, aber ob das in Sprachen ohne native Unterstützung, wie z.B. C++, auch noch gilt, muss wohl jeder für sich entscheiden. Gegebenenfalls kannst du da auch einen Blick auf boost::coroutine (eher low-leve) und boost::context (etwas mehr high-level, basiert auf boost::coroutine ) werfen.

    Etwas abseits vom Thema, falls du auf der Suche nach Alternativen für Threads bist, dann kannst du dich auch mal mit green threads beschäftigen (die gibt es z.B. in Go, Erlang oder Haskell). Im Endeffekt sind das Usermode-Threads, die von der Runtime verwaltet werden, aber sich effektiv wie echte Threads verhalten, die nur viel billiger sind. Also in den genannten Sprachen ist es ohne weiteres möglich, mehrere hunderttausend Threads zu starten, die dann auf wenige tatsächliche OS-Threads gemappt werden. Ich weiß allerdings nicht, welche Lösungen es dafür in C++ gibt.



  • ipsec schrieb:

    Etwas abseits vom Thema, falls du auf der Suche nach Alternativen für Threads bist, dann kannst du dich auch mal mit green threads beschäftigen (die gibt es z.B. in Go, Erlang oder Haskell). Im Endeffekt sind das Usermode-Threads, die von der Runtime verwaltet werden, aber sich effektiv wie echte Threads verhalten, die nur viel billiger sind.

    Aber wenn einer dieser Green Threads in einer längeren Schleife verweilt, wird er nicht unterbrochen* und andere Green Threads bekommen Rechenzeit zugeteilt, oder doch?

    😉 Bei "echten" Threads ist es so.



  • ipsec schrieb:

    Ich habe bisher Coroutinen nicht als Mittel für Multithreading verstanden, sondern wirklich als syntaktischer Zucker bzw. als neue Kontrollkonstrukte. Also für sowas wie Generatoren in Python, mit denen man viele Iteratoren deutlich angenehmer implementieren kann. Aber schlussendlich so, dass die Kontextwechsel quasi ein Implementierungsdetail sind und trotzdem alles sequenziell abläuft.

    Ich bisher auch nicht, bis ich z.B. deren Verwendung in boost asio entdeckt habe (asio::spawn), wo es im Prinzip nur zur Aufhübschung benutzt wird. Green Threads scheinen mir ideell das Selbe wie Coroutinen/Fibers zu sein. Womit ich ein Problem habe, ist die irgendwie zu Grunde liegende Vermutung, man sei cleverer oder schneller als der Kernel und der Scheduler und könne das selber im Usermode besser machen.



  • Andromeda schrieb:

    [Aber wenn einer dieser Green Threads in einer längeren Schleife verweilt, wird er nicht unterbrochen* und andere Green Threads bekommen Rechenzeit zugeteilt, oder doch?

    Doch, Green Threads sind präemptiv. Man muss lediglich aufpassen bei syscalls o.ä., die den OS-Thread blockieren und damit auch alle anderen Green Threads, die auf demselben OS-Thread laufen. Das kann man lösen durch asynchrone IO, in Sprachen mit nativen Green Threads macht das die Runtime in der Regel automatisch.

    Jodocus schrieb:

    Womit ich ein Problem habe, ist die irgendwie zu Grunde liegende Vermutung, man sei cleverer oder schneller als der Kernel und der Scheduler und könne das selber im Usermode besser machen.

    Aber es ist Fakt. Starte mal eine million OS-Threads und eine million Go-Routinen in Go und vergleiche das Ergebnis. In einem anderen Thread hattest du ein Problem beschrieben, dass das System instabil wird, wenn zu viele Threads gestartet werden. Ich nehme an, die Grenze liegt da bei wenigen tausend. Mit Green Threads hat man diese Probleme einfach nicht.

    Der Grund ist natürlich nicht, dass die Kernel-Entwickler keine Ahnung vom Scheduling haben, sondern dass der Verwaltungsaufwand für Green Threads deutlich geringer ist. Ein kompletter Kontextwechsel ist nunmal sehr teuer. Bei Green Threads werden im günstigsten Fall lediglich die Register gespeichert und geladen und ein simples jmp ausgeführt.



  • ipsec schrieb:

    Doch, Green Threads sind präemptiv. Man muss lediglich aufpassen bei syscalls o.ä., die den OS-Thread blockieren und damit auch alle anderen Green Threads, die auf demselben OS-Thread laufen. Das kann man lösen durch asynchrone IO, in Sprachen mit nativen Green Threads macht das die Runtime in der Regel automatisch.

    Okay, wenn sie präemptiv sind, ist die inhärente Gefahr durch Verhungern weitaus geringer. Wie du schon andeutest, muss man sehr aufpassen, dass man nicht versehentlich blockiert. Wenn man z.B. einen Thread hat, in dem Fibers/Green Threads laufen, die entweder auf gemeinsame Ressourcen zugreifen (also auch eine gewisse Lock-Contention haben) oder vollkommen autark arbeiten, so werden die autonomen Green Threads trotzdem durch die Lock-Contention beeinflusst, da der Thread ja insgesamt am Mutex blockiert. Als Programmierer kann man nicht wissen, ob etwa in irgendeiner Datenstruktur ein Mutex lauert oder nicht. Das würde also bedeuten, man müsste auch Green Mutexe basteln, die nicht den ganzen Thread blockieren, sondern den nächsten Aufrufen - man müsste also alle Datenstrukturen entsprechend umbauen.

    Der Grund ist natürlich nicht, dass die Kernel-Entwickler keine Ahnung vom Scheduling haben, sondern dass der Verwaltungsaufwand für Green Threads deutlich geringer ist. Ein kompletter Kontextwechsel ist nunmal sehr teuer. Bei Green Threads werden im günstigsten Fall lediglich die Register gespeichert und geladen und ein simples jmp ausgeführt.

    Wäre es nicht besser, der Kernel würde an sich Threads anbieten, die nur einen "Kontextwechsel light" durchführen, anstatt "Staat im Staat"-mäßig das den Anwendungen zu überlassen?



  • Jodocus schrieb:

    Wäre es nicht besser, der Kernel würde an sich Threads anbieten, die nur einen "Kontextwechsel light" durchführen, anstatt "Staat im Staat"-mäßig das den Anwendungen zu überlassen?

    Du willst Syscalls haben, die dir die Latenz von Syscalls eliminieren?



  • dachschaden schrieb:

    Jodocus schrieb:

    Wäre es nicht besser, der Kernel würde an sich Threads anbieten, die nur einen "Kontextwechsel light" durchführen, anstatt "Staat im Staat"-mäßig das den Anwendungen zu überlassen?

    Du willst Syscalls haben, die dir die Latenz von Syscalls eliminieren?

    Dass der Übergang zum Kernel-Mode auf aktuellen Systemen teuer ist (z.B. per SYSENTER), wage ich mal zu bezweifeln. Das stärkere Argument war ja, dass Green Threads keinen vollständigen (da unnötigen) Kontextwechsel durchführen. Das scheint ein sinnvoller Ansatz zu sein, wenn man es auf viele Kontextwechsel ankommen lassen will. Der Ansatz, möglicht wenig Kontextwechsel zu haben, die dafür dann komplette Kontextwechsel sind, könnte man eigentlich gut durch Green Threads ergänzen, um das beste aus beiden Welten zu haben. Daher halte ich Sachen wie Green Threads für weniger als Sprachfeature sondern mehr als Kernel-Feature geeignet. Sachen wie Scheduling gehören imho nicht in Applikationen außerhalb des Kernels.



  • Jodocus schrieb:

    Das würde also bedeuten, man müsste auch Green Mutexe basteln, die nicht den ganzen Thread blockieren, sondern den nächsten Aufrufen - man müsste also alle Datenstrukturen entsprechend umbauen.

    Ja, die braucht man. In Go gibt es dafür die Channel, in Haskell gibt es MVar etc. und der jeweilige Scheduler in der Runtime kann damit umgehen und schedult z.B. keine Threads, die gerade durch einen Mutex gelockt sind. Also im Prinzip so, wie es der Kernel auch macht.

    Du hast natürlich recht, es wäre schön, wenn der Kernel bzw. das OS sowas von sich aus schon anbieten würde. Unter Windows gibt es ja dafür die Fiber, die man nutzen kann, um ein solches System zu bauen. Natürlich ist es trotzdem noch relativ aufwendig. Unter Linux ist mir nichts vergleichbares bekannt.

    Aber auf der anderen Seite, natürlich sind die Kernel-Entwickler sehr kompetent, aber auch nicht heilig. Es gibt prinzipiell keinen Grund, warum die Usermode-Scheduler schlechter als der des Kernels sein sollten. Und es handelt sich hierbei um ein Problem, welches sich komplett innerhalb der Anwendung abspielt und was mit dem restlichen System überhaupt nichts zu tun hat. Warum sollte man das dem Kernel überlassen?

    Die Implementierung ist halt leider relativ aufwendig, insbesondere wenn die Sprache recht low-level ist und eigentlich nicht darauf ausgelegt wurde. Aber es scheint tatsächlich auch für C ein paar Bibliotheken zu geben, siehe z.B. diese SO-Frage.



  • Unter Windows sind Fibers ja leider auch nur rein kooperativ. Natürlich muss ein UM-Scheduler nicht schlechter sein als einer im Kernel-Mode, aber unter dem Gesichtspunkt kommt es mir dann schon so wie die Mutter aller premature optimizations vor, wenn einem der Scheduler nicht passt. 😉

    Danke für die Klarstellungen/Anregungen.



  • Jodocus schrieb:

    Dass der Übergang zum Kernel-Mode auf aktuellen Systemen teuer ist (z.B. per SYSENTER), wage ich mal zu bezweifeln.

    Seit Version 2.3.4 der Glibc speichern sie den Return von getpid , weil sie ansonsten den Kernel davon anhauen müssten. Weil der Wechsel in Kernelmode nun mal teuer ist. Auch heute noch. Aber nicht so teuer, dass ich das bei Threads jemals bemerkt hätte.

    Ich sag's direkt, mit Userland-Threads (a.k.a Green Threads) habe ich noch nicht gearbeitet, weil meiner (persönlichen) Erfahrung nach die Kontextwechsel nie das Problem waren. Was das Problem war, ist dass Windows dich den zu verwendenden Stackspeicher nicht auswählen lässt und pthreads, wenn du den Stackspeicher nicht selbst setzt, auch stark unterdurchschnittlich performt.

    Sobald ich diesen Flaschenhals dann mal eliminiert habe, habe ich mit pthreads (meines Wissens nach Kernel-Threads) einen Load Average von > 3000 erzeugt, und das System hat noch reagiert. Verzögert, aber es war da.

    EDIT: Auf Linux natürlich. Windows lässt dich den Thread-Speicher auch mit pthreads (gibt ja Windows-Implementierungen) nicht auswählen.



  • Ich hab bisher ein mal coroutines verwendet. Ich hatte eine öffentliche Iterator Schnittstelle, intern aber eine rekursive Suche. Sobald die rekursive Funktion was interessantes gefunden hat, hat sie dann quasi yield aufgerufen.
    War im Endeffekt Spielerei, weil ich mal coroutines verwenden wollte 😉 An der Stelle hätte ich einfach alles durchsuchen und dann über die Ergebnisse iterieren können.



  • Ich hatte Fibers(Windows-Leichtgewichtige-Threads-Nur-Kooperativ) verwendet, als WinXP bei 3400 Threads (mit je supi sparsam stack und beliebig viel damals einbaubarem RAM) abgekackt ist und kam nicht echt weiter. Fibers sind nicht besser als Threads und die sind, behaupte ich mal, in fast allen bezahlten Anwendungen nicht besser als Prozesse.

    Ich will zwei 22-Kerner auf Dual-Board mit Hyperthreading haben, was 88 Threads macht und die Compilerfehlermeldung kommt gefühlt in die IDE lange bevor ich die Compile-Taste gedrückt habe.



  • volkard schrieb:

    [Threads] sind, behaupte ich mal, in fast allen bezahlten Anwendungen nicht besser als Prozesse.

    • Datenaustausch zwischen Threads eines Prozesses geht richtig schnell.
    • belegen keine doppelten COW-Einträge in der Page Table (ist egal, ob die COW oder RO sind, Hauptsache ist, sie existieren und können somit zu Page Walks führen).
    • sind wesentlich schneller zu erstellen (ein Benchmark von mir aus dem Jahr 2013 auf Linux zeigte, dass Threads so um den Fatkor 50 schneller erstellt werden als zu forken).
    • (auf Linux) kannst du deinen eigenen Speicher als Threadstack angeben, was noch mal die Leistung hochbringt.

    Gegenargumente?



  • Ähhhh, Quatsch, Faktor 25. Forken war 50 Zeiteinheiten, Thread erstellen zwei.



  • dachschaden_off schrieb:

    volkard schrieb:

    [Threads] sind, behaupte ich mal, in fast allen bezahlten Anwendungen nicht besser als Prozesse.

    • Datenaustausch zwischen Threads eines Prozesses geht richtig schnell.
    • belegen keine doppelten COW-Einträge in der Page Table (ist egal, ob die COW oder RO sind, Hauptsache ist, sie existieren und können somit zu Page Walks führen).
    • sind wesentlich schneller zu erstellen (ein Benchmark von mir aus dem Jahr 2013 auf Linux zeigte, dass Threads so um den Fatkor 50 schneller erstellt werden als zu forken).
    • (auf Linux) kannst du deinen eigenen Speicher als Threadstack angeben, was noch mal die Leistung hochbringt.

    Gegenargumente?

    [Threads] sind, behaupte ich mal, in fast allen bezahlten Anwendungen nicht besser als Prozesse.
    Mir geht es nicht um theoretische Mikromessungen oder Gamecoding, sondern das, wo der Kunde fett Geld bezahlt für die Software.
    Die Mikroargumente kenne ich alle, klar, ich bin auch ein Fan davon, dem Thread 64k eigenen Stackspeicher unterzuschubsen, und dann auch gleich noch innerhalb des Threads davon 32k abzuwacken und ein selbergeschriebenes malloc/free darauf aufsetzten.


Log in to reply