C# Laufzeitverbesserung durch Multithreading - Wie kann ich den Code verbessern?

[Kokujou]

Link zum Code: StateTree.cs

Wie ihr seht versuche ich einen Zustandsbaum aufzubauen. Und ich will ganz ehrlich sein ich hab keine Ahnung was ich da tue oder ob das halbwegs Sinn macht.

Hintergrund: Es geht um ein Kartenspiel. Es hat eine Maximalanzahl von 8 Zügen pro Spieler, danach ist das Spiel immer beendet. Klingt also möglich. Ich lasse die KI jetzt jeden Zug durchrechnen und versuche sie soweit optimieren, dass ich möglichst viele Züge zur Laufzeit berechnen kann.

BuildStateTree fängt mit einem Zustand an, baut dann Folgezustände auf und immer wenn einer fertig ist werden auf den Zustand nochmal x neue Gepackt.

Das Erstellen neuer Zustände wird parallel ausgeführt.
Dann wollte ich noch Asynchronität einbauen úm die Laufzeit nochmal zu verbessern. In jedem Zustand werden für jede Karte die er in der Hand hat neue Zustände generiert und das mache ich irgendwie... hoffentlich... asynchron.

Ich würde gerne auf mindestens 8 Züge kommen, damit ich zumindest für einen Spieler die Züge vollständig aufbauen kann so immer die Wahrscheinlichste und vielleicht sogar die 2. Wahrhscienlichste Wahl des Spielers einbauen kann... aber das wird owhl knapp.

 

[Enurian]

Task.WaitAny gibt dir den Index des beendeten Tasks zurück. Du musst nicht nochmal danach suchen.
Behalte im Hinterkopf, dass du das Multithreading nur machst, um deine CPU voll auszulasten. Dafür braucht es keine unendlich vielen Tasks/Threads. Sprich deine oberste Schicht Tasks sollte nicht noch einmal welche erstellen (in BuildChildNodes). Dort übrigens ein kleiner Hinweis: Wenn du eine feste Liste an abzuarbeitenden Objekten hast und du diese parallelisieren möchtest, benutze einfach Parallel.Foreach. Würde ich in diesem Fall aber wie gesagt ganz weglassen, da das bereits in jeweils eigenen Tasks läuft.

Dementsprechend sollte alles darunter synchron sein, um die Aufgabe möglichst zügig abzuarbeiten. Das Erstellen von mehr Tasks bedeutet nur mehr Overhead ohne Nutzen.

Ansonsten musst du halt analysieren, warum das so lange dauert und dann optimieren. Da gibt es ja im Prinzip nur zwei Möglichkeiten: Du hast irgendwo extrem viele Aufrufe / Verzweigungen oder ein Stück in deinem Code braucht verhältnismäßig lang zur Ausführung.
Da muss man sich aber die Logik anschauen (dafür bitte mal ordentlich kommentieren) oder es zur Laufzeit analysieren.

 

[Kokujou]

Ich hab bei WaitAny und Multithreading etwas angst dass so Tasks übersprungen werden. Kann das passieren?
Wenn z.B. mehrere Fertig sind gibt Waitany einen aus und wenn dann schon 2 fertig sind oder während der bearbeitung des ersten noch einer fertig wird wird der ja nicht abgefangen oder?

Oder terminiert WaitAny immer wenn in der Liste ein fertiger Prozess ist?

Ergänzung (19. Januar 2019)

Und noch eine Frage...
Asynchronität mit Multithreading bringt keinen Geschwindigkeitsvorteil?
Ich hatte gehofft das gibt dann nochmal irgendwie nen Boost...
Das blöde ist dass ich nicht so gut debuggen kann weil ich sehr unterschiedliche Zeiten kriege. Es ist ein Kartenspiel. Zufällig gemischt bedeutet Pro zug ne verschiedene Anzahl von entscheidungsmöglichkeiten. und demnach auch immer mehr dauer...

 

[NeoExacun]

Es bringt schon einen Geschwindigkeitsvorteil. Aber nicht, wenn du ZU viele Threads erzeugst. Jeder Thread erzeugt auch Overhead. Hast du zuviele Threads, erzeugst du mehr Overhead als du durch Multithreading wieder reinholst.

Wenn du trotz Zufall debuggen willst, musst du deinen Zufallszahlengenerator mit einem fixen Seed initialisieren.

 

[Kokujou]

Heißt das ich soll erst warten bis sie fertig sind? Wie würdest du denn das Problem im code angehen wir reden hier über MINDESTENS 40.000 Züge die am Ende entstehen müssen.
MINDESTENS! wahrscheinlich eher 160.000

 

[NeoExacun]

Das heißt du sollst dein Problem auf 8 Threads (oder wieviele logische Prozessorkerne du eben hast) verteilen und nicht mehr.

 

[Kokujou]

Also warten... wie sonst. Schön nacheinander abarbeiten.

Ich meine je kleiner du deine Aufgaben zerlegen kannst desto besser isses doch eigentlich... was meinst du eigentlich mit Overhead? Was passiert denn wenn ich 160.000 threads habe. wird das dadurch dann langsamer oder entsteht einfach nur datenmüll?

Ergänzung (19. Januar 2019)

Ich meine was würdest du mit meinem code denn anfangen. oder zumindest mit meinem Problem. Der Code ist wohl schrottreif.

 

[NeoExacun]

Wenn du 160.000 winzige Threads hast bedeutet das, dass das OS die ganze Zeit einen neuen Thread auf einen CPU-Kern legen muss. Jeder dieser Wechsel kostet Zeit (und zwar nicht wenig). Daher sollte man nicht allzuviele Thread erzeugen. Sonst wartest du länger als mit einer passenden Anzahl.

Ich habe deinen Code nur überflogen. Fremdcode ist mir gerade zu anstrengend. Aber ich gehe davon aus, dass du für jeden Zug einen neuen Thread erzeugst. Mein Vorschlag: Erzeuge für jeden ERSTEN Zug einen eigenen Thread und mache alle Folgezüge im selben.

 

[Kokujou]

Ich habs befürchtet... Tiefenkonstruktion statt Breitenkonstruktion wennich mal so spreche^^

passenderweise gibt es maximal 8 Züge pro Spieler... 8 Kerne... Joa^^ gut ich hab 12 aber

Tja das Asynchrone hab ich jetz erstmal rausgenomen. ich hatte gehofft durch die Kombo erziele ich nochn extra boost... dass ich die Kerne quasi optimal einsetze...

Aber wennich jetzt tatsächlich nur 8 parallele Threads hätte würde da die asynchronität weiterhelfen? das sind ja nun komplexere prozesse und alle Folgezustände können ja zuindest "quasiparallel" geregelt werden.

 

[NeoExacun]

Was auch immer du unter asynchron verstehst.

 

[Enurian]

Man erzeugt am besten (sofern nicht explizit notwendig) gar keine Threads, sondern lässt das den Threadpool machen. Der ist nämlich recht intelligent in der Threadverwaltung und verhindert so etwas wie 100.000 gleichzeitig laufende Threads.
Da du Tasks erzeugst, tust du das bereits - passt.

Async/await bringt erstmal überhaupt keine Performance. Am schnellsten geht es ganz einfach, wenn so wenig wie möglich gemacht werden muss und die Hardware ausgelastet wird. Async/await wurde gebaut, um es einfach zu machen auf langsame Dinge (z.B. IO) zu reagieren, ohne dadurch den aktuellen Thread zu blockieren.
Wenn ich eine Anfrage in das Internet laufen habe, hat der Thread, der die Anfrage erstellt, praktisch nichts zu tun und wartet nur bis er endlich eine Antwort bekommt. Async macht es nun einfach, währenddessen andere Dinge auf dem selben Thread auszuführen. Daher ist das für UI- oder "Main"-Threads Gold wert.
Es lässt sich aber auch dafür nutzen, anstatt von IO eine CPU-gebundene Aufgabe genauso zu behandeln. Diese muss dann natürlich auf einem anderen Thread (am besten per Task) laufen, sonst hat man ja nichts gewonnen und der eigene Thread wäre genau wie ohne async/await blockiert.

Um auf deine Performance zurückzukommen: Wie ich oben schon schrieb, musst du nur dafür sorgen, dass die CPU ausgelastet wird. Das machst du, indem du deine zu erledigende Arbeit in Teilprobleme zerlegst und diese als Tasks auf dem Threadpool ausführen lässt.
Das hast du ja schon drin.
Bist du dir denn sicher, dass überhaupt das richtige Ergebnis erzeugt wirst? Nicht dass du irgendwelche Schleifen drin hast.
Ansonsten geht es dann ans Optimieren. Ich sehe gerade, dass in der Visual Studio Community Version der Performance Profiler gar nicht enthalten ist. Das ist natürlich schade, aber mit der Stopwatch-Klasse und Log-Dateien kannst du das auch per Hand hinbekommen.

 

[Kokujou]

Na das ganze Async await Zeug^^
Ich kapier das eh nicht... warum überhaupt await? aWAIT heißt doch warten und das wollen wir doch gerade nicht XD

Ach das heißt das ist alles schon perfekt? Oh perfekt... Aber ein kleines Detail stört mich: Ja ich komme auf 100% aber nicht dauernd! manchmal sackt er runter auf 40, 30, 20% kann ich irgendwas machen damit er konstant auf 100% runterrattert das klingt so als wäre da irgendein störenfried am werk

Ah verstehe also quasi wie Unitys Coroutinen... die sind sogar noch langsamer das erklärt den Performance-Boost als ich es abgeschafft habe

Ja ich fürchte auch... ich optimiere schon so viel aber ich wollte diese Frage halt primär stellen um zu sehen ob ich es überhaupt richtig mache. Wie du bereits sagtest mit den ThreadPools und dergleichen... Allein mit der Umsetzung des Multithreading kann man ja schon viel raushauen.

Ich bin schon dankbar dass ich jetzt doch keine Tiefenkonstruktion machen kann sondern bei dem Breitenverfahren bleiben kann ^_^ (die Worte lehne ich an Tiefen- und Breitensuche aus dem Unterricht an also Breite wo man quasi dann immer von links nach rechts aufbaut und tiefensuche von unten nach oben, wenn das Bildlich genug ist )

 

[Enurian]

Tasks erstellen und abarbeiten erzeugt immer noch Overhead, "perfekt" muss das also nicht sein (die "untere Schicht" bringt z.B. wie gesagt höchstwahrscheinlich nichts mehr sondern macht es nur langsamer).

"Await" bräuchtest du, damit dein Main Thread nicht einfriert. Lies dazu einfach mal ein paar Artikel, das muss man hier ja nicht alles wiederkäuen. Nur so viel: dort, wo du "await" schreibst, hält die Ausführung der Methode an und gibt die Kontrolle an den Aufrufer zurück. Erst, wenn der Task, auf den gewartet wird, abgeschlossen ist, springt der Thread zurück in die Methode und macht den Rest.

Du musst nun ermitteln, was bei der Ausführung so lange dauert. Dann analysieren warum das so ist und wie man es verbessern kann.

 

[new Account()]

Na das ganze Async await Zeug^^
Ich kapier das eh nicht... warum überhaupt await? aWAIT heißt doch warten und das wollen wir doch gerade nicht XD

YouTube

An dieser Stelle steht ein externer Inhalt von YouTube, der den Forumbeitrag ergänzt. Er kann mit einem Klick geladen und auch wieder ausgeblendet werden.

YouTube-Embeds laden

Ich bin damit einverstanden, dass YouTube-Embeds geladen werden. Dabei können personen­bezogene Daten an YouTube übermittelt werden. Mehr dazu in der Datenschutzerklärung.

YouTube-Embeds laden

Datenschutzerklärung

 

[Kokujou]

Also son bisl wie bei Coroutinen nur dass man da nicht warten kann bis sie fertig sind. Glaub ich zumindest.

Aber gut dann ist das sowieso sinnlos in meinem Beispiel. Gut das trotzdem mal zu wissen. Aber gut wenn das soweit geklärt ist muss ich mich jetzt wohl oder übel an die Feinarbeit machen...

Kriegt man Performance-Boosts wenn man die Komplexität der Klassen einschränkt oder würde das nur den Speicherverbrauch optimieren? Ich überlege die Klassen einfach durch Indizes zu abstrahieren, weiß aber nicht ob sich der aufwand lohnt, denn so komplex sind die Klassen nicht und da sie größtenteils nur lesbar sind arbeitet er verutlich eh nur mit referenzen