Dev Diary #4 (Teil 3 von 3) – September-Oktober 2018

Teil 3: Speicherfragmentierung

Wir haben den ersten Teil über „Nicht initialisierte Variablen“ am Montag, den 1. Oktober 2018 gepostet. Der zweite Teil über „Speicherlecks (Memory Leaks)“ wurde am 12. Oktober gepostet. Dies ist ist nun der dritte und letzte Teil: „Speicherfragmentierung“.

Es geht hier um relativ technische Themen, aber wir bemühen uns alles so zu umschreiben, dass auch Nicht-Programmierer folgen und einen Überblick erhalten können.
Für die Programmierer unter euch: Uns ist bewusst dass wir hier einiges extrem vereinfachen, also habt bitte Nachsicht mit uns. Die Gilde 3 ist in C++ geschrieben, also setzt bitte eure C++-gefärbten Sonnenbrillen zum Lesen auf.

Das Problem

Hierbei handelt es sich wieder um ein etwas komplexes Problem, weshalb ich wieder auf unsere Metapher mit der Bibliothek zurückgreifen werde.

Stellt euch vor, dass ein Bibliotheksbesucher (unser Programm) damit beginnt, Informationen zu verarbeiten, und daher allmählich einen Lesetisch nach dem anderen mit Büchern und ähnlichen Werken besetzt. Da unser Besucher sehr organisiert und methodisch vorgeht (wie jedes Programm), möchte er die Bücher so anordnen, dass sie nicht überlappen und auch möglichst keine Lücken freilassen. Jedes neue Buch, das er holt, wird sauber und nahtlos an die vorherigen Bücher anschließend auf den Tisch gelegt. Natürlich wird es einige kleinen Lücken geben – nicht alle Bücher sind genau gleich groß. Des weiteren wird er, um Verwirrung zu vermeiden, Bücher nicht bewegen, sobald sie auf einem Tisch liegen, auch wenn er alle benachbarten Bücher zurückgibt.
Sobald er mit einem Buch fertig ist, entfernt er es von seinem Lesetisch und stellt es ins Regal zurück. Wenn er ein neues Buch holt, legt er es in die erste Lücke auf seinen Tischen, die genug Platz für das Buch bietet, ohne die benachbarten Bücher zu überlappen.

Wie ihr euch vorstellen könnt, lassen sehr große Bücher auch entsprechend große Lücken, in die ein oder auch mehrere neu geholte Bücher leicht passen. Wenn jedoch ein kleines Buch zurückgegeben wird, dann bleibt auch nur eine kleine Lücke, in die unter Umständen kein anderes Buch mehr passt. Stattdessen wird ein neues Buch in den freien Platz am Ende des Tisches gelegt, oder gar auf einen neuen Tisch.

Dieses Muster wiederholt sich solange der Besucher arbeitet – unbenutzte Werke werden retourniert und lassen Lücken, in die neu geholte Bücher möglicherweise nicht passen, und daher auf neue Tischen abgelegt werden müssen. Wenn sich diese Vorgänge lang genug wiederholen, wird der Lesesaal der Bibliothek sehr seltsam aussehen:

Der Besucher wird sein Arbeitsmaterial über viele Tische verteilt haben. Diese Tische müssen nicht einmal sehr voll sein – alle Bücher auf ihnen sind säuberlich arrangiert, allerdings mit seltsam geformten Lücken dazwischen, in die kein Buch mehr passt. Obwohl die totale Fläche, die von allen Büchern belegt ist, nicht sehr groß ist, wird er eine hohe Anzahl an Tischen besetzen.

Die Auswirkungen

Das beschreibt mehr oder weniger gut das Problem der Speicherfragmentierung. Ein Programm fordert oft Speicher vom Betriebssystem an, und retourniert auch oft wieder Speicher. Sobald ein Speicherabschnitt belegt ist, kann er nicht mehr verschoben werden – wenn man ein Stückchen Speicher zwischen zwei anderen Stücken freigibt, so kann man die Lücke nicht schließen indem man die Abschnitte ‘zusammenschiebt’. Stattdessen bleibt ein kleiner freier Bereich der nicht wirklich genutzt werden kann, aber die effektive Größe des belegten Arbeitsspeichers erhöht.

In vergangenen Zeiten wäre das Endresultat gewesen, dass man früher oder später keinen Speicher mehr anfordern kann. Der gesamte Speicherverbrauch wäre nicht sehr groß gewesen, aber der freie Speicher wäre in lauter kleine Abschnitte zersägt und zwischen den belegten Speicherbereichen ‘eingeklemmt’.

Auf modernen Systemen kommt es dazu nicht mehr. 64 bit Betriebssysteme und virtueller Speicher bewirken, dass man nicht mehr wirklich zu wenig Speicher haben kann. Anstelle dessen wird es mit zunehmender Laufzeit immer aufwendiger, einen freien Speicherbereich zu finden. In Gilde 3 resultiert das in zunehmen schlechter Performance, je länger man spielt – bis hin zur Unspielbarkeit. Ein Neustart gibt allen Speicher frei und ermöglicht es wieder für geraume Zeit weiter zu spielen.

Die Lösung

Wir haben bereits eine größere Änderung umgesetzt, die die Situation wesentlich verbessert hat. Die Gilde 3 hatte eine eigene Speicherverwaltung, die leider sehr schlecht auf fragmentierten Speicher reagiert hat, wodurch die Leistung des Spiels sehr steil abfiel. Wir haben diese Speicherverwaltung entfernt, und verwenden stattdessen den nativ in Windows verfügbaren Low Fragmentation Heap, der diese Situation sehr gut bewältigt ( https://docs.microsoft.com/en-us/windows/desktop/memory/low-fragmentation-heap ). Diese Änderung wurde mit Patch 0.5.4 implementiert, und hat sehr gutes Feedback erhalten.

Das Hauptproblem ist jedoch nach wie vor, dass das Spiel sehr gerne Speicher allokiert und nicht wieder freigibt, wodurch die Speicherfragmentierung zunimmt – Speicher wird nicht nur durch benötigte Daten belegt, sondern auch durch Daten die keiner mehr braucht! Diese Situation wird sich mit der Zeit verbessern, da wir unbenutzten Code entfernen und existierende Funktionalität überarbeiten.

Falls euch das Thema interessiert, kann ich euch wiederum den Wikipedia Artikel über Speicherfragmentierung empfehlen: https://de.wikipedia.org/wiki/Fragmentierung_(Informationstechnik)
Außerdem gibt es ein interessantes Video über ein anderes Spiel, das mit diesem Problem kämpfen musste: https://www.youtube.com/watch?v=_zD33Hrbo4Y

Schlusswort

Wir hoffen, dass wir euch mit diesem Dev Diary einen Blick hinter die Kulissen gewähren konnten. Ihr könnt die Arbeit, die in die Behebung dieser Probleme fließt, nie auf offensichtliche Weise sehen. Stattdessen wird dadurch über Zeit die Stabilität und Performance erhöht, was zu einem generell verbesserten Spielerlebnis führt.

Daniel Rind
Programmierer für Die Gilde 3
Purple Lamp Studios