Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Mär 29, 2024 11:33

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 18 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: Asynchrones Design
BeitragVerfasst: Fr Jun 10, 2016 21:29 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hallo liebe Leute,

die letzten Tage hatte ich mal wieder Zeit an meiner Engine zu werkeln. Dabei habe ich insbesondere viel an der Kommunikation zwischen den Threads gearbeitet. Nun stelle ich mir aber die Frage ob man das nicht besser machen könnte. Daher wollte ich mal nachfragen wie ihr das so löst.

Aktuell benutze ich zur Kommunikation zwischen den Threads ein Template "async_callable". Dabei handelt es sich um einen Front+Back Vector der den Aufruf zwischenspeichert. Im Zielthread werden dann beider
Vektoren vertauscht und die einzelnen Elemente dann ausgeführt. In der Regel baue ich pro Funktionseinheit eine abstrakte Klasse die dann als eine Art Enum + Type gebraucht wird. Mein Fenster hat zum Beispiel:
Code:
  1.  
  2.  
  3.     bt::async_dispatcher<mouse_delegate> mouseEventDispatcher;
  4.     bt::async_dispatcher<keyboard_delegate> keyboardEventDispatcher;
  5.     bt::async_dispatcher<window_delegate> startupWindowEventDispatcher;
  6.     bt::async_delegate<window_change> windowChangeDelegate;
  7.  
  8.  


Code:
  1.  
  2. struct window_delegate : nocopy, noalloc
  3. {
  4.     virtual void window_did_pause(void) = 0;
  5.     virtual void window_did_resume(void) = 0;
  6.     virtual void window_did_appear(void) = 0;
  7.     virtual void window_close_requested(void) = 0;
  8.     virtual void window_size_changed(int width, int height) = 0;
  9.     virtual void window_change_handled(void) = 0;
  10. };
  11.  
  12. struct window_change : nocopy, noalloc
  13. {
  14.     virtual void set_title(const string & title) = 0;
  15.     virtual void set_position(int left,int top,int width,int height) = 0;
  16.     virtual void set_borderless(bool enabled) = 0;
  17.     virtual void set_render_interface(render_interface * renderer) = 0;
  18.     virtual void set_mouse_handler(bt::async_dispatcher<mouse_delegate> * mouseHandler) = 0;
  19.     virtual void set_keyboard_handler(bt::async_dispatcher<keyboard_delegate> * keyboardHandler) = 0;
  20. };
  21.  
  22. struct mouse_delegate : nocopy, noalloc
  23. {
  24.     virtual void mouse_input_move(int deltaX,int deltaY, int absoluteX,int absoluteY) = 0;
  25.     virtual void mouse_input_down(int absoluteX,int absoluteY,virtual_mouse_button button) = 0;
  26.     virtual void mouse_input_up(int absoluteX,int absoluteY,virtual_mouse_button button) = 0;
  27.     virtual void mouse_input_scroll(int delta) = 0;
  28. };
  29.  
  30. struct keyboard_delegate : nocopy, noalloc
  31. {
  32.     virtual void keyboard_input_down(virtual_keyboard_key key) = 0;
  33.     virtual void keyboard_input_textchar(char c) = 0;
  34.     virtual void keybaord_input_up(virtual_keyboard_key key) = 0;
  35. };
  36.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: So Jun 12, 2016 11:48 
Offline
DGL Member
Benutzeravatar

Registriert: Do Sep 02, 2004 19:42
Beiträge: 4158
Programmiersprache: FreePascal, C++
Ich versuche Kommunikation zwischen Threads vor allem im bereich GUI (das sieht mir arg nach GUI aus) zu vermeiden.

Der Extremfall den ich bisher hatte war dass die GUI-Logik und das Rendern in unterschiedlichen Threads läuft. Das macht QML so (siehe auch mein Post von neulich). Aber eigentlich habe ich das immer im gleichen Thread.

Dann hab ich in dem derzeitigen Projekt einige Threads die sich mit Simulation und asynchronem Nachbereiten von Daten beschäftigen. Hier nutze ich aber eher das in Qt vorwiegende Modell, dass man sich halt für Callbacks registriert und die dann in den Thread zugestellt werden. Da kümmert sich entweder Qt für mich oder bei dem low-level-kram habe ich mir eine kleine thread-safe Signal-Library gebaut. Da wird das Callback dann zwar nicht im richtigen Kontext ausgeführt, aber dafür nimmt man dann halt noch eine Condition Variable auf die der Zielthread wartet oder der gleichen. Hier nehme ich in der Regel einfach das passende Tool für den Job.

Den Synchronisationsoverhead versuche ich zu vermeiden indem ich selten Daten zwischen Threads hin- und herschiebe. Mit std::shared_mutex kann man auch gut rw-locks haben: damit muss ich nur sehr selten synchronisieren weil die meisten Benutzer von Daten einfach nur lesen wollen und sich damit nicht gegenseitig aussperren müssen. Beispiel: Ich habe mehrere Threads die auf den riesigen Terraindaten (1920×1920 Felder) arbeiten. Die werden immer aufgeweckt, wenn sich etwas am Terrain ändert und erhalten das Rect dazu beim aufwecken (intern werden mehrere Rects zu einem überdeckenden Rect zusammengefügt – das ist okay, weil Änderungen meist lokal sind). Dann werden z.B. normalen und das LOD neu berechnet. Das mache ich nicht direkt weil das durchaus seine Zeit dauern kann (vor allem das LOD). Wenn die Threads fertig sind holen sie sich kurz nen write-lock auf die entsprechende Datenstruktur und schreiben die vorbereiteten Daten rein, manchmal geht das über std::swap, manchmal muss ich einzelne Bereiche überschreiben.

Die Threads sind aber alle sehr spezialisiert, was es leicht macht, den Overhead durch Kopien von Daten oder ähnlichem zu verringern. Wenn man so ein allgemeines Modell hat stößt man schnell an Effizienzgrenzen. Für meine Fluidsimulation hatte ich erst ein Modell mit einem generischen Workerpool wo ich dann den Rechenauftrag (nichtmal mit Daten, nur mit x/y-Koordinate des zu berechnenden Blocks) reingeschoben hab. Allein das Kopieren sowie die Konstruktion/Dekonstruktion des Callables (std::function) hat so viel overhead verursacht dass ich am ende mit einem spezialisierten Workerpool besser (um einige Größenordnungen) dran war.

Langer Rede kurzer Sinn: Spezialisierung ist bei mir das, was den Overhead klein hält :-).

viele Grüße,
Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant networkmy photostream
„Writing code is like writing poetry“ - source unknown


„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Mo Jun 13, 2016 20:22 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Nu hat nicht wirklich was mit UI zu tun, sondern eher mit den Low-Level Kram wie bei dir. Das Window System ist halt am weitesten übersetzt und man sieht am besten wie Registrieren usw. funktioniert. Wenn du willst kannst du dir ja mal meine Helper Klassen anschauen, da sind der delegate und dispatcher definiert.

Ansonsten kann ich dir nur zustimmen je weiter dein "Thread" (oder Fiber, Coroutine oder sonstewas) ist umso eher kannst du halt höhere Interfaces bauen und dein Overhead wird wieder kleiner. Die Ideen für den Renderer sehen bei mir zum Beispiel in etwa gleich aus wie das Render-Interface von Quake 2. Nur halt noch mit Materials, Shader und Buffer-Objekte. Da dürfte also eigentlich egal sein wie gut die Kommunikation wird, denn der Window/OpenGL-Thread wird immer länger brauchen :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jun 28, 2016 21:36 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Das Konzept bringt zwar multithreading aber nicht gerade optimal.

Ich lese aktuell 2 Bücher zu dem Thema und dort waren auch solche Konzepte am Anfang mit drin aber es gibt wesentlich effizientere.
Generell sollte man ein Threadpool erzeugen, je logischen Prozessor ein Thread und diese auch fix diesen zuweisen.
Man sollte nie Logik threads zuweisen, also GUI==MainThread, Physic==Thread1, Sound == Thread2, denn das skaliert super mies auf weniger kernen und ist nahezu immer am starving/verhungern.
Da man bei GUI keine andere Wahl hat, hat man in der Regel einen extrem dünnen Mainthread, der den Input vom OS verarbeitet und ins System gibt aber sonnst schläft und damit dem Thread im Threadpool platz macht.

Code:
  1. App.Append(MyForm);
  2. while(App.IsRunning()){
  3.   App.Update();// System Messages verarbeiten
  4.   App.Process();// Form logik ausführen
  5. }

In der Form Klasse hab ich eine Idle Funktion, die dann von Application aufgerufen wird.
Dort packe ich meine Anwendungslogik rein, diese erzeugt viele Tasks und geht dabei schlafen.
Die Tasks werden vom Threadpool verarbeitet, dabei arbeite ich aktuell noch mit einem alten Sheduler, eine geteilte Lockfree Queue für alle und für jeden Thread noch eine eigene Serielle Queue.
Das Buch und auch einige moderne Engines empfehlen einen work stealing Sheduler.
Dieser verbringt weniger Zeit beim Enqueue und Dequeue und die Threads werden automatisch ausbalanciert.
Funktionieren tut es wie folgt.
Jeder Thread hat eine double sided queue, wo die producer seite keine synchronisierung und die consumer seite lockfree ist.
Hat ein Thread keine Tasks mehr, dann guckt er mit einem zufälligen offset in einen anderen Threadqueue ob noch was da ist und nimmt sich den letzten.
Also nur der Thread selber darf Tasks auf seiner Queue erstellen aber darf von jeder Queue ein Task nehmen.
Der Grund dafür ist, dass während man die Tasks in der lokalen Liste erzeugt, können die anderen Threads schon sich die Tasks raus ziehen und am ende Tut der Thread selber aus den eigenen Queue sich bedienen.
Google mal dazu single producer multiple consumer queue.

Bei Tasks empfehle ich dir einen Funktionspointer, einen Datenpointer und optional noch ein Destructor Funktionspointer.
Code:
  1. void (*TaskFunction)(void* Parameter);
  2. struct Task{
  3.   TaskFunction m_Function;
  4.   void* m_Parameter;
  5. };
  6.  
  7. // bla.cpp
  8. Task bla{&TerrainRendererComponent::Run, &currentEntity};
  9. Thread::CurrentInstance().Enqueue(bla);
  10.  
  11. // RendererComponent.hpp
  12. struct TerrainRendererComponent{
  13.   static void Run(void* Parameter){
  14.     ProceduralTerrain* entity = (ProceduralTerrain*)Parameter;
  15.     // ...
  16.   }
  17. };

Maximal 24byte auf dem Stack, keine allocation/deallocation für nen Task, konstante größe für nen Task erlaubt ein small object allocator.
Die Alternative wären Ableitungen mit ihren overhead.

Alles was zum Fenster gehört sollte im Fenster verarbeitet werden und dann von dort den State abfragen können.
Sobald du eine Condition, Mutex, Join irgendwo einbauen willst, denke lieber nochmal nach, man ist mitlerweile so weit, dass man sowas als schlechten Multithreading code betitelt.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Fr Jul 01, 2016 13:04 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
mhhh ja so ein Worker-System koennte man an einigen Stellen sicher gut gebrauchen. Ich denke aber eher das man hier auf ein generisches Konzept setzen sollte statt eine spezielle Implementierung. Je nachdem wie Geschickt man das baut kann man so auch alle speziellen Cases abdecken. Ich stelle mir das in etwa wie folgt vor:

Code:
  1.  
  2.  
  3. interface task_storage_policy<type, task_type = function<type>, allocator_type = allocator<task_type>>
  4. {
  5.     void add_work<expr>(expr work);
  6.     void execute_pending<argtypes...>(argtypes... args);
  7. }
  8.  
  9. class worklist<type, policy> : nocopy, noalloc, policy
  10. {
  11. }
  12.  
  13. using work_type = void();
  14. using work_item = bt::function<work_type>;
  15. using work_allocator_policy = bt::allocation_policy::freelist<64, bt::allocation_policy::default_alloc>;
  16. using work_allocator = bt::allocator<work_item, work_allocator_policy>;
  17. using work_storage_policy = bt::task_storage_policy::single_producer_single_consumer<work_type, work_item ,work_allocator>;
  18. bt::worklist<work_type,work_storage_policy> tasks;
  19.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Fr Jul 01, 2016 18:49 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Schau dir am besten die aktuelle ThreadPool klasse von .net und java an. Die benutzen nun auch ein work steal sheduler und die implementierung von unreal engine, sowie cryengine sind recht ähnlich.
Ein globale threadpool instanz mit einem thread pro logischen kern und teilweise den fix zugewiesen.
Man kann dann eine task instanz übergeben oder über funktionen und parameter ein generieren lassen.
Jeder hat die tasks anders definiert.
Früher hatte der .net threadpool auch noch completion threads aber sind raus geflogen und man soll nun async calls machen.

Workerthreads ist ein generisches Konzept.
So ziemlich jedes framework für multithreading verwendet threadpools, wenn mann sich mal mit threads auseinander gesetzt hat ist es auch logisch, die Erstellung , context switches zwischen kernen und abräumen ist sau teuer im vergleich zur arbeit die man in tasks damit erledigt.
Der Container, wo die tasks rein kommen ist oft unterschiedlich und das ist der kritische part.
Das verhalten, wie speicher geholt und freigegeben wird ist sehr wichtig, wenn man auch kleinere tasks verarbeiten will.
Intel tbb und cilk sowie fibre sind so gut optimiert, dass man sogar einzelne iterationen von ner schleife verteilen kann und es noch performance orteile bringt.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 12:50 
Offline
DGL Member
Benutzeravatar

Registriert: Do Sep 02, 2004 19:42
Beiträge: 4158
Programmiersprache: FreePascal, C++
Um nochmal darauf zurückzukommen. Die Idee klingt an sich gut, was mir noch nicht ganz klar ist, wie man mit Abhängigkeiten umgeht.

Ich habe hier zwei Situationen die evenutell unterschiedliche Lösungsansätze brauchen.

Situation 1: "Game loop"

Im Moment habe ich einen Thread für den Server, der den Game Loop macht. Der macht im Prinzip folgendes: alle ca. 16ms wird ein Game Frame ausgeführt. Ein Game Frame beginnt damit, mit allen Simulationen zu synchronisieren, also zu warten, bis der vorherige Frame zuende gerechnet ist (im idealfall muss hier nicht gewartet werden, weil die Simulationen weniger als 16ms brauchen sollten). Dann werden die Befehle, die sich in der Zwischenzeit über das Netzwerk angesammelt haben in die Welt eingespielt und ggfs. Fehlerantworten an die Clients verschickt. Daraufhin werden die Simulationen angestoßen um den Frame durchzurechnen. Rinse & Repeat.

Offenbar dürfen die Simulationen nicht anlaufen, bevor die Befehle eingespielt wurden und ebenso dürfen die Befehle nicht eingespielt werden bevor die Simulationen vom vorherigen Frame fertig sind. Wie würde man sowas lösen?

Einfachste Lösung: Den Server weiterhin als eigenen, nicht Worker-Pool-Thread halten und über Semaphore o.ä. mit den Simulationsthreads synchronisieren. Ist das der richtige Weg in dem Kontext? Der Serverthread würde den Großteil der Zeit schlafen, weil er nur darauf wartet, dass die 16ms rum sind um dann kurz zu synchronisieren und die Befehle einzuspielen. Letzteres kann allerdings je nach Befehlen durchaus ein paar hundert Mikrosekunden dauern. Die Befehle müssen allerdings in der Reihenfolge ausgeführt werden, in der sie ankommen.

Situation 2

Ich habe hier ein Partikelsystem was ich aus unterschiedlichen Gründen auf der CPU rechne. Das ist double-buffered, das heißt, ich kann den Simulationsschritt für das Partikelsystem problemlos parallelisieren, indem ich immer z.B. 1000 Partikel in einen Block zusammenfasse und die Blöcke auf Kerne verteile. Danach möchte ich das aber noch in eine Raumunterteilungsstruktur (hier: Spatial Hash) einsortieren. Das aus den Threads heraus zu machen erwarte ich als sehr ineffizient, weil die ja untereinander synchronisieren müssten, um die Struktur nicht kaputtzuschreiben. Daher würde ich das in einem separaten Task machen. Edit: Ebenso sollte das Hinzufügen neuer Partikel entweder vor oder nach den anderen Tasks passieren.

Wie stelle ich nun sicher, dass dieser Task erst ausgeführt wird, wenn alle anderen Partikelsimulationstasks durch sind?

Eine Lösung die mir einfällt, die aber eher unschön ist, ist ein atomic int der zählt, wieviele Blöcke schon durchgerechnet wurden. Jeder Update-Task inkrementiert und liest den Wert wenn er fertig ist. Der letzte Task stellt fest, dass er der letzte war und führt noch den zusätzlichen Einräumschritt durch. Ergibt das Sinn?

viele Grüße & danke für die Hinweise,
Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant networkmy photostream
„Writing code is like writing poetry“ - source unknown


„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 15:53 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hi, das ist in beiden Fällen das gleiche Problem. Du musst halt an irgendeiner Stelle prüfen ob deine höhere Aufgabe erledigt ist um in die nächste zu wechseln. Das meinte ich auch mit der generischen Lösung denn dieser Mechanismus unterscheidet sich je nach Anzahl der Threads.

Wenn du mehrere Worker/Abzweigungen hast wäre so ein atomic int schon einmal keine schlechte Idee. Wenn du nur 1 Thread/ keine Abzweigungen hast, dann bieten sich hierfür entsprechende Nachrichten an.

In jeden Fall sollte aber der Wechsel durch die jeweilige Task lokal angestoßen werden. Dadurch kannst du beide Sachen miteinander vermischen.

Alternativ kannst du dir natürlich auch Futures / Promises antun :-)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 16:15 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
1) Ich würde OS Timer für die 16ms Loop nehmen, wenn du wirklich nur alle 16ms aufrufen willst. Der Timer Spawnt alle 16ms ein Task im Pool, der halt ein Frame verarbeitet.
Wenn der Frame mehr als 16ms brauchen kann, dann sollte der Task entsprechend so gebaut werden, dass ein folgender Process nicht verarbeitet sondern den aktuellen einfach weiter in der loop laufen lässt.
Code:
  1. void MyTask(void* Data){
  2.   static AtomicInt32 ProcessFrameTasks = 0;
  3.   auto lastValue = ProcessFrameTasks.FetchAndAdd(1);
  4.   if (lastValue == 0)
  5.   {
  6.     while(ProcessFrameTasks != 0)
  7.     {
  8.        // viel Frame processing code.
  9.        ProcessFrameTasks.Decrement();
  10.     }
  11.   }
  12. }

Sollten 2 oder mehrere Tasks in der Queue liegen, weil die sich aufgestaut haben, dann werden alle ausser der erste einfach nur den ProcessFrameTasks erhöhen aber dann den ganzen rest überspringen. Der erste Task tut dann einfach wieder von vorne sein Code durchhämmern, statt den Task zu beenden, dass ist für die Caches viel besser.

Ich würde das Netzwerk über Socket select poolen und auch über ein Timer sehr frequent abfragen(z.B. 2-4ms). Dort würde ich das aber mit dem Counter und der Loop weg lassen, denn der kram ist niemals solange mit dem kopieren vom Netzwerkspeicher in den Arbeitspeicher beschäftigt. Dann kannst noch das Paket verarbeiten und je nach Aufwand es in Tasks zerlegen.
Deine Pakete sollten auch Server Timestamps benutzen. Also wann wurde das Paket nach Serverzeit versandt.
Damit kann die Extrapolation und auch eine Validierung viel fluffiger arbeiten.
Netzwerkpakete sollten so schnell wie möglich aus dem Netzwerkspeicher raus in den Arbeitspseicher, da sämtlicher Traffic in dem Speicher landet und der gnadenlos Pakete verwirfft, wenn neue rein müssen. Beim Client kein Problem, da kommt kaum traffic aber beim Server sollte das abholen sehr frequent passieren.

Die Simulation sollte über Kräfte agieren und über States mit dem Client synchronisieren. Also in der Simulation hast du Rotations- und Bewegungskräfte und States sind z.B. Impulse die auf die Kräfte addiert werden.
Bei einem Autorennen hat dein Auto einen Richtungsvektor, Up-Vektor, Rotationskraft auf Up-Vektor und Bewegungskraft auf dem Richtungsvektor.
Die ersten beiden kommen von der Physik Simulation mit einigen weiteren kräften, die von aussen einwirken und dann die beiden modifizieren.
Die anderen beiden sind dein Netzwerk Input, also ein Winkel(float), Gas(float) und ein Timestamp, wann die beiden Werte auf dem Client erfasst wurden.
Die Werte können z.B. -1 für Pfeiltaste unten und 1 für Pfeiltaste oben, -1 Pfeiltaste Links und 1 für Pfeiltaste Rechts sein oder bei einem Menschen Max(MausDelta.X*MouseModifier, MaximaleRotation)/MaximaleRotation für Winkel sein. Auf Serverseite wird dann anhand des Timestamp die jetzige Rotation und Gas extrapoliert und auf die Kräfte angewendet. Dann sendet man die resultierende Position und Richtung zurück und der Client kann abweichungen bei sich dann korrigieren(Rubberband).

2) In Spielen benutzt man Stages und die Transition versucht man so kurz wie möglich zu halten, da diese single threaded ist.
Man hat also ein Task, der das Processing anstuppst.
Code:
  1. void MyParticleProcessing(void* Data){
  2.   ParticleTask* pt=(ParticleTask*)(Data);
  3.   ParticleTask a,b;
  4.   if (pt.Count > 50){
  5.     pt->SplitInHalf(a,b);
  6.     pt->ToDo->Increment();
  7.     ThreadPool::GetInstance().Enqueue(MyParticleProcessing,a);
  8.     pt->ToDo->Increment();
  9.     ThreadPool::GetInstance().Enqueue(MyParticleProcessing,b);
  10.   } else {
  11.     // Apply forces
  12.     // Simulate
  13.     pt->ToDo->Decrement();
  14.   }
  15. }
  16.  
  17. void MyParticleCorrection(void* Data){
  18.   ParticleTask* pt=(ParticleTask*)(Data);
  19.   ParticleTask a,b;
  20.   if (pt.Count > 50){
  21.     pt->SplitInHalf(a,b);
  22.     pt->ToDo->Increment();
  23.     ThreadPool::GetInstance().Enqueue(MyParticleProcessing,a);
  24.     pt->ToDo->Increment();
  25.     ThreadPool::GetInstance().Enqueue(MyParticleProcessing,b);
  26.   } else {
  27.     // Alles positionen und Richtungen werden nicht verändert und damit können alle Threads auf alle Partikel lesen.
  28.     // Setze korrektur Kräfte.
  29.     pt->ToDo->Decrement();
  30.   }
  31. }
  32.  
  33. void ParticleSimulation(void* Data){
  34.   AtomicInt32 toDo = 1;
  35.   ParticleSimulation* sim = (ParticleSimulation*)(Data);
  36.   ParticleTask a;
  37.   a.Offset = 0;
  38.   a.Count = sim.Count;
  39.   a.Simulation = sim;
  40.   a.ToDo = &toDo;
  41.   ThreadPool::GetInstance().Enqueue(MyParticleProcessing,a);
  42.   while(toDo != 0)
  43.   {
  44.     Thread::Yield();
  45.   }
  46.   toDo.Increment();
  47.   ThreadPool::GetInstance().Enqueue(MyParticleCorrection,a);
  48.   while(toDo != 0)
  49.   {
  50.     Thread::Yield();
  51.   }
  52.   toDo.Increment();
  53.   ThreadPool::GetInstance().Enqueue(MyParticleProcessing,a);
  54. }

Erst Kräfte anwenden, dann simulieren, dann in einem readonly Schritt neue Kräfte berechnen, damit Fehler behoben werden können, wie zu weit in ein Objekt geschnitten.
Dann nochmal die simulation laufen lassen und man hat ein korrekten Frame geschafft.
Man legt bei modernen Multithreading Architekturen ein Threshold fest, z.B. 50 Partikel in dem obigen Fall, bis dahin wird in 2 Teile geteilt und der Task beendet und darunter werden die Partikel berechnet.
Das macht man, damit sehr schnell viele Tasks erzeugt werden, damit die anderen Threads ordentlich nachschub bekommen.
Aufsplitten anhand der Logischen Prozessor oder ähnliches hat sich als ineffizient erwiesen, so das Ergebnis von Intel TBB, OpenMP und AMD.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 16:58 
Offline
DGL Member
Benutzeravatar

Registriert: Do Sep 02, 2004 19:42
Beiträge: 4158
Programmiersprache: FreePascal, C++
Erstmal vielen Dank für eure Antworten.

@yunharla
Das Problem bei allem, worauf ich warten müsste (Messages, Futures/Promises), ist halt, dass das nicht in einem Workertask geschehen kann, ich also wiederum einen extra Thread bräuchte.

Am liebsten wäre mir hier eine Runtime die Koroutinen unterstützt (ala Python asyncio) für so Koordinatorthreads. Die müssen meist recht wenig am Stück mit CPU machen, das könnte man problemlos in einen echten Thread packen und den Rest kooperativ via Koroutine lösen.

Beim ersten Fall kommt noch das Problem dazu, dass ich dann ja auch noch auf einen Zeitpunkt warten muss. Nur weil die Simulation fertig ist, heißt das nicht, dass der nächste Frame losgehen kann. Ggfs. muss noch der rest der 16 ms abgewartet werden. Das kann wiederum nicht in einem Workerthread geschehen. Dafür bräuchte man einen vollständigen Scheduler mit Wartebedingungen wie Aufwachzeit oder dergleichen – und an der Stelle möchte ich das doch lieber dem Betriebssystem überlassen, weshalb ich da einen separaten Thread favorisieren würde.

@TAK2004
Bei N < 16 clients mach ich mir um die Netzwerkschnittstelle nicht soo große Sorgen. Die wird optimiert wenn’s wirklich mal ein Problem gibt, ist eh alles TCP :).

Bei deinem zweiten Beispiel, würde man da nicht eher eine Condition Variable nehmen anstatt in einer Busy Loop Thread::Yield aufzurufen? Und: Ist ParticleSimulation ein separater Thread oder ein Workerpool-Task? Wenn letzteres, wie geht man damit um dass der die meiste Zeit einfach nichts tut und einen Worker blockiert?

Das erste Beispiel hab ich noch nicht ganz durchschaut. Meinst du mit:
TAK2004 hat geschrieben:
Wenn der Frame mehr als 16ms brauchen kann, dann sollte der Task entsprechend so gebaut werden, dass ein folgender Process nicht verarbeitet sondern den aktuellen einfach weiter in der loop laufen lässt.
schlicht, dass ich dann beim 16ms Timer nicht einen neuen Task reinschiebe sondern einen Counter inkrementiere, der den existierenden Task weiterlaufen lässt?

viele Grüße,
Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant networkmy photostream
„Writing code is like writing poetry“ - source unknown


„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 17:15 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Lord Horazont hat geschrieben:
@TAK2004
Bei N < 16 clients mach ich mir um die Netzwerkschnittstelle nicht soo große Sorgen. Die wird optimiert wenn’s wirklich mal ein Problem gibt, ist eh alles TCP :).

Bei deinem zweiten Beispiel, würde man da nicht eher eine Condition Variable nehmen anstatt in einer Busy Loop Thread::Yield aufzurufen? Und: Ist ParticleSimulation ein separater Thread oder ein Workerpool-Task? Wenn letzteres, wie geht man damit um dass der die meiste Zeit einfach nichts tut und einen Worker blockiert?

Das erste Beispiel hab ich noch nicht ganz durchschaut. Meinst du mit:
TAK2004 hat geschrieben:
Wenn der Frame mehr als 16ms brauchen kann, dann sollte der Task entsprechend so gebaut werden, dass ein folgender Process nicht verarbeitet sondern den aktuellen einfach weiter in der loop laufen lässt.
schlicht, dass ich dann beim 16ms Timer nicht einen neuen Task reinschiebe sondern einen Counter inkrementiere, der den existierenden Task weiterlaufen lässt?

viele Grüße,
Horazont

Der Hauptcode war von der main Funktion gedacht, also würde Yield die mainloop anhalten und den Worker auf dem entsprechenden Kern arbeiten lassen. Ist die Zeitscheibe zuende kommt er zurück, guckt und geht eventuell wieder pennen.
In der Regel Konkurrieren Process Thread(main) und ein WorkerThread, das ist ständig ein anderer, ausser man legt den Process Thread auf ein Kern fest, dann leidet immer der gleiche Worker aber das ist nicht zu empfehlen.

.net hatte früher Complete Ports für blocking IO, welche nix anderes waren als Seperate Threads die im Blocking mode liefen und seperat zu den WorkerThreads existierten und konkurrierten.
Heute überlässt Microsoft es dem Programmierer, wie er seine sachen synchronisiert und verteilt und hat noch ASync IO implementiert.

Nicht ganz, der Task ist ja schon erzeugt und macht ein Inkrement aber er tut nix weiter und beendet, der schon existierende Task, der die Loop betreten hat ist der dann weiter arbeitet.
Der hat einen heißen Cache auf die benötigten Daten und daher läuft er im 2. Durchlauf schneller, wenn er nicht extrem verteilte Zugriffe macht.
Du hast damit auch weniger Sorgen, dass du die benutzte API Threadsafe machen müsstest und damit der Code schneller ist.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Di Jul 19, 2016 18:24 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Lord Horazont hat geschrieben:
@yunharla
Das Problem bei allem, worauf ich warten müsste (Messages, Futures/Promises), ist halt, dass das nicht in einem Workertask geschehen kann, ich also wiederum einen extra Thread bräuchte.

Am liebsten wäre mir hier eine Runtime die Koroutinen unterstützt (ala Python asyncio) für so Koordinatorthreads. Die müssen meist recht wenig am Stück mit CPU machen, das könnte man problemlos in einen echten Thread packen und den Rest kooperativ via Koroutine lösen.

Beim ersten Fall kommt noch das Problem dazu, dass ich dann ja auch noch auf einen Zeitpunkt warten muss. Nur weil die Simulation fertig ist, heißt das nicht, dass der nächste Frame losgehen kann. Ggfs. muss noch der rest der 16 ms abgewartet werden. Das kann wiederum nicht in einem Workerthread geschehen. Dafür bräuchte man einen vollständigen Scheduler mit Wartebedingungen wie Aufwachzeit oder dergleichen – und an der Stelle möchte ich das doch lieber dem Betriebssystem überlassen, weshalb ich da einen separaten Thread favorisieren würde.


Nu das könntest du zum Beispiel ganz leicht über Timer oder Events lösen um einen sehr dünnen Controller-Thread
zu bauen. Dieser müsste dann einfach nur ein Wait-Any auf solche Objekte machen. Allerdings brauchst du nur
ein entsprechendes Controller-Objekt und nicht unbedingt einen Thread. Du könntest also natürlich auch deine Tasks
taggen und mit einen Controller-Objekt verknüpfen. Dann könnte dein Pool hier je nach Art von Task ganz
ohne (oder mit geringen) Overhead im Anschluss den Controller anstoßen. Das wäre vielleicht sogar die beste
Lösung wenn Server und Client in der selben Anwendung laufen, denn dann könntest du dein Sleep so bauen das es nur
getriggert wird wenn beide nix zu tun hätten. Beim dedizierten Server wäre das aber ein bisschen zu
over-the-top glaube ich :)

Für den 1. Fall könnte sowas dann zum Beispiel wie folgt aussehen:
Code:
  1.  
  2.  
  3. Counted_Controller<'Tag,'PoolStorage> : PoolStorage //Achtung! ggf. in einen member-type ablegen
  4. {
  5.      static bind<'NewController> = Fallback_Controller<Counted_Controller, 'NewController>
  6.      tls_counter : int //Anzahl der Tasks im Thread
  7.      shared_counter : atomic int //Anzahl der Threads mit Tasks
  8.      timer : TimerHandle //ein Timer und eine Uhr sollten reichen :-)
  9.      clock : ClockHandle
  10.      void push_back(task<'Tag>); //Counter erhöhen
  11.      task<'Tag,bool> pop_front(void); //Counter verringen und den Tag für "Last" binden
  12. }
  13.  
  14.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Mi Jul 20, 2016 12:50 
Offline
DGL Member
Benutzeravatar

Registriert: Do Sep 02, 2004 19:42
Beiträge: 4158
Programmiersprache: FreePascal, C++
TAK2004 hat geschrieben:
Funktionieren tut es wie folgt.
Jeder Thread hat eine double sided queue, wo die producer seite keine synchronisierung und die consumer seite lockfree ist.
Hat ein Thread keine Tasks mehr, dann guckt er mit einem zufälligen offset in einen anderen Threadqueue ob noch was da ist und nimmt sich den letzten.
Also nur der Thread selber darf Tasks auf seiner Queue erstellen aber darf von jeder Queue ein Task nehmen.


Wie gibt man hier Tasks von "extern" drauf (z.B. ausm GUI-Thread)? Bzw. wie synchronisiert man das hinzufügen und das entfernen von Tasks vom Ende? Nimmt man da einfach ein Mutex und geht davon aus dass es nicht zu viel congestion gibt?

Edit: Und wie funktioniert das Consumer-Ende der Queue, auch in der Situation dass genau ein Task in der Queue ist und ein anderer Thread den Task gerade klauen will und der Thread dem die Queue gehört den gerade rausholen will.

(Langsam habe ich den Eindruck, dass du einfach mal die Bücher nennen solltest ;-))

viele Grüße,
Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant networkmy photostream
„Writing code is like writing poetry“ - source unknown


„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Mi Jul 20, 2016 14:34 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Nu du koenntest dir zum Beispiel mal die Queue von Michael und Scott dafuer anschauen. Die sollte eigentlich ausreichen.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Asynchrones Design
BeitragVerfasst: Mi Jul 20, 2016 17:34 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Structured-Parallel-Programming(Sehr gut, weil Intel TBB, Cilk++, OpenMP, OpenCL häufig gegeneinander verglichen werden und auch sehr tiefgehend)
Parallele Programmierung
Game Engine Architecture, Second Edition(eher praktische Anwendung und weniger Implementierung)

Erstmal zur Kommunikation zwischen Threads.
Es wird hier zwischen 4 Arten unterschieden
-single producer(SP) und single consumer(SC)
-SP und multiple consumer(MC)
-multiple producer(MP) und SC
-MP und MC
Jede variante wird anders implementiert und wird von oben nach unten immer langsamer(natürlich relative betrachtet) und komplexer.
Eine SPSC Queue ist das einfachste und MPMC das komplexeste aber in alten Designs häufiger eingesetzt.
Synchronisierung wurde früher über Mutex gemacht und man versucht eigentlich diese über Lockfree mechanismen zu ersetzen.
Performancetechnisch sieht es wie folgt aus.
(Langsam)Mutex>Atomic Operation>normale Operationen(schnell)
Atomic Operation sind teilweise auch normale Operationen, z.B. ein A=B kann atomic sein, wenn es 4bzw. 8Byte groß ist und Memory Aligned ist also 4 oder 8byte Alignment hat.
x86 ist 8Byte Alignment und damit möglichst alles mit einer Operation passiert haben die Compiler dann 8Byte Alignment als default für das Target.
Je nach CPU tut ein 2Byte Variable dann 8Byte laden und swizzeln in einem Schritt und auf anderen sind es dann halt 2 oder mehr und damit ist es nicht mehr Atomic.
Atomic Variable gibt es als Int32,Int64 und void* die entsprechend ein Byte Alignment von 4 oder 8 erzwingen und die CPU macht dann die Magie, da hat der Compiler nix weiter mit zu tun.
Dann gibt es bestimmte Operations die z.B. 2 Operationen enthalten und trotzdem in einen Schritt erledigt werden können und somit Thread safe sind.
Die meist genutzen sind compare and exchange(CAS) und fetch and add.
Mit diesem Baukasten bauen nun Programmierer auf verschiedensten weisen Lockfree oder Locking Container hauptsächlich Queue.

Im 1. Buch wird z.B. eine SPMC Queue empfohlen und das ist auch was die modernen Renderengines und Multithreaded Libs verwenden.
Dabei hat jeder Workerthread eine SPMC Queue und wenn die eigene Queue leer ist, fragen die andere Thread Queues, ob die ihnen ein Task abgeben.
In diesem Fall ist das Push eine normale Funktion, die weder Locking noch Atomic operations braucht, die arbeitet einfach auf dem Anfang.
Das Pop muss synchronisiert werden und arbeitet auf dem Ende.
Da kann man viel falsch machen und man sollte gucken dass man entweder sehr viel Zeit und einige Tests schreibt oder was existierendes nimmt.
Ich hab z.B. nun fest gestellt, dass meine MPMC Queue buggy ist und obwohl die Jahrelang funktioniert hat und als ich nun noch mehr Druck auf die Queue ausgeübt hab der Sync Bug erst aufgefallen ist.
Bei solchen Queues teilt sich die Implementierung in das Link List(struct mit nem next pointer member und den Daten) und Ringbuffer Lager auf.
Link Listen haben den Vorteil, dass die sehr dynamisch wachsen und schrumpfen aber halt ständig new und delete aufrufen und Ringbuffer ist fix von der größe aber halt cache und Speicherfreundlich.
Auf das Konzept, worauf ich gerade umstelle nutzt z.B. myItem = Tail.FetchAndAdd(1), also myItem ist dann der Index vom Task, den er verarbeiten darf, gucken ob es den wirklich gibt und wenn nicht wieder Tail.Decrement() machen und beenden. Der Author von dem ich das nachbaue hat allerdings ne blocking loop gebaut und lässt den Thread solange warten bis myItem valide ist.
Der Mainthread hat auch eine queue und der Poolmanager kennt dann zu den Workerthreads auch diese.
Am Anfang sind alle Queues leer und der Mainthread wirft einen Task in seine Liste, da er die nicht verarbeitet klauen die Workerthreads die Tasks noch während er weitere pusht.
Rekursives zerlegen von Arbeit in weitere Tasks füllt dann ganz schnell alle Queues mit arbeit, statt dem teuren stehlen von anderen.
Das sind Generische Systeme.

Es gibt auch Ansätze in Games mit MPSC, bei Naughty Dog z.B. tun die Worker in eine InQueue pushen und der MainThread ist dann der consumer und wechselt dann in die nächste Stage und Pusht in die SPSC InQueue von den Workern. Da darf aber nur der Mainthread arbeit in die Worker geben und ein Worker kann kein neuen Task sich selbst erstellen.
Das geht, weil es Anwendungspezifisch ist und für jeden Zeitpunkt fest steht welcher Thread da ist und und was er tun muss.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 18 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

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


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.232s | 17 Queries | GZIP : On ]