Fibers und Thread-Pools

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.

Fibers und Thread-Pools

Beitragvon Schrompf » 01.03.2016, 16:09

[Abgespalten aus dem Jammer-Thread]

PAGEFAULT_IN_NONPAGED_AREA (win32kfull.sys)

Der war neu für mich. Ist eigentlich kein wirklicher Jammergrund, weil der durch einen winzigen Fehler in meiner Meshgenerierung entstand, wodurch ich irgendwas >64k Fibers mit je 128kb Stack angelegt habe. Beim ersten Mal hab ich noch ganz banal nullptr vom letzten new zurückbekommen. Und weil der Task Manager aus irgendwelchen Gründen bloß 5GB Speicher angab, wurde ich neugierig. Es gab irgendwo diese Ressourcen-Ansicht, mit der man den kompletten Committed Heap sehen konnte, aber den hab ich so schnell nicht gefunden. Und beim erneuten Starten dann mein erster Bluescreen wegen Speichermangel.

Eigentlich freu ich mich gerade viel zu sehr über die Parallelisierung und das ganze Fiber-System, als dass ich hier jammern wollen würde. Aber ich wollte zumindest anekdotisch davon erzählen.
Zuletzt geändert von Schrompf am 01.03.2016, 23:38, insgesamt 2-mal geändert.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Jammer-Thread

Beitragvon dot » 01.03.2016, 16:37

Was genau machst du eigentlich mit Fibers? xD
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1601
Registriert: 06.03.2004, 19:10

Re: Jammer-Thread

Beitragvon Schrompf » 01.03.2016, 17:02

Alles :-) Ich wollte Dir auf die Schnelle die Präsentation von DICE zur Frostbite-Engine raussuchen, wo ich die Idee der expliziten Formulierung der Datenabhängigkeiten mittels Fibers her habe. Leider lässt mich mein GoogleFu gerade im Stich.

Aktuell parallelisiere ich damit als ersten Schritt die Meshgenerierung. Wenn die Kamera still steht, rendert alles mit 60+fps. Aber sobald die Kamera bewegt wird, ruckelt und hackt alles, weil da bis zu mehreren Sekunden Pause drin sind, bis die paar dutzend neuen Meshes berechnet wurden. Und es erscheint verlockend, erstmal mit den alten Meshes weiter zu rendern, bis die neuen Detailstufen da sind.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Jammer-Thread

Beitragvon dot » 01.03.2016, 19:29

Schrompf hat geschrieben:Alles :-) Ich wollte Dir auf die Schnelle die Präsentation von DICE zur Frostbite-Engine raussuchen, wo ich die Idee der expliziten Formulierung der Datenabhängigkeiten mittels Fibers her habe.

Das scheint mir aber doch ein wenig viel Overhead zu sein, wieso nicht einfach einen normalen Thread Pool (in Windows versteckt sich ein extrem cooler, eingebauter Thread Pool Mechanismus hinter I/O Completion Ports; Datenabhängigkeiten – zumindest der Natur wie man sie normalerweise hat – lassen sich sehr einfach modellieren, indem abhängige Tasks erst von den ihre Inputdaten produzierenden parent Tasks gespawned werden)!?

Edit: Ok, ich nehme an es gibt eine Fiber pro "Task" und das ganze basiert darauf, dass in jedem Frame die selben Tasks wieder laufen müssen und dann gibt es einen Thread Pool der sich die nächste Fiber, die ready ist, schnappt!? Interessante Idee...
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1601
Registriert: 06.03.2004, 19:10

Re: Jammer-Thread

Beitragvon kristof » 01.03.2016, 20:21

Ich helfe mal mit dem Link zum Talk aus ;)

http://www.gdcvault.com/play/1022186/Pa ... Dog-Engine

Ich hab das auch mal prototypisch implementiert. Auch das mit dem Pipelining was er später noch erwähnt geht dann sehr einfach umzusetzen. Leider hab ich das Ganze noch nie wirklich unter einer realistischen Last gesehen. Bin gespannt was Schrompf noch so berichtet :)
kristof
 
Beiträge: 88
Registriert: 19.01.2009, 14:05

Re: Jammer-Thread

Beitragvon Krishty » 01.03.2016, 20:47

Würde auch zum Windows Thread Pool greifen; aus dem banalen Grund, dass er sowieso da ist – üblicherweise füttern D3D oder der GPU-Treiber nämlich schon Aufgaben rein.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6136
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Fibers und Thread-Pools

Beitragvon Schrompf » 02.03.2016, 01:03

Hm. Gute Ideen, denke ich - ich habe von denen vorher schlicht nichts gehört. Aber ich wollte halt eine systemunabhängie Lösung. Und Boost.Context bietet eine solche, auch wenn man so Kleinigkeiten wie "Stack wächst in negative Richtung" wissen muss und bei der Übergabe des Stack-Pointers selbst beachten muss.

Mein aktuelles System sieht so aus:

Für 8 Hardware-Threads:
8 Threads für schnelle parallele Jobs, die auf jeden Fall für das aktuelle Frames gebraucht werden
4 Thread für längerlaufende Jobs, die auch mal über das aktuelle Frame hinaus laufen dürfen
1 Thread für IO-Stuff, der primär auf die Platte wartet
1 Queue für Jobs, die sowieso im Hauptthread laufen müssen

Jede dieser Thread-Gruppen hängt an jeweils einer spezialisierten Queue mit beigeordneter condition_variable, auf der die Threads warten, falls die Queue gerade leer ist. Und das Coole daran ist, das man halt Fibers mit eigenem Stackframe einrichten und zu beliebigen Punkten auch wieder verlassen kann. Es gibt Leute, die damit Spiellogik machen: eine permanent durchlaufende Work()-Funktion, die jedesmal verlassen und im nächsten Frame neu betreten wird. Ich dagegen benutze das, um den aktuellen Ausführungsstrang zu verlassen, wenn ich auf die Fertigstellung einer Reihe anderer Jobs oder auch nur auf die Verfügbarkeit eines Mutex warte. Mutex oder Jobs haben dann so ne Art "Ich warte auf Dich"-Liste und packen die Wartenden einfach zur Wiedervorlage in die passende Queue, von wo aus sich der nächste Worker sie dann weiter ausführt.

Damit kann man halt sehr schön die Datenabhängigkeiten explizit ausformulieren: tu das, das und diese Reihe hier, und ich warte so lange. Nur halt dass der Thread nicht wirklich schläft, sondern sich währenddessen was Anderes zu tun sucht.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Fibers und Thread-Pools

Beitragvon MasterQ32 » 02.03.2016, 11:29

Es gibt Leute, die damit Spiellogik machen: eine permanent durchlaufende Work()-Funktion, die jedesmal verlassen und im nächsten Frame neu betreten wird.

Gamestudio macht das so, die haben eine Funktion wait(n) wobei bei n > 0 eine gewisse Menge an Frames gewartet wird und bei n < 0 eine gewissen Anzahl an Sekunden. Bei n=0 passiert undefined behaviour, was zum fixen von bugs verwendet werden kann :P

Es ist meiner Meinung nach eine ziemlich coole Alternative zu dem klassischen GameLogic-Ansatz, aber wenn man damit aufwächst, ist es relativ schwer, davon loszulassen.

Wäre cool, wenn du deine Fiber-Lösung veröffentlichst, mich würde das durchaus interessieren, damit mal was zu bauen ;)

Grüße
Felix
Duct tape is like the force. It has a light side, a dark side, and it holds the world together.
Benutzeravatar
MasterQ32
Felix Queißner
Establishment
 
Beiträge: 1006
Registriert: 07.10.2012, 14:56

Re: Fibers und Thread-Pools

Beitragvon Schrompf » 02.03.2016, 11:55

Kann ich gerne machen, aber ich muss euch natürlich wieder vor Augenkrebs-Gefahr warnen, weil ich im Privaten immernoch auf Deutsch programmiere.

Der Nachteil der Work()-Funktion mit Yield() zwischendurch ist allerdings, dass ein solcher lokaler State unmöglich in Spielstände oder sowas geschrieben werden kann. Als ich das letzte Mal eine Skriptsprache selbst geschrieben habe, hatte ich auch so eine Wait()-Funktion eingebaut, mit der man aber nur Frames warten konnte. Da die Framerate aber auf nervösen 20fps festgenagelt war, war das ok. Und man konnte halt die aktuelle Mission nur neustarten, sonst nix. Obwohl der Teil albern war, weil die Skripte ja in einer Mini-VM liefen, deren Zustand ich stress- und verlustfrei serialisieren könnte.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Fibers und Thread-Pools

Beitragvon dot » 02.03.2016, 12:34

Schrompf hat geschrieben:Mein aktuelles System sieht so aus:

Für 8 Hardware-Threads:
8 Threads für schnelle parallele Jobs, die auf jeden Fall für das aktuelle Frames gebraucht werden
4 Thread für längerlaufende Jobs, die auch mal über das aktuelle Frame hinaus laufen dürfen
1 Thread für IO-Stuff, der primär auf die Platte wartet
1 Queue für Jobs, die sowieso im Hauptthread laufen müssen

Jede dieser Thread-Gruppen hängt an jeweils einer spezialisierten Queue mit beigeordneter condition_variable, auf der die Threads warten, falls die Queue gerade leer ist. Und das Coole daran ist, das man halt Fibers mit eigenem Stackframe einrichten und zu beliebigen Punkten auch wieder verlassen kann. Es gibt Leute, die damit Spiellogik machen: eine permanent durchlaufende Work()-Funktion, die jedesmal verlassen und im nächsten Frame neu betreten wird. Ich dagegen benutze das, um den aktuellen Ausführungsstrang zu verlassen, wenn ich auf die Fertigstellung einer Reihe anderer Jobs oder auch nur auf die Verfügbarkeit eines Mutex warte. Mutex oder Jobs haben dann so ne Art "Ich warte auf Dich"-Liste und packen die Wartenden einfach zur Wiedervorlage in die passende Queue, von wo aus sich der nächste Worker sie dann weiter ausführt.

Du hast also effektiv einen OS Scheduler im OS Scheduler gebaut... :P

Insbesondere da du trotz all dem ja immer noch eine Work Queue brauchst, frag ich mich doch sehr, ob das – beispielsweise in Anbetracht des zusätzlichen Fiber Context Switch Overhead – wirklich effizienter ist als ein einfacher Thread Pool. Ich würde mir unbedingt mal I/O Completion Ports anschaun, die sind mitunter eines der absolut coolsten Features des Windows Kernel...
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1601
Registriert: 06.03.2004, 19:10

Re: Fibers und Thread-Pools

Beitragvon Schrompf » 02.03.2016, 12:49

Müsste schon.

Ein Thread Switch sind ein paar tausend Takte, weswegen man da halt in gröberer Granularität arbeitet. Gute Sache für ne GUI-Anwendung mit rechenintensiven Aktionen, z.B. ein Malprogramm.

Ein Fiber Switch sind ein paar Dutzend Takte, weswegen man da in feinerer Granularität arbeitet. Prima Sache für Spiele, die in einem Frame ein paar hundert Jobs zu erledigen haben, die teilweise parallel arbeiten können, aber alle bis zum Frame-Ende fertig sein müssen.

Ob es effizienter ist, ist die andere Frage. Ich bin sicher, ich habe beim Bauen des Thread Pools und speziell der Jobverteilung irgendwelche Anfängerfehler gemacht. Das wird sich dann herausstellen.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Fibers und Thread-Pools

Beitragvon dot » 02.03.2016, 13:16

Schrompf hat geschrieben:Müsste schon.

Ein Thread Switch sind ein paar tausend Takte, weswegen man da halt in gröberer Granularität arbeitet. Gute Sache für ne GUI-Anwendung mit rechenintensiven Aktionen, z.B. ein Malprogramm.

Mit I/O Completion Ports hast du aber nur Threadswitches wenn der Thread blocked oder das Quota abläuft (also gleich wie mit den Threads in denen deine Fibers laufen), nicht zwischen Arbeitspaketen, deine Work Queue ist direkt im OS implementiert und du bekommst sogar noch gratis dazu, dass ein anderer Thread des Pool losgelassen wird sobald ein Thread auf I/O blocked, damit ja keine CPU Cycles unnötig verschwendet werden... ;)

Schrompf hat geschrieben:Ein Fiber Switch sind ein paar Dutzend Takte, weswegen man da in feinerer Granularität arbeitet. Prima Sache für Spiele, die in einem Frame ein paar hundert Jobs zu erledigen haben, die teilweise parallel arbeiten können, aber alle bis zum Frame-Ende fertig sein müssen.

"Ein paar Dutzend" ist wohl recht optimistisch und der Cache ist nach einem Fiber Switch genauso kalt, was vermutlich overall viel mehr ausmacht als ein paar tausend Takte... ;)

Ich hatte noch nie mit so einem System zu tun, aber rein nach der Beschreibung hier erscheint mir das alles immens kompliziert für etwas, das am Ende vermutlich nicht wirklich was bringt, vor allem wenn man bedenkt, dass du beim Coden der Fibers furchtbar aufpassen musst, dass du ja keine Library/API Funktionen oder sonstwas aufrufst, die blocken könnten, sondern alles async sein muss, damit du dann explizit switchen kannst und so, weil du sonst keinen Vorteil von den Fibers haben wirst...
Benutzeravatar
dot
Michael Kenzel
Establishment
 
Beiträge: 1601
Registriert: 06.03.2004, 19:10

Re: Fibers und Thread-Pools

Beitragvon Schrompf » 02.03.2016, 13:34

Ich stimme Dir zu, dass IO Completion Ports durchaus schmackhaft klingen. Geht halt nur nicht, weil nur Windows. Punkt. Der Rest der Diskussion ist dann eh müßig, aber dazu fehlt mir auch die Erfahrung mit dem Ding unter echter Last. Bisher ist es halt sehr angenehm, so seine Aufgaben zu formulieren. Blockierende OS-Funktionen spielen damit natürlich nicht mit, alles andere dagegen sehr gut. Und der Cache ist bei beiden Kontext-Wechseln arschkalt, das ist also kein Argument.

Dazu kommt in meinem Fall noch diese kleine Besonderheit des "Seriellen Jobs", die in einer speziellen Queue landen und portionsweise manuell im Hauptthread ausgelöst werden. Da packt man halt Input oder DX9-Calls rein, die halt zwingend aus dem Hauptthread kommen müssen. Der Renderer soll z.B. auf diese Art seine ganzen Arbeiten und Vorbereitungen parallel machen und dann am Ende, wenn er jeweils genug Daten für einen Renderpass zusammenhat, den Hauptthread-Job auslösen, der das Ganze an DirectX wichtelt. Ob sich die Mühe lohnt, wird sich wieder erst in den nächsten Wochen zeigen, aber es ist ein Detail, was OS-interne Lösungen rein prinzipiell so nicht bieten können.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Fibers und Thread-Pools

Beitragvon Krishty » 02.03.2016, 13:36

Klingt tatsächlich enorm komplex, aber wenn er plattformübergreifend gleiches Verhalten braucht, ist boost vielleicht wirklich der bessere Anfang.

Bzgl. Fibers: Windows’ Thread Pool nutzt intern ebenso Fibers, und jede Thread-Pool-Implementierung muss was Ähnliches tun um Rekursion und Abhängigkeiten ordentlich verwalten zu können.

Demnach wäre meine Strategie eher: Boost nach Code durchsuchen, der intern auf Windows’ Thread Pool zugreift. Gucken, ob das umgebende Interface tauglich für dich ist. Dann kannst du relativ sicher sein, dass das Verhalten auf anderen Plattformen ähnlich optimal ist; die Schnittstelle plattformübergreifend; und dass du selber nicht so viel Systemprogrammierung betreiben musst.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
 
Beiträge: 6136
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy

Re: Fibers und Thread-Pools

Beitragvon Schrompf » 02.03.2016, 13:42

Auch eine Herangehensweise. Die Boost-Doku dazu besagt, dass es alternativ auch einen Build gibt, der intern die Windows-Fiber-API benutzt. Weiß nicht, was genau sie damit meinen - evtl. meinen die auch nur die alte SwitchThreadToFiber()-Funktion. Bezweifle ich aber, das ergäbe in dem Kontext keinen Sinn.

Mein Problem ist halt: Boost.Context ist ein minimales kleines Ding, was ich sehr angenehm finde. Boost bietet (vom selben Author) auch eine höhere Abstraktion an, die sich dann Boost.Coroutine nennt. Aber das ist dann wieder so ein übler Template-Krieg, der üblicherweise der Grund dafür ist, dass keiner wirklich Boost mag.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3626
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Nächste

Zurück zu Algorithmen und Datenstrukturen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 5 Gäste