Die Speicherung von Daten in einem nicht-menschenlesbaren Binärformat kann nützlich sein, da sie viel weniger Platz beanspruchen und das Parsen einfacher und schneller ist. Es scheint viel praktischer, auf eine solche Datei wie auf einen Vektor und nicht wie auf einen File-Stream zuzugreifen.

Die Stream-Funktionalität des regulären Dateizugriffs in C++ ist nützlich für das Parsen von Dateien, aber wenn die Dateien binäre Daten enthalten, ist der einzige Vorteil gegenüber dem alten C-Stil mit getchar(), dass RAII (resource acquisition is initialization) zum Einsatz kommt. Die Speicherung von Daten in einem nicht-menschenlesbaren Binärformat kann nützlich sein, da sie viel weniger Platz beanspruchen und das Parsen einfacher und schneller ist. Es erscheint viel praktischer, auf eine solche Datei wie auf einen Vektor zuzugreifen. Deshalb beschloss ich, eine kleine Bibliothek dafür zu entwickeln.

Aus Gründen, die Teil einer Geheimhaltungsvereinbarung sind, wurde sie mit diesen zusätzlichen, nicht-funktionalen Anforderungen konzipiert:

1. Die Bytes am Anfang der Datei werden eher benötigt als die am Ende und die am Ende nur, wenn die am Anfang benötigt werden.
2. In den meisten Fällen – falls in die Datei geschrieben wird – wird in sie häufig und ans Ende geschrieben, sonst überhaupt nicht.
3. Die Dateien sind nicht groß genug, um den RAM zu füllen, so dass eine Optimierung die nötigen Kompromisse nicht lohnt.
4. Verwendung eines einheitlichen Interfaces, um die Daten in komprimierten Formaten oder auf andere Weise zu speichern.

Die Grundidee

Eine RAII-konforme Möglichkeit, dies zu erreichen, bestünde darin, die Datei zu lesen und einen Vektor mit ihrem Inhalt zu füllen, Zugriff auf den Inhalt des Vektors zu gewähren und ihn vom Vektor in die Datei zurückkopieren zu lassen, wobei die neuen Daten ans Ende angehangen würden. Da der Destruktor nicht trivial sein kann (er muss neben der Flush-Operation auch den Dateinamen speichern), gibt es keine Möglichkeit, dies durch Vererbung von std::vector zu tun.

Die zusätzlichen Anforderungen machen es etwas komplizierter. Das Lesen der gesamten Datei ist möglicherweise nicht erforderlich. Auch das Schreiben ist möglicherweise nicht erforderlich.

Anforderung 1 ermöglicht es uns, die Nutzung zu beschleunigen, indem wir nur die benötigten Bytes und auch nur vom Dateianfang an lesen. Dass der Aufrufer ankündigen muss, wie viele Bytes benötigt werden, kann nervig sein. Also liest man die Datei bis zum angeforderten Byte und einige weitere Bytes voraus, was ein gewisser Prozentsatz der Anzahl der angeforderten Bytes sein kann, mit einer unteren Grenze (das Lesen der ersten paar Bytes würde lange dauern) und einer oberen Grenze (um RAM-Speicherplatz zu sparen). Alle gelesenen Bytes können in einem Vektor gespeichert und bei Bedarf ohne Lesen zurückgegeben werden, da davon ausgegangen wird, dass das Überspringen des Anfangs und das Lesen einiger Bytes am Ende der Datei nicht erforderlich ist.

Bedingung 2 erfordert eine Optimierung für das Anhängen an die Datei. Wenn die vorhandenen Daten nicht geändert werden, sollten sie nur beim Flush angehängt werden. Dies kann gelöst werden, indem man den letzten Index der bereits gespeicherten Daten speichert und verfolgt, ob Änderungen an den Daten in der Datei vorgenommen wurden. Der Operator [] erlaubt sowohl schreibenden als auch nicht-schreibenden Zugriff, aber es ist möglich, zwischen lesendem Zugriff und schreibendem Zugriff durch const-Correctness (also dem korrekten Verwenden des const-Keywords vor einem Objekt) zu unterscheiden. Das kann zu der merkwürdigen Notwendigkeit führen, mit const_cast ein Nicht-const-Objekt in ein const-Objekt umzuwandeln.

Aufgrund der Anforderung 3 ist es nicht erforderlich, Bytes zu entfernen, auf welche bereits zugegriffen und die vermutlich bereits verarbeitet wurden, oder sonstige Tricks, um den Speicherverbrauch zu reduzieren.

Anforderung 4 erfordert die Aufteilung des Objekts in ein Interface und ein Objekt, das die I/O spezifiziert. Unter Ausnutzung der geringen Einschränkungen bei der Vererbung von Implementierungen in C++ kann die Interface-Klasse die Zugriffslogik enthalten. Auf diese Weise können wir nicht-inline-bare virtuelle Funktionen beim Zugriff auf die einzelnen Bytes vermeiden und virtuelle Methoden nur für den ohnehin viel langsameren Festplattenzugriff verwenden.

Die Implementierung

Ich habe zuerst eine übergeordnete Klasse namens MemoryMappedFileBase erstellt, die den Dateinamen, die Daten und den Änderungsstatus verwaltet. Sie bietet Zugriff auf die Daten über den Operator [], die Prüfung, ob bestimmte Bytes gelesen werden können, Schnittstellen zum Dateizugriff über die Funktionen load() und flush() und eine Schnittstelle mit Standard-Implementierungen zum Anhängen.

Dann habe ich eine Unterklasse namens MemoryMappedFileUncompressed erstellt, um die Binärdaten normal auf der Festplatte zu speichern. Sie implementiert die Funktionen load() und flush() und ersetzt die standardmäßig implementierten Anhängefunktionen, so dass nur durch Anhängen an eine Datei geflusht werden kann (was bei komprimierten Dateien möglicherweise nicht machbar wäre).

Das Ergebnis ist eine Klasse, die einen viel bequemeren Zugriff auf Binärdateien ermöglicht:

MemoryMappedFileUncompressed file("saved_stuff");
file.push_back('a');
file.push_back('h');
file.push_back('o');
file.push_back('y');

for (int i = 0; file.canReadAt(i); i++) {
  std::cout << file[i];
}
std::cout << std::endl;

Objekte statt Bytes

Das byteweise Lesen der Datei ist lästig, da es sich bei den Daten meist um Zahlen in Ganzzahl- oder Float-Binärformaten handelt, also um Strukturen, die aus solchen Zahlen bestehen. In ausgeklügelteren Fällen kann es auch Zeichenketten mit fester Breite, Flags oder Indizes geben, die auf andere Elemente im Array verweisen (Pointer können nicht auf diese Weise gespeichert werden und sind in der Regel ohnehin unnötig groß.).

Dies wird durch eine Template-Klasse namens MemoryMappedFile implementiert, die auf die in einer Unterklasse von MemoryMappedFileBase gespeicherten Daten zugreift, ohne sie Byte für Byte zu kopieren (mit reinterpret_cast auf Zeiger und neu berechneten Grenzprüfungen).

Dies ermöglicht eine einfache Speicherung von Objekten:

struct Entry {
  uint32_t timestamp;
  int32_t value;
  Entry(uint32_t timestamp, int32_t value) :
      timestamp(timestamp), value(value) {}
}
MemoryMappedFile<Entry, MemoryMappedFileUncompressed> file("stuff");
file.push_back(Entry(time(nullptr), 13));

std::cout << file[0].timestamp << " " << file[0].value << std::endl;
std::cout << "Size is now: " << file.size() << std::endl;

Das kann zu Problemen beim Memory-Alignment führen. Im Beispiel ist die Struktur 8 Bytes lang und auf 32-Bit- und 64-Bit-Architekturen identisch, aber wenn sie 12 Bytes benötigte, könnte sie die gleiche Größe von 12 Bytes auf 32-Bit-Architekturen und eine abweichende Größe von 16 Bytes auf 64-Bit-Architekturen haben. Es ist Sache des Benutzers, es bei Bedarf richtig auszurichten.

Kompression

Die Größe der Daten kann durch Kompression reduziert werden. Das sich wiederholende Muster der enthaltenen Objekte ermöglicht gute Kompressionsraten, sogar über 75%. Wie man vermutlich aus dem Namen MemoryMappedFileUncompressed erraten kann, geschieht dies durch eine andere Klasse namens MemoryMappedFileCompressed, die sehr ähnlichen Byte-Zugriff erlaubt, jedoch aus Daten, die in einem Archiv gespeichert sind.

Ein sehr guter Komprimierungsalgorithmus ist LZMA, das in den Archivformaten 7z und xz verwendet wird. Ohne lange darüber nachzudenken, habe ich mich für das LZMA SDK entschieden, einfach weil es dafür bekannt ist, am effizientesten zu sein. Seine Schnittstelle ist in etwa so freundlich wie ein Schutzstaffel-Todeskommando (wörtl., Anm. d. Übers.), so dass es geradezu masochistisch war, einige Fassadenfunktionen zum Laufen zu bringen. Verdammt, es erforderte sogar, ihm einen Zeiger zu einer Funktion zu liefern, während es annahm, dass 8 Bytes vor diesem Zeiger ein Zeiger ist, den die Funktion als ihr Argument empfängt, damit die Information übergeben werden kann, mit welcher Datei sie arbeiten muss. Als ich es schließlich zum Laufen brachte, stellte sich heraus, dass es auf der Windows-API aufsetzt (ich war auf Windows, weil Unternehmen oft an unklugen Entscheidungen hängen bleiben, die in der fernen Vergangenheit getroffen wurden). Man könnte es mit XZ Utils oder durch Refactoring (was es dringend benötigt) und die Verwendung von Standard-Bibliotheken für die Windows-API-Funktionalität überarbeiten, doch das werde ich nicht bald tun.

Die Klasse kann verwendet werden, indem man MemoryMappedFileCompressed überall anstelle von MemoryMappedFileUncompressed in den Beispielen einsetzt.

Fazit

Aus Gründen, die ich nicht offenlegen darf, habe ich eine Bibliothek zum Speichern von Objekten in Dateien erstellt, die häufiges Anhängen und das Lesen von Objekten von Dateianfängen optimiert, die sowohl komprimierten als auch unkomprimierten Zugriff mit einer vektorähnlichen Schnittstelle ermöglicht. Der Quellcode ist auf meiner Github-Seite. Seine Header sind für weitere Informationen sehr detailliert kommentiert.

Dieser Artikel erschien auch auf Michal’s Blog und wurde von André Hahn übersetzt.