Diskussion zur Peformance und fehlenden Features (Build 6181)

Willkommen in der Transport Fever Community

Wir begrüßen euch in der Fan-Community zu den Spielen Transport Fever und Train Fever, den Wirtschaftssimulatoren von Urban Games. Die Community steht euch kostenlos zur Verfügung damit ihr euch über das Spiel austauschen und informieren könnt. Wir pflegen hier einen freundlichen und sachlichen Umgang untereinander und unser Team steht euch in allen Fragen gerne beiseite.

 

Die Registrierung und Nutzung ist selbstverständlich kostenlos.

 

Wir wünschen euch viel Spaß und hoffen auf rege Beteiligung.

Das Team der Transport-Fever Community


    Städte, die schlagartig auf die 3-fache Größe anwachsen hatte ich noch nie gehabt. Auf die doppelte Größe innerhalb von 50 Jahren: Ja das geht.
    Allerdings habe ich auch noch nie eine Stadt mit über 1000 Einwohner.
    Ich spiele allerdings auch dezentral: Keine Hauptstadt von der alle Strecken ausgehen, sondern ein Netz das mehr oder weniger gleichgroße Städte verbindet. Und Bahnhöfe haben bei mir in der Regel nur 3 Bahnsteiggleise, selten auch mal 5, teilweise aber noch mal mit mindestens 5 Gleisen ohne Bahnsteig (Durchgangs- und Nebengleise) wie das vor dem großen Kahlschlag von Mehdorn eigentlich die Regel war. Damals galt als Faustregel: Ein normaler Bahnhof hat ca doppelt soviel Güter- und Abstellgleise (ohne Bahnsteig) wie Gleise für den Personenverkehr (Gleise mit Bahnsteig).

    Hallo erstmal!


    Gestattet, dass ich mich kurz vorstelle: Ich lese hier nun seit einem Jahr mit und bin wirklich begeistert von dem Spiel. Als großer Fan Railroad Tycoon sowie Transport Tycoon Fan, ist Train Fever wie für mich geschaffen.


    Das Problem der Monatsruckler nimmt mir früher oder später immer den Spielspaß und kleine Karten bieten mir ehrlich gesagt zu wenig Möglichkeiten. Vom Spielertyp würde ich mich dann auch eher als "Großbauer" statt als Schönbauer" beschreiben, auch wenn ich irgendwann anfange alte Strecken zu verschönern, was ich dann aber aufgrund der ständigen Zwangspausen entnervt lasse.


    Im Forum wird dieses Thema immer wieder mal aufgegriffen und scheint die Lager zu spalten. Die einen sehen dies als Spielstopper und damit als Fehler anderen hingegen ist das egal und verteidigen das ansonsten großartige Spiel. So auch wieder vor einigen Beiträgen mit der Aufforderung statt zu meckern Vorschläge zur Verbesserung zu machen.


    Eines Vorweg: mein "Wissen" über die Train Fever internen Berechnungen basiert auf den Informationen im Forum: Am Monatsende wird das Städtewachstum berechnet. Neue und bereits bestehende Agenten kalkulieren dann auch neue Wege zu möglichen Zielorten. Dies ist in einem extra Thread ausgelagert. Ist dieser Thread mit den Berechnungen zum Monatsende nicht fertig, wartet das Spiel so lange.


    Meine Annahme:
    Das generieren neuer Agenten ist rechnerisch kein Problem. Ich vermute die verschiedenen Zielorte der Agenten (Arbeit, Freizeit) werden willkürlich festgelegt, werden dabei nur durch eine vorher berechnete Konstante auf innerhalb eines bestimmten Radius um den Wohnort beschränkt. Das ist eine sehr einfache Berechnung und hinreichend realistisch wenn man einen Algorithmus wählt, der eine Gaußsche Normalverteilung sicherstellt.


    Nach dem generieren des Agenten und möglicher Ziele bleibt nun die Wegfindung, welche auch für alle bereits bestehenden Agenten neu ausgeführt wird. Hier nehme ich an, dass Urban Games eine A* Implementierung mit zusätzlichen Kostenfaktoren für Umstiegszeiten verwendet. Sind die Kosten (also die Zeit) höher als ein Vorgabewert tritt der Agent die Reise nicht an. Ist er zu Fuß oder mit einem eigenem PKW schneller, nutzt er keine ÖPNV.


    Meine Optimierungsvorschläge


    1. Algorithmus Optimierung
    Den A* Algorithmus könnte man mit einer Binären Heap Optimieren. Die Implementierung ist sauber möglich, da man "nur" die Vergleichsoperation anpassen muss und die Navigationsinformationen statt in einer Liste in einem Heap gespeichert werden. Hier ist eine Verbesserung der Performance um Faktor 4 möglich.


    Hat man sich in die Theorie dahinter eingearbeitet (ca. 20 min) geht diese Umstellung schnell von der Hand.


    2. Mehrkernoptimierung
    Nachdem die neuen Agenten generiert wurden, können alle Agenten auf mehrere Listen verteilt werden. Dabei stehen neue Agenten immer auf Liste 1, alle weiteren auf Liste 1...n.
    Das Spiel prüft zu Start wie viele Kerne zur Verfügung stehen und erstellt je für eine Liste einen eigenen Thread, die Anzahl paralleler Threads sollte aber auf CPU Kerne-2 limitiert werden.


    Beispiel. Eine 8 Kern CPU (bzw. 4 kern mit HT) erlaubt 6 Berchnungsthreads. Das heißt für eine Karte mit 5900 Einwohnern und einem monatlichem Wachstum von 100 Einwohnern, dass alle neuen Einwohner in Liste 1 kommen, der Rest wird gleichmäßig verteilt. Somit wird die Navigation parallel auf 6 Kernen ausgeführt.*


    Das Aufteilen der Agenten in Listen sollte kein großes Problem sein, da man nach Abschluss der Berechnung die Listen wieder zusammenführen kann. Dies könnte der Berechnungsthread 1 übernehmen und dem restlichem Spiel die Daten in bekannter Form zurück übergeben.
    Nachteil: Mit jedem parallelem Thread erhöht sich der benötigte Arbeitsspeicher, hier wäre eine eine einstellbare Limitierung empfehlenswert.


    3. Aufteilen der Berechnungen auf verschiedene Monate
    Alle Agenten werden einer Liste zugeteilt. Stellt das Spiel fest, dass es zu Monatsrucklern (>1 Sek.) kommt, dann wird die die Anzahl an Listen erhöht. Neue Agenten sind immer auf Liste 1, werden dann aber gleichmäßig auf Liste 2..n verteilt. Die Agenten verbleiben dauerhaft auf den Listen. Treten Monatsruckler erneut auf, wird die Anzahl an Listen wiederum erhöht. Die neuen Agenten werden bei der nächsten Berechnung immer an die letzte Liste angehängt. Es wird bei der Monatsberechnung nur noch eine Liste abgearbeitet. Man kann die Anzahl an Liste auf 4 begrenzten um sicherzustellen das jeder Agent wenigstens alle 4 Monate den Weg neu berechnet. Dann werden die Listen einfach länger. Ist das Wachstum größer als der Puffer, wird die Liste ebenfalls verlängert.


    Beispiel ohne Mehrkernoptimierung, Karte mit 5900 Einwohnern, Wachstum +100. Das Spiel hat bei der letzten Monatsabrechnung mehr als 1 Sekunde auf der Ergebnis gewartet: Das Spiel führt nun eine Liste ein und begrenzt sie auf 5000 Plätze. 10% sind davon immer für neue Agenten reserviert, d.h. den existierenden Agenten stehen 4500 Plätze zur Verfügung. Ist eine Liste voll, wird eine weitere erstellt. In dem Beispiel haben wir Nun Liste 1: 1x 4500 + 100 und Liste 2: 1x 1400 + 100.



    Wie bei der Mehrkernoptimierung sollte das Aufteilen der Agenten auf Listen kein großes Problem darstellen, lediglich der Umstand, dass sich der Agent dauerhaft merken muss auf welcher Liste er steht macht eine weitere Anpassung nötig. Je nach verwendeter Datenstruktur, kann die Aufteilung auch über Indexranges erfolgen. Dies stellt die einfachste Optimierungsmöglichkeit dar. Zwar sinkt mit der Zeit die Genauigkeit der Simulation, aber macht sie nicht unrealistisch, denn Menschen sind träge, und nicht jeder überlegt sich jeden Monat wie er noch schneller zur Arbeit kommen kann :)


    Abschließende Gedanken
    Ich bin bei den Optimierungsüberlegung davon ausgegangen, das teile der Spielmechanik so funktionieren wie ich sie implementiert hätte, das muss natürlich nicht richtig sein, dementsprechend kann es natürlich sein, dass meine Vorschläge nicht funktionieren würden, bzw nicht so leicht zu implementieren wären. Ich kenne das Problem komplexer Programme und bin ein Anhänger des "never touch a running system" Paradigmas, dennoch hoffe ich meine Vorschläge finden halbwegs anklang.


    Die einfachste Implementierung wäre die Heap Optimierung, hängt aber ganz davon ab wie die Berechnung tatsächlich erfolgt. Ich gehe davon aus, dass man die Heap Optimierung aber wahrscheinlich ohnehin schon implementiert hat oder diese nicht möglich ist.
    Das Aufteilen der Berechnung (Vorschlag 3) sollte auch relativ leicht zu implementieren sein, bringt aber leichte nachteile bei der Genauigkeit. Vor Lösung 2 habe ich den meisten Respekt weil Multithreading Programmierung meine persönlich Hölle ist. Allerdings in Kombination mit Vorschlag 3 das Monatsrucklerproblem am besten bekämpft.


    Ich entschuldige mich an dieser Stelle für etwaige Ungenauigkeiten, aber der Beitrag ist lang genug geworden.

    Zitat von Falkenbahn

    Am Monatsende wird das Städtewachstum berechnet. Neue und bereits bestehende Agenten kalkulieren dann auch neue Wege zu möglichen Zielorten. Dies ist in einem extra Thread ausgelagert. Ist dieser Thread mit den Berechnungen zum Monatsende nicht fertig, wartet das Spiel so lange.


    So wie du es beschreibst, war es mal. Jetzt werden die Berechnungen anders gehandhabt. Genau Punkt Monatsende werden Berechnungen durchgeführt, die die Monatsendruckler auslösen. Das kann man sehr gut selbst testen, wenn man bis einen Tag vor Monatswechsel das Spiel für eine Weile pausiert. Das Standbild ist dann genauso lang, wie wenn der Monat normal durchgelaufen wäre. Vor dieser Änderung konnte man die ausstehenden Berechnungen mit dem Pausieren wieder 'einholen' und hatte kein Standbild.

    @Falkenbahn


    Dein Beitrag gefällt mir sehr gut, das man auch mal als Laie einen groben Einblick bekommt, wie solche Programme strukturell aufgebaut/umgesetzt sind.
    Hat Spaß gemacht zu lesen, inklusive der Links.

    Die sehr schöne Analyse von Falkenbahn zu dem Monatsruckler-Problem bewegt mich jetzt dazu, auch etwas zu diesem Thema zu schreiben. Schon des Öfteren habe ich in diesem Forum Analysen und Diskussionen zu diesem Problem gelesen - ganz ehrlich: so genau hat mich das bisher nicht interessiert, denn a) is halt so, b) die Entwickler werden dieses Problem am besten kennen und c) alles was in ihrer Macht (und Zeit-Ressourcen) liegt, daransetzen es zu lindern.


    Obwohl ich mich also wirklich nicht detaillierter damit beschäftigt habe, wundere ich mich jedoch einerseits, dass mein neuer Skylake i7 (einer der schnellsten Stock-Prozessoren Stand jetzt) hier trotz seines Turbo-Mode und Pipapo dennoch Probleme bei der Monats-Endberechnung hat.


    Andererseits frage ich mich schon, seit dem ich das erste Mal dieses Zuckeln gespürt habe, warum denn um alles in der Welt bis zu einem definierten Zeitpunkt im Spiel gewartet werden muss, um dann in großer Zeit-/Performance-Not unbedingt alle Berechnungen auf einmal machen zu müssen?


    90% der Berechnungen aka Agenten-Entscheidungen (ich folge mal dem obigen Wording) können doch einfach jederzeit gemacht werden und dann in den Main Thread aufsynchronisiert werden, wenn sie halt fertig sind.
    Natürlich kommt mit diesem Prinzip ordentlich Overhead hinzu. Doch ist Dieser in der Multicore-Ära fast vollständig wurschd - außer man betrachtet die Energieeffizienz :D
    Der einzig schmerzende Overhead ist die Synchronisierung in den Main Thread - doch je nachdem was Dieser überhaupt alles behandelt, ist das in vielen Situationen evtl. gar nicht relevant. Generell sollte der Main Thread frei von Spezialisierung sein, sondern lediglich anonymisierte Datenpakete so effizient wie möglich verteilen.


    Das ist jetzt - wie Falkenbahn ja auch schon erläuterte - natürlich eine generalisierte, abstrahierte und möglicherweise vollkommen unpassende Herangehensweise an Berechnungs-Abläufe die evtl. entweder so gar nicht in TF existieren, oder aber gar nicht Problemursache sind, sondern Diese ganz woanders liegen.... :D :D


    Dennoch würde mich Erleuchtung zur Eingangsfrage freuen!


    PS:
    Und ja, ich weiß was für eine Hölle Multithread-Programmierung sein kann, bzw. genau gesagt, ist die reine Multithread-Programmierung nicht das Problem, sondern die Synchronisierung. Ich entwickle Backend-Dienste die u. a. Echtzeit-Events verarbeiten und da hat man halt leider nicht die Wahl - man muss einfach multithreaded entwickeln, denn ein Event das weg ist weil du zu langsam warst, das ist weg und du kannst nur raten was wohl passiert ist.... (oder es ist nicht weg, sondern veraltet - genauso blöd) :D :D

    Hätten wir besseren RAM Durchsatz, alles wäre gut.
    Fakt ist das TF beim Sync der Threads bzw. der Daten (und wir reden hier von Gigabyte an Daten) einfach irgendwann nicht mehr fertig wird in einem Monat.
    TF macht diese Berechnungen nicht (mehr) im MainThread...


    Das hatte ich ja schon mal hier aufgeführt. (Es ist zwar besser geworden, das Grundprinzip in TF blieb aber bestehen)
    Was macht TF Intern und warum es ruckelt


    Bei TF ist das Problem eines Feedback-Loops. Am Ende eines Monats muss alles wieder zusammen kommen, da der nächste Monat auf die Vormonats Berechnung basiert.
    Der ganze C++ STL Container "Müll" macht die Sache nicht einfacher. Vielleicht würde ein -Os Kompilat für alte/große Spielstände wunder bewirken, wenn der Compiler mehr in den CPU Cacheline bekommen könnte.

    Wenn man den ersten Monat nicht korrekt abrechnet und z.B. deswegen 10 Sekunden warten muss, wären es bei deinem Vorschlag eben alle 2 Monate 20 Sekunden.


    Oder es bringt die gesamte Spielbalance aus dem Gleichgewicht. Denn natürlich könnte man den Monat einfach langsamer ablaufen lassen, damit noch Zeit übrig bleibt, um alles ohne Ruckeln abzurechnen (das ist dein Vorschlag effektiv, wenn du nur alle 2 Monate abrechnen willst), und dann den neuen Rechenzeitraum zu beginnen. Das Problem ist nur, dass damit beispielsweise die Geschwindigkeitstasten deaktiviert werden müssten.

    Bilder sagen mehr als tausend Worte... (Erweiterte Antwort --> Datei anhängen --> Bild auswählen --> *freuen*)

    Build 7554 ist gestern erschienen und es heißt in den Release notes es gäbe kürzeren Monatsendlag

    • Improved late-game performance (less/shorter end-of-month freezes)


    Hat das schon jemand gestestet?

    Bei meinem Game mit immerhin 300 Mods, mehreren 10-tausend Einwohnern und einer Menge Fahrzeuge Funktionierts viel besser. Der Monats"laaagg" dauert nun noch knapp eine halbe Sekunde, vorher 3 bis schlimmstenfalls sogar 8 Sekunden. Dafür ist die Performance in Grossstädten eher Schlechter geworden.


    Aber dies stört mich nicht, das Spiel läuft nun halt dauerhaft mit kleinen holpern.

    Es ist noch kein Meister vom Himmel gefallen.
    ----------------------------------------------------------
    Auch mal ein Blick wert

    Ja es ist viel besser geworden. Bei meiner grössten Karte hatte ich lags zwischen 6 - 9 Sekunden. Jetzt sind es 0.5 und darunter. Allerdings muss man dem Spiel zuvor ein paar monate vorlauf geben, denn das Städtewachstum wird offenbar jetzt anders berechnet. Daher kann es noch zu erhöhter bauaktivität in den ersten paar Monaten kommen.

    Zitat von Tom

    Wachsen die Städte bei dir auch noch?

    Ja, zum Teil sogar sprunghaft, gerade nach dem Laden des alten Spielstandes. Vorallem Erholungsgebiete schossen in einigen Dörfern an allen Ecken und Enden aus dem Boden. Daher hat es auch ca. 6 Monate gedauert bis der Monatsendefreez stabil unter 0.5 Sekunden blieb.

BlueBrixx