[C++] Suche Parallel Execution Lib

[Schrompf]

Moin Loite,

ich bin auf der Suche nach einer Bibliothek, in die ich beliebige Tasks reinschmeißen kann, so dass sie auf allen verfügbaren Kernen parallel ausgeführt werden.

Pflicht-Kriterien:
- mindestens Windows / Mac / Linux
- taugt für vielfältige und evtl. blockierende Aufgaben, nicht nur Parallelisierung eines Algorithmus

Wunsch-Kriterien:
- niedrige Latenz bei verfügbaren Threads, im Idealfall <1ms
- weitere Plattformen, z.B. Konsolen
- Abhängigkeiten zwischen Tasks, also dass C erst losläuft, wenn A und B fertig sind

Bisher habe ich Intels Threading Building Blocks benutzt, aber der schließt explizit I/O und alle sonstigen blockierenden Aktionen aus. Außerdem ist das Ding extrem auf die "billige" Parallelisierung spezialisiert, also das Aufteilen eine billig parallelisierbaren linearen Algorithmus auf mehrere Kerne. Pfft. Für diesen Job bietet Microsoft die Concurrency Runtime an, die aber windows-spezifisch ist, also ausfällt. Bisher habe ich im kleinen Maßstab mit std::async() gearbeitet, was auf dem GCC aber nur sequentiell ausgeführt wird. Dann habe ich http://threadpool.sourceforge.net/index.html gefunden, was gut aussieht, aber zumindest keine Inter-Job-Dependencies kann. Außerdem scheint es schon etwas älter, was mich immer skeptisch macht. Dafür ist es Header-only, ein echtes Plus in Zeiten von CMake und make install.

Hat jemand eine Empfehlung? Erfahrungswerte? Danke im Voraus.

[Matthias Gubisch]

Das Problem mit blockierenden Tasks bei der Intels TBB kann ich nachvollziehen, die Tasks dort können leider nicht unterbrochen werden.
Die "billige" Parallelisierung stimmt so nicht ganz. Schau dir mal den Task Scheduler an, mit dem hab ich schon ne gesamte Game Engine Paralleisiert bekommen, der kann beliebige Tasks und auch Abhänigkeiten davon abarbeiten.

Konzeptionell hab ich für jeden Frame eine Anzahl Tasks (Grafik, Physik, Sound, usw..., teilweise auch mit subtasks) gestartet. Das Problem mit der Blockierenden IO hab ich dadurch gelöst dass ich die in nem speraten Thread mache und zu Begin jedes Frames bevor die Tasks erneut gestartet werden diesen nach Aktualisierungen gefragt, im Schlimmsten Fall hast du also 1en Frame versatz drinnen.
Management von blockierenden Tasks ist für solche Manager auch nicht immer ganz einfach. Einfallen würde mir jezt auf die schnelle keiner.

Ansonsten kann man sich sowas mit boost::thread auch relativ schnell und einfach selber bauen. Das sollte auch die Probleme von std::async unter gcc nicht haben (zumindest sind sind diese mir so nicht bekannt)

[Spiele Programmierer]

std::thread
Und wenn du außergewöhnliche Anforderungen hast, implementiere die Task-Verwaltung doch einfach selbst.

[Schrompf]

Ok, dann schau ich mit TBB nochmal an. Und ich fand gar nicht, das meine Anforderungen so außergewöhnlich sind. Ich dachte eher, das wär Standardkram, den jeder irgendwie braucht. Und gleichzeitig weiß ich, was man bei paralleler Programmierung alles falsch machen kann, daher hoffte ich, eine getestete Lösung von jemandem zu finden, der mehr von dem Fach versteht. Ich bekomme sicher auch was hin, aber ich würde im Laufe des nächsten Jahres noch den einen oder anderen Tag an Fehlerjagd einplanen müssen.

Mein aktueller Plan lautet jetzt: Intels TBB für alle kritischen Aufgaben, die jedes Frame anfallen, und so Dinge wie Texturen laden separat davon in nem selbsterstellten Thread.

[hagbard]

OpenMP kann sowas wenn es der Compiler unterstützt. Kenne es aber nur vom hören sagen. Ich glaube da ist auch viel Handarbeit nötig...

[kristof]

Ich kann zwar keine fertige Lib empfehlen, hab aber kürzlich einen sehr interessanten GDC talk zu dem Thema gesehen:

Slides: http://www.swedishcoding.com/2015/03/08 ... og-engine/
Aufzeichnung: http://www.gdcvault.com/play/1022186/Pa ... Dog-Engine

Ich hab das basierend darauf auch mal selbst ausprobiert und war erstaunt wie einfach das zu implementieren ist wenn man einmal verstanden hat wie Fiber funktionieren. Leider ist mir nicht bekannt ob es eine fertige und abgehangene Lib gibt, die das implementiert.

[dot]

Die Windows API hat schon praktisch immer Support für Fibers (MSVC hat sogar einen switch für Fiber-Safe Thread-Local Storage), wie's auf Linux und Mac aussieht, kann ich leider nicht genau sagen (notfalls das hier). Es sollte auf jeden Fall Libraries dafür geben, da spezieller Kernel Support nicht notwendig ist (genau das ist am Ende ja die Idee). Oft lauft das Ding auch unter "user level threads" oder "light-weight processes"...

[kristof]

Die set/getcontext API ist leider deprecated und nicht mehr Teil von POSIX. Unter Mac OS X zumindest gibt es nichts vom OS selbst. Ich hab es mit ein paar Zeilen inline Assembly gelöst. Man muss wirklich nur den Stack Pointer austauschen und eine Hand voll Register abspeichern.

[Krishty]

Was haben Fibers damit zu tun? Die sind doch seriell?

[dot]

Ich denk die Idee ist, einen Thread pro Core zu machen und darauf dann per Fibers selbst kooperatives Multitasking zu implementieren. Ich wäre jetzt auch nicht so begeistert davon...

[Schrompf]

Eigentlich kling es wie ne dumme Idee - Threadwechsel wären wohl deutlich teurer, wenn ich sie unter dem Namen "Fiber" selbst implementiere, als wenn ich die des OS-Task Schedulers nehme. Laut Präsentation hat Dice damit wohl "Ripple Effects" vermieden, weil der PS4-Scheduler die Threads fröhlich zwischen den Cores rumgeschoben hat. Hm. Allgemein ist die ganze Präsentation nur auf PS4 beschränkt. Ich vermute mal, diese Funktionen zum freundlichen Speichern und Wiederherstellen des aktuellen Thread-Zustands gibt es anderswo gar nicht.

Ich habe dabei aber gelernt, dass auch ein Job Queue System seine eigenen Probleme hat. In der Präsentation z.B. wurde der Fall genannt, dass ein Teil der Spiellogik ein paar Raycasts abfeuert und dann auf deren Ergebnis wartet. Das führt zu nem Deadlock, wenn man das innerhalb eines Job-Systems macht, wo jeder Task ununterbrochen bis zum Ende läuft. Aber wenn ich das richtig verstehe, könnte man das Thema einfach mit weiteren Threads lösen. Also z.B. doppelt so viele Worker Threads wie Prozessorkerne, aber die in Pärchen organisiert, so dass der Zweitthread eines Kernes nur dann einen Job bekommt, wenn der primäre Thread innerhalb eines Tasks auf was wartet. Keine Ahnung, wie die Task Scheduler damit klar kommen, aber ich vermute mal, dass auch 48 anstatt 8 Threads noch kein modernes OS in Bedrängnis bringen.

[kristof]

Das schöne an Fibers in dem Zusammenhang ist, dass man sie anhalten kann um auf die Fertigstellung anderer Unteraufgaben zu warten ohne den darunter liegenden OS Thread zu blockieren. Aus Sicht des Jobs sieht das warten dann aus wie ein einfacher Funktionsaufruf (waitForSomethingToHappen() oder so). Allerdings kann der selbe Job danach auf einem beliebigen freien Worker Thread wieder aufwachen.
Ich will jetzt auch nicht sagen, dass das in allen Situationen sinnvoll ist und hab selbst, bis auf ein paar kleine Spielereien, noch keine praktische Erfahrung damit. Der Talk hat mich aber sehr beeindruckt.

[Krishty]

Nein; sie benutzen Fibers damit sie deutlich mehr Jobs (160) einreihen können als sie Threads haben (8). Nagut; macht vielleicht wirklich vieles einfacher.

[kristof]

Die Zahl der Fibers begrenzt wie viele Jobs zu einem Zeitpunkt auf Unteraufgaben warten dürfen. Jobs können beliebig viele eingereiht sein. Oder verstehe ich dich falsch?
EDIT: Ausserdem ist ein Context Wechsel von Fiber zu Fiber wesentlich günstiger (Im Grunde vergleichbar mit einem Funktionsaufruf) als von Thread zu Thread. Dabei müssen nämlich immer alle Register gespeichert werden.

[Spiele Programmierer]

Was spricht gegen eine Implementierung in (Standard) C++ mit ganz normalen std::thread Threads?
Anstatt "waitForSomethingToHappen" kann man doch einfach den Job aufteilen - also einen neuen Job erstellen, der dann losläuft, wenn die Wartebedinung erfüllt ist und den Alten beenden.

Zu viele Threads sind prinzipiell schon ungünstig. Und besonders wenn man gerne viele Dinge auf dem Stack legt, schlägt sich das auf dem Speicherverbrauch nieder.

[Schrompf]

Ausserdem ist ein Context Wechsel von Fiber zu Fiber wesentlich günstiger (Im Grunde vergleichbar mit einem Funktionsaufruf) als von Thread zu Thread. Dabei müssen nämlich immer alle Register gespeichert werden.

Warum muss man das bei Fibern nicht machen? Die Präsentation erwähnt mehrfach eine PS4-eingebaute Funktion, die genau das tut. Also wenn ich das richtig verstehe, ist das eigentlich genau ein Thread-Wechsel, nur halt handprogrammiert.

Was spricht gegen eine Implementierung in (Standard) C++ mit ganz normalen std::thread Threads?
Anstatt "waitForSomethingToHappen" kann man doch einfach den Job aufteilen - also einen neuen Job erstellen, der dann losläuft, wenn die Wartebedinung erfüllt ist und den Alten beenden.

Naja, genau das "Job beenden" ist ein Problem, wenn Du mitten im Ausführen einer Aufgabe einen anderen Job starten und auf dessen Ergebnis warten willst.

Zu viele Threads sind prinzipiell schon ungünstig. Und besonders wenn man gerne viele Dinge auf dem Stack legt, schlägt sich das auf dem Speicherverbrauch nieder.

Ja, jeder Thread kostet Speicher; für Verwaltung und vor allem für Stack. Aber auch jeder Fiber kostet Speicher, zumindest für den Stack exakt genauso viel. Die Präsentation schrieb, dass sie 160 Fibers vorallokiert hätten, mit 128kb oder 512kb Stack. Der Speicherbedarf dürfte also immer grob derselbe sein.

[Krishty]

Die Zahl der Fibers begrenzt wie viele Jobs zu einem Zeitpunkt auf Unteraufgaben warten dürfen. Jobs können beliebig viele eingereiht sein. Oder verstehe ich dich falsch?

Stimmt; das sagt es noch besser.

EDIT: Ausserdem ist ein Context Wechsel von Fiber zu Fiber wesentlich günstiger (Im Grunde vergleichbar mit einem Funktionsaufruf) als von Thread zu Thread. Dabei müssen nämlich immer alle Register gespeichert werden.

Nein; das hat mit Registern nichts zu tun. Threads sind teuer und kein Programmierer, der bei Trost ist, würde 300 Threads anlegen wenn er 300 Aufgaben zu erledigen hat. Darum übergibt man herkömmlichen Thread Pools immer nur Funktionszeiger – man behält die feste Anzahl Threads, und die wechseln die Funktionen, die sie ausführen. Nur wenn die Threads auf Unteraufgaben aus anderen Jobs warten müssen, wird es kritisch, und da sind dann Fibers (besser: Koroutinen) günstig.

[kristof]

Warum muss man das bei Fibern nicht machen? Die Präsentation erwähnt mehrfach eine PS4-eingebaute Funktion, die genau das tut. Also wenn ich das richtig verstehe, ist das eigentlich genau ein Thread-Wechsel, nur halt handprogrammiert.

Aus Sicht des wartenden Jobs muss ja eine Funktion aufgerufen werden. Das heisst, dieser muss alle Register, entsprechend der Calling convention, sichern, die er danach noch verwenden will. Das kann der Compiler natürlich schön optimieren. Bei dem Wechsel zu einem anderen Fiber müssen also nur die Register gespeichert werden, die nach der Calling convention von der aufgerufenen Funktion zu sichern sind. Unter Mac OS X 64bit sind das rsp, rbp, rbx, r12, r13, r14, r15 Die muss man auch immer sichern, da man ja nicht weiss, was der Fiber der danach aufgerufen wird, mit den Registern macht.
Ein OS Thread Context Wechsel kann ja grundsätzlich immer passieren. Das heisst, es müssen auch immer alle Register gesichert werde.
Natürlich werden die Fiber immer noch auf OS Threads ausgeführt, was heisst, dass man trotzdem solche Context Wechsel bekommt. Wenn man aber die Worker Threads auf die physischen Cores mapped und nur so viele Worker hat wie Cores, sollten man die Contextswitches deutlich reduzieren können.

[Spiele Programmierer]

Naja, genau das "Job beenden" ist ein Problem, wenn Du mitten im Ausführen einer Aufgabe einen anderen Job starten und auf dessen Ergebnis warten willst.

Deshalb würde ich eben vorschlagen, dass man einen Job mit Wartezeiten aufteilt, auch weil ich schon das befürchtet hatte: "dass sie 160 Fibers vorallokiert hätten, mit 128kb oder 512kb Stack. "
128KB Stack ist eh ziemlich wenig. Und 512KB * 160 = 80MB !!!

[dot]

Eigentlich kling es wie ne dumme Idee - Threadwechsel wären wohl deutlich teurer, wenn ich sie unter dem Namen "Fiber" selbst implementiere, als wenn ich die des OS-Task Schedulers nehme.

Nein, ganz im Gegenteil, das ist ja gerade die Idee von Fibers. Wechsel zwischen den Kernel Threads, die der OS-Scheduler verwaltet, bedeuten unter anderem einen fetten Kernel Mode Switch; Fibers sind nicht präemptiv sondern kooperativ, d.h. du musst im Fibercode selbst den "Scheduler" aufrufen, dafür lauft aber alles rein im User Space. Effektiv kannst du damit viele "virtuelle Threads" auf einen OS-Thread multiplexen, musst dich um deren Scheduling aber selbst kümmern...

[Krishty]

Aus Sicht des wartenden Jobs muss ja eine Funktion aufgerufen werden. Das heisst, dieser muss alle Register, entsprechend der Calling convention, sichern, die er danach noch verwenden will. Das kann der Compiler natürlich schön optimieren. Bei dem Wechsel zu einem anderen Fiber müssen also nur die Register gespeichert werden, die nach der Calling convention von der aufgerufenen Funktion zu sichern sind. Unter Mac OS X 64bit sind das rsp, rbp, rbx, r12, r13, r14, r15 Die muss man auch immer sichern, da man ja nicht weiss, was der Fiber der danach aufgerufen wird, mit den Registern macht.

Nein. Ein Fiber-Wechsel ist immer ein Aufruf ins Betriebssystem, und DAS kümmert sich um Speichern und wiederherstellen des Kontexts, und NICHT der Compiler. Der Grund, warum Fibers weniger Overhead haben, ist, dass das Umschalten nicht den Scheduler des Betriebssystems (und damit nicht den Kernel Mode) passieren muss.

[kristof]

Nein. Ein Fiber-Wechsel ist immer ein Aufruf ins Betriebssystem, und DAS kümmert sich um Speichern und wiederherstellen des Kontexts, und NICHT der Compiler. Der Grund, warum Fibers weniger Overhead haben, ist, dass das Umschalten nicht den Scheduler des Betriebssystems (und damit nicht den Kernel Mode) passieren muss.

Unter Windows gibt es die Funktionen rund um ConvertThreadToFiber. Das sind natürlich aufrufe ins Betriebssystem und da kann ich auch nicht sagen was die für nen Overhead haben. Ich habe Fibers unter Mac OS X allerdings selber implementiert. Dazu braucht man ein paar Zeilen inline Assembly jedoch garantiert keinen Aufruf ins Betriebssystem. Wie gesagt, man muss nur eine Hand voll Register retten. Dafür braucht man keine besonderen Rechte. Es würde mich wundern wenn Fiberwechsel unter Windows wesentlich teurer wären.
EDIT: Hier mal meine Funktion zum Wechseln eines Context. Geht sicherlich noch irgendwie einfacher.

Code: Alles auswählen

__attribute__ ((noinline))
void swapContext(Context* origin, Context* target, void* userData = nullptr) {
    // Note: rbp is saved on the stack
    asm volatile ("movq %%rbx, %0 \n\t" : "=m"(origin->rbx):);
    asm volatile ("movq %%r12, %0 \n\t" : "=m"(origin->r12):);
    asm volatile ("movq %%r13, %0 \n\t" : "=m"(origin->r13):);
    asm volatile ("movq %%r14, %0 \n\t" : "=m"(origin->r14):);
    asm volatile ("movq %%r15, %0 \n\t" : "=m"(origin->r15):);
    asm volatile ("movq %0, %%rbx \n\t" :: "m"(target->rbx));
    asm volatile ("movq %0, %%r12 \n\t" :: "m"(target->r12));
    asm volatile ("movq %0, %%r13 \n\t" :: "m"(target->r13));
    asm volatile ("movq %0, %%r14 \n\t" :: "m"(target->r14));
    asm volatile ("movq %0, %%r15 \n\t" :: "m"(target->r15));
    asm volatile ("movq %%rsp, %0 \n\t" // store origin rsp
                  "movq %2, %%rdi \n\t" // pass userData to the fiber
                  "movq %1, %%rsp \n\t" // switch to target rsp
                  : "=m"(origin->rsp) : "m"(target->rsp), "r"(userData));
}

[Schrompf]

Ok, dann hatte ich das missverstanden - Fiber sind also mangels Wechsel in den Kernel Mode doch deutlich billiger als Threads. Also verschiebt sich meine Suche nach einer plattformunabhängigen Lib für Fibers.

[Krishty]

Nein. Ein Fiber-Wechsel ist immer ein Aufruf ins Betriebssystem, und DAS kümmert sich um Speichern und wiederherstellen des Kontexts, und NICHT der Compiler. Der Grund, warum Fibers weniger Overhead haben, ist, dass das Umschalten nicht den Scheduler des Betriebssystems (und damit nicht den Kernel Mode) passieren muss.

Unter Windows gibt es die Funktionen rund um ConvertThreadToFiber. Das sind natürlich aufrufe ins Betriebssystem und da kann ich auch nicht sagen was die für nen Overhead haben. Ich habe Fibers unter Mac OS X allerdings selber implementiert. Dazu braucht man ein paar Zeilen inline Assembly jedoch garantiert keinen Aufruf ins Betriebssystem. Wie gesagt, man muss nur eine Hand voll Register retten.

Ja; du hast absolut recht. Unter Windows ist es in der Tat aufwändiger, schon allein wegen der etlichen Calling Conventions. Davon habe ich mich dann wohl in die Irre führen lassen …

[Spiele Programmierer]

Das sollte unter Windows eigentlich doch schon genauso gehen, oder nicht? Ich sehe nicht in wie fern Calling Convention da rein spielen sollen. Man muss einfach alle Register sichern abhänig von der Calling Convention sichern, die man für diese eine Funktion verwendet. Und man muss natürlich richtiges Assembler verwenden, weil zumindest der MSVC kein Inline Assembly in 64 Bit unterstützt.

[kristof]

Nein, die Calling Convention muss beachtet werden. Durch das Austauschen des Stack Pointers ändert sich ja die Rücksprungadresse. Wir springen also in einen anderen Context, in dem davon ausgegangen worden sein könnte, dass andere Register gesichert worden sind.
Mir verknotet sich dabei aber auch regelmässig das Hirn :)

[dot]

Wie auch bei Threads muss der Einsprungpunkt einer Fiber unter Windows der __stdcall Calling Convention folgen... ;)

[Krishty]

Nur wenn man die WinAPI verwendet, oder? Die Diskussion ist ja gerade, dass man das nicht muss. Ich wundere mich nur, wie man dann die Stacks für die Fiber erzeugt. Von Hand die Stack Size aus dem PE-Header popeln, der zu der virtuellen Adresse gehört, in der der Einsprungspunkt liegt?

[kristof]

Ich wundere mich nur, wie man dann die Stacks für die Fiber erzeugt. Von Hand die Stack Size aus dem PE-Header popeln, der zu der virtuellen Adresse gehört, in der der Einsprungspunkt liegt?

Ich reserviere mit mmap ein paar Seiten Speicher. Dann schreibt man einfach die Rücksprungadresse und einen dummy rbp auf den Stack (dabei natürlich beachten, dass der stack von hohen Adressen zu kleinen Adressen "wächst"). Unter Mac OS X muss man auch noch beachten, dass jeder neue Stack Frame 16 Byte aligned sein muss. Das ist aber wieder einfach Teil der Calling Convention.
So sieht das bei mir aus:

Code: Alles auswählen

// Note: Stack grows downward and has to be 16 byte aligned upon function entry.
void** rsp = (void**)fiber->stackMemoryPointer + (fiber->stackSize / sizeof(void*));
*(--rsp) = (void*)0;          // alignment padding
*(--rsp) = (void*)entryPoint; // return address
assert(((std::uintptr_t)rsp & 0xF) == 0); // Ensure 16 byte alignment
*(--rsp) = (void*)0;          // dummy rbp
fiber->context.rsp = rsp;

[Schrompf]

Ich habe mich jetzt mal wieder mit dem Problem beschäftigt. So, wie's aussieht, kann ich mir eine simple Job Queue mit C++11 threads oder zumindest boost::thread zusammenbauen. Und die Fibers würde ich dann mit boost::context bauen - das sieht brauchbar aus, ist hinreichend minimal, und es ist angeblich für praktisch jeden Prozessor und jede Calling Convention implementiert.

Es gibt darauf aufbauend zwar auch ein boost::coroutine, aber das ist wieder das typische undurchsichtige boost-Template-Massaker, bei dem ich mir wünsche, dass sie es mit ihrer Abstraktion nicht so maßlos übertreiben würden. Das Ding saugt dann wieder 10MB MetaProgramming-Header an, von denen ich eigentlich nach und nach wegkommen wollte. Ich fürchte das Schlimmste, wenn ich jemals für eine Konsole porten will.