Virtual File System (VFS)

[Sergius]

Hallo,

hat vielleicht schon einer die Erfahrung mit Programmierung von eigenem Virtual File System (VFS) für ein Spiel gesammelt ?

Hier einige Gedanken von mir:

Was bei einem VFS im Spiel wichtig ist, es soll ein Haufen von ausgewählten Dateien (einige hunderte von relativ kleinen Dateien: Modele, Texturen, Effektfiles, ...) schnell von der Festplatte lesen können. Da aber ein VFS schon in Gigabyte Bereich sein kann, ist es nicht sinnvoll kompletes VFS in RAM zu lesen und dann von da aus mit gezielten Zeigersprungen bestimmte Dateien zu lesen. Anderseits ist es auch langsam viele ausgewählte Festplattenzugriffe zu machen, wenn man ausgewählte Dateien lesen will, insbesondere wenn so ein großer VFS auf der Festplatte mit Sicherheit fragmentiert sein wird.

Die erste Frage die sich also stellt:
Was ist für ein VFS für ein Spiel besser. Komplettes VFS zuerst in RAM zu mappen oder die Dateien einzeln von dem VFS von der Festplatte zu lesen.

Die zweite Frage ist:
Lohnt es sich ein Komprimierungsalgorithmus zu verwenden ?

Es gibt zwar die Möglichkeit sich selber einen Chunk-Format auszudenken und zu implementieren, aber es gibt auch schon viele freie Komprimierungs-Algorithmen, z.B. zlib, rar, zip, lzma, ... (mit und ohne Komprimierung).
Zum Beispiel der lzma hat sehr gute Kompressionsratte und laut Spec kann auf einem 2 GHz Rechner 20-30 MB/s entpacken, das heisst wenn man Datei lesen und Entpacken parallel in Threads macht, kann man die Lesezeit von der Festplatte sich sparen und vorallem die Größe, also nochmal Zeit. Deswegen wird lzma auch für ein Realtime VFS empfohlen.

Habt ihr andere Erfahrungen gesammelt oder hat jemand vieleicht einige neue Ideen ?

Gruß

[odenter]

Erfahrungen damit habe ich keine, so spontan würde ich aber sagen ins RAM einlesen. Denn so ein VFS ist ja um Prinzip nur eine Sammlung von Strukturen ala

Code: Alles auswählen

struct tFile {
char name[255]
__int32 type;
__int64 size;
};
struct tHeader {
int anzahlDateien;
};

Und das ganze ist ja in einer großen Datei verpackt, also diese große Datei einlesen und dann auseinander nehmen. Oder immer jeweils eine Datei rausholen bzw. die Dateien die man braucht. Man kann die Struktur ja so aufbauen das z.B. erst alle Grafiken kommen, dann alle Modelle etc. so müsste man recht fix das einlesen können was man braucht.

[Aramis]

Bei mir sieht es so aus, dass ich im Prinzip das ganze (NTFS-)Dateisystem durch eigene Interfaces virtualisiert habe (d.h. Dateien und Verzeichnisse, auch Softlinks u.ä.). Der VFS-Baum wird dynamisch aufgebaut, d.h. ich lade nicht am Anfang das ganze Dateisystem in den Arbeitsspeicher, aber sobald das Programm versucht auf z.B. <root>/iwas/nochwas/sonstwo/datei.txt zuzugreifen, wird der entsprechende Teilbaum geladen und gecached - spätere Dateisuchen und auch Zugriffe innerhalb dieses Teilbaums kann ich dann mit deutlich weniger OS-Aufrufen abwickeln. Gleichzeitig nutze ich eigene Pfadvariablen, die stets auch mehrere Werte beeinhalten können. So werden - für das eigentliche Programm völlig transparent - auf der Suche nach Shadern, Skripten, etc. mehrere Verzeichnisse implizit zusammengeführt.

Archivierung und Kompression läuft über ein eigenes Archivformat, welches einfach an eine bestimmte Dateierweiterung gekoppelt ist. Greift das Programm auf <root>/iwas/sonstwo/test.txt zu, und es existiert eine Datei namens <root>/iwas/sonstwo.<archiverweiterung>, so wird selbiges Archiv geladen und in den Dateisystembaum eingefügt, dann wird die Suche nach der Datei darin fortgeführt. Momentan ist der Archivinhalt noch völlig unkomprimiert, ich plane aber bald auf LZMA umzustellen (genau wie Du aus der Hoffnung heraus damit nicht nennenswert langsamer zu werden). Das alles war eine ganze Menge Arbeit (~2 Wochen), aber es hat sich definitiv gelohnt.

[Krishty]

Erstens ist LZMA vielleicht overkill. Die NTFS-eigene Dateikompression erreicht zwar nicht ansatzweise die Kompression von LZMA, dafür ist sie aber vollkommen transparent und ins Betriebssystem integriert – man spart um die 30% ohne irgendwas am Programm ändern zu müssen und das ganze wird dann auch noch von Windows gemanaged (Multithreading etc). Ist doch auch was, zumal Festplatten heute doch eh in den hunderten GB zur Verfügung stehen und wir um die 10 GiB von jedem neuen Spiel gewohnt sind.

Dann zum Mapping: Unter 64-Bit-Systemen kein Problem, da hast du afaik 16 TiB Adressraum und kannst mal schnell jede Datei auf der Festplatte mappen. Unter 32 Bits jedoch problematisch, da dir nur 3 GiB Adressraum zur Verfügung stehen.

Die Frage, die du dir stellen musst, ist, wann du überhaupt eine 1:1-Map der Datei brauchst. Für Ressourcen, deren Größe sich verändert, ist Mapping oft unbrauchbar und für Ressourcen, die sich oft (oder gar in jedem Frame) verändern, ebenfalls. Unter’m Strich kannst du File-Mapping nur für solche Daten optimal benutzen, die im RAM genauso aussehen wie auf der Festplatte (bzw. serialisiert sind) – umkomprimierte Texturen usw. Die würde ich dann on-Demand mappen und wieder freigeben.

Gruß, Ky

[Aramis]

Erstens ist LZMA vielleicht overkill .. Ist doch auch was, zumal Festplatten heute doch eh in den hunderten GB zur Verfügung stehen und wir um die 10 GiB von jedem neuen Spiel gewohnt sind.

… zu meiner Verteidigung, ich habe mal an einem PNG-Optimizer gefeilt. Seitdem sehe ich überall ungenutztes Kompressionspotenzial und das ist iwie zwanghaft.

Irgendwie erscheint mir das widersprüchlich :-)

PS: Filemapping für große Archive lohnt sich imho _nicht_. Es ist gerade auf 32 Bit Systemen deutlich mehr Arbeit, weil man ständig auf seinen Adressraum aufpassen muss .. gleichzeitig spricht bei Archiven nur wenig dagegen einfach das File zu öffnen, die Verzeichnistabelle einzulesen und dann, wenn ein File angefordert wird, einfach an die entsprechende Stelle zu seeken. Filemapping lohnt sich aber evtl. für Datencaches, die eine konstante Größe haben und aufbereitete Daten für den aktuellen Weltabschnitt zwischenspeichern. Außerdem braucht Filemapping plattformspezifischen Code - also ein zusätzlicher Pflegeaufwand.

[Krishty]

Ich bin eben ein Mensch der Widersprüche :D Threads querverweisen ist fies.

Naja, das sind komplett unterschiedliche Situationen – Web/Archivierung vs. Echtzeitsystem. Ich versuche es mal iwie auszudrücken:

Wenn ich mal wieder in einer Trial'n'Error-/Debugging-Phase bin, kommt es – wie bei Sergius – vor allem darauf an, dass alles schnell startet. Dann geht, auch wenn es konterintuitiv ist, wirklich nichts über unkomprimierte Dateiformate (BMP, rohe Vertexdaten, rohe Indexdaten), die ich von der NTFS-komprimierten Festplatte aus direkt als Initialisierungsdaten für Texturen, Vertex- oder Index-Buffer nutzen kann … die Erfahrung zeigt, dass das ab dem zweiten Laden rund zwei- bis dreimal so schnell wie das Laden aus komprimierten Formaten (PNG, komprimierte Indizes, Models etc) ist.

Der Hintergrund ist, dass Windows’ Dateimanager die Dateien im Cache behält – wenn sie NTFS-komprimiert sind, sind sie dann im RAM sogar bereits extrahiert! Sie sind dann bei der nächsten Verwendung direkt parat. Alle nicht von NTFS komprimierten, manuell komprimierten Daten – seien nun Texturen als PNGs komprimiert oder ganze Spieldaten mit LZMA – liegen zwar ebenfalls im Cache, aber immernoch komprimiert. Wendet man die 20 bis 30 MB/s Dekompressionsrate von LZMA nun auf diese Dateien an, die im RAM liegen, ist das ganze plötzlich garnicht mehr so schnell wie es sich beim Extrahieren von Festplatte anhört.

Ich bin zwar ein ziemlicher Fan von Kompression jeglicher Art, aber wenn man diese Verantwortung zu jemandem dirigieren kann, der damit viel effizienter umgeht (z.B. der Windows-File-Manager), nutze ich lieber diese Möglichkeit. Wenn ich demgegenüber was ins Web hochlade, meine wöchentliche Sicherheitskopie mache oder Screenshot-Gallerien archiviere, wird bis zum Maximum komprimiert.


Übrigens habe ich gehört, dass LZMA am besten auf möglichst rohe Daten anwendbar ist (LZMA-komprimierte TGAs sollen nochmal besser performen als optimierte PNGs) – wenn man die Daten zur Installation oder zum Download komprimieren möchte, sollten Rohdaten also nochmal Vorteile haben. Ist aber jetzt aus zweiter Hand.

[Schrompf]

Ich würde dazu auch ein Filesystem einsetzen, was *nur* nachher in der Installation auf dem Kundenrechner aus Archiven lädt. Vorher verschwendet man damit einfach viel zu viel Zeit. Das FS sollte also so entworfen sein, dass es mit beiden Herangehensweisen transparent umgehen kann.

Ich hatte dazu mal vor, mir ein FS zu schreiben, dass am Anfang den Verzeichnisbaum des Spiels durchsucht und eine Tabelle der Dateien aufstellt. Dabei gefundene Archivdateien werden geöffnet und die in ihrem Header aufgelisteten Dateien ebenso der Tabelle hinzugefügt. Damit hat man einen sauberen Hybriden, der Dateien aus beliebigen Quellen frisst. Während der Entwicklung liegen alle Dateien roh rum, und für's Release nachher verpackt man alle in ein paar Archive und löscht die Orginale. Optimierungen wie das Vorladen eines ganzen Archivs für Schnellzugriff kann man ja dann immernoch einbauen, Kompression oder ne schlichte Verschlüsselung genauso. Und man könnte damit Addons oder Patches realisieren, indem man in den Archiven intern eine Priorität ablegt. Wenn man dann einen Patch nachreicht, kann man den in ein Archiv mit eins höherer Priorität verpacken und das Filesystem bevorzugt die neuen Dateien dann automatisch. Die Priorität wäre dann idealerweise Echte Datei > Archiv mit höherer Priorität > Archiv mit niedrigerer Priorität

[Krishty]

Und man könnte damit Addons oder Patches realisieren, indem man in den Archiven intern eine Priorität ablegt.

Das ist ein sehr nützlicher Punkt, man kann z.B. zerstörte Umgebung mit den üblichen Spielständen speichern und diesem Verzeichnis eine höhere Priorität zuordnen, so dass beim Laden eines Spielstandes automatisch die zugehörigen Veränderungen an der Umgebung mitgeladen werden.

[Aramis]

Ich nutze den Trick im oben skizzierten System z.B. auch um Übersetzungsbedüftiges auszulagern. Jede Sprache kann jede beliebige Resource überschreiben, da das Verzeichnis in dem sprachspezifische Dateien liegen vom VFS hinter den Kulissen mit den 'normalen' Resourcenverzeichnissen zusammengeführt wird, aber eine höhere Priorität (bei mir ganz unkreativ als 'virtual timestamp' bezeichnet) besitzt. Das ist etwas, in das man bei einem Hobbyprojekt wohl kaum extra Arbeit investieren würde .. aber nachdem die Infrastruktur da ist, ist es eine leichte Sache.

Während der Entwicklung ist es imho sowieso unumgänglich alle Daten unkomprimiert zu halten. Da ist ein VFS, wie von Schrompf skizziert, nützlich weil es durch die Abstraktion des Dateisystems schlussendlich völlig egal ist wo und wie die Daten dann tatsächlich liegen. Idealerweise käme am Ende der Entwicklung dann ein spezieller Resourcencompiler zum Einsatz, der für die Zielplattform voroptimierte Archive generierte. Aber das entspricht leider nicht ganz der Manpower von 1-Personen-Projekten ;-)

PS: @Krishty - sorry, ich konnte der Versuchung nicht wiederstehen und musste den Querverweis einfach bringen :D

[kimmi]

Lege doch einfach im Dataheader eine Version und eine Checksumme, die zum Beispiel die Größe des Headers beinhaltet. Also so etwas:

Code: Alles auswählen

struct dataHeader
{
  int version;
  ...
  size_t DataSize;
};

Und die Abstraktion der IO-Zugriffe kann später auch noch für andere Kunstgriffe wie zum Beispiel das Laden von Daten über das Netztwerk / Internet etc. verwendet werden, ohne daß der Benutzer sich um die Quelle der Daten Gedanken machen muß. Zum Beispiel nutzt das Nebula-Device einen solchen Ansatz für ihr FS.
Eine Idee für Komprimierung wäre dann ein policy-based Design.

Edit: Im VFS der ZFXCE unterstützen wir dazu noch die Möglichkeit, Archive im Filesystem einzuhängen. Ist eine ganz praktische Sache, wenn man ein eigenes Zip-Archiv hinzufügen möchte.

Gruß Kimmi

[dv]

Nach schätzungsweise sieben designten VFS gehen mir die Gründe aus, um eins mit Packfiles einzusetzen. Teilweise Installation (Packfile 1 & 2 auf HD, 3 & 4 auf CD) war bisher eines der Hauptgründe, das fällt aber immer mehr weg. FAT32 ist auch mittlerweile eher in der Minderheit, somit sind die Clustergrößen kein Problem. Ein VFS, welches nur relative Pfade in absolute Systempfade mappt, ist ok, aber Packfiles?