Kompressionsverfahren im Vergleich
Nachdem wieder mal Kritik an xz hoch gekocht ist, habe ich mich zuerst gefreut, dass ich auf zunehmend auf zstd setze. Dann gab es aber Nachfragen, wie sich den zstd so schlagen würde. Besonders im Hinblick auf den Hutter Prize. Also habe ich mal gemessen.
Der Hutter Prize
Der Informationsgehalt natürlicher (englischer) Sprache liegt bei einem Bit pro Zeichen. Soweit behauptet das die Shannon-Theorie.
Aber wie weit kann man wirklich an das Limit kommen?
Der Hutter Prize stellt vereinfacht gesagt folgende Aufgabe:
- Gegeben ist eine 100MByte Auszug der englischen Wikipedia in XML.
- Nimmt man 1bit/Zeichen als Limit an, so müsste sich dieser Auszug auf 12,5 MByte packen lassen.
- Damit die Aktion fair bleibt und das Kompressionsprogramm nicht selbst den ganzen Text enthält, zählt die Größe des Dekomprimierprogrammes mit.
- Als Qualifikation sind weniger als 16MByte zu schaffen.
- Es gibt eine Zeitbeschränkungen von 10h.
- Da es inkrementelle Fortschritte gibt, wird der Preis auch nur inkrementell ausgezahlt.
Es steht natürlich nicht zu erwarten, dass allgemeine Kompressionsprogramme so dicht heran kommen. Stattdessen ist das theoretische Limit nur dann zu erreichen, wenn man den Kontext der englischsprachigen Welt bereits kennt.
Genauer gesagt, sollte die Dekompression eher wie eine freie Rede unter Zuhilfenahme eines Stichpunktzettels (das Komprimat) ablaufen. Es läuft also auf eine Entwicklung einer partiell begabten künstlichen Intelligenz hinaus, die den Kontext es Stichpunktzettels richtig zu deuten weiß.
In einer solchen Liga spielen die handelsüblichen Programme natürlich nicht.
Messungen
Ich habe das Testfile des Hutter Prizes als Grundlage eigener Messungen genommen. Es entspricht in etwa den Datenbank-Dumps oder den Webseiten typischer CMS-Syteme und damit einem unserer Backup-Szenarien.
Gemessen wurden:
- Kompressionsrate als Anteil der Dateneinsparung. 20% heißt also die 100MByte Datei ist 20% (20MByte) kleiner, die komprimierte Datei hat also 80Mbyte. Größer sind besser.
- Die Zeit zum Komprimieren ist vor allem eine praktische Eigenschaft. Schnelle Algorithmen belasten das System weniger. Kleiner ist besser.
- Speicherbedarf beim Komprimieren ist analog. Insbesondere sollte vermieden werden, dass die Maschine swappen muss. Kleiner ist besser.
- Die Zeit zum Entpacken ist im Recovery-Fall wichtig. Wenn man an Backups ran muss, ist der Zeitdruck meist schon groß. Wenn man dann noch auf's entpacken warten muss, kann das die Nerven völlig zerrütten. Kleiner ist besser.
- Speicherbedarf beim Entpacken ist analog. Ausgepackt wird im Notfall auf stark belasteten Maschinen evtl. sogar parallel. Kleiner ist besser.
zstd läuft hier in zwei Modi: Einmal mit extra Dictionary (-D) und einmal normal. Das Dictionary wurde mit einer Auswahl einiger tausend page-Elemente aus der Originaldatei trainiert. Auf welche Art und mit wie vielen Elementen trainiert wird, macht keinen praktischen Unterschied.
Die Kompressionsoptionen laufen von 1 (schneller) bis zu hohen Werten (kompakter). Die Optionen sind nicht vollständig angegeben.
| Programm | Rate | Zeit (comp) | MB (comp) | Zeit (decomp) | MB (decomp) |
| gzip -1 | 58% | 2,64 | 3 | 1,13 | 3 |
| gzip -9 | 64% | 8,14 | 5 | 1,02 | 3 |
| bzip2 -1 | 67% | 12,24 | 5 | 4,11 | 3 |
| bzip2 -9 | 71% | 12,86 | 27 | 4,91 | 16 |
| zstd -3 | 64% | 1,96 | 12 | 0,51 | 8 |
| zstd -9 | 68% | 9,51 | 45 | 0,64 | 12 |
| zstd -19 | 72% | 78,83 | 231 | 0,46 | 36 |
| zstd -22 | 75% | 126,17 | 2948 | 0,62 | 385 |
| zstd -D | 64% | 2,12 | 16 | 0,48 | 9 |
| zstd -D -9 | 68% | 11,67 | 78 | 0,45 | 13 |
| zstd -D -19 | 72% | 81,88 | 426 | 0,45 | 37 |
| zstd -D -22 | 75% | 128,38 | 5508 | 0,63 | 386 |
| xz | 74% | 98,70 | 376 | 2,40 | 36 |
| xz -9 | 75% | 125,93 | 2688 | 2,16 | 260 |
| xz -9e | 75% | 134,20 | 2688 | 2,47 | 260 |
| Shannon | 88% | ||||
| sha256 | 0,44 | ||||
| sha1 | 0,21 | ||||
Zum Vergleich habe ich die theoretische Grenze und die Verarbeitung der Originaldatei mit zwei Hashverfahren hinzugenommen. Letzteres dient vor allem der Abschätzung, was so beim reinen Durchpumpen der Daten durch die CPU an Arbeit entsteht.
Auswertung
Zuerst zur Kompressionsrate:
Alles über 70% ist großartig, über 60% ist gut. xz und zstd sind also prima, bzip2 kommt nahe ran. Auffällig ist, dass zstd einen großen Bereich an Kompressionsraten abdeckt.
Also schauen wir als nächstes auf die Laufzeiten.
Hier sind die Unterschiede massiv. xz fällt jedoch in allen Varianten aus dem Rahmen.
Also mal nur eine Auswahl der praktisch relevanten Zeiten:
Bei bzip2 überraschen die hohen Entpackzeiten.
Was kann die hohen Packzeiten verursacht haben? In erster Linie könnte die Maschine ins Swappen kommen, wenn der RAM Bedarf die Größe der Testmaschine übersteigt. Das ist tatsächlich ein praktisch relevanter Fall. Also schauen wir mal:
Die Testmaschine hat 2GB RAM, was zum Packen von 100M eigentlich ausreichen sollte. Alles über 1GB ist schlicht indiskutabel. Über Zeiten braucht man da nicht mehr reden.
Auffällig ist, dass zstd mit einem extra Dictionary gar nicht gut fährt. Dieser Modus ist ganz offensichtlich ausschließlich für sehr kleine Dateien wir JSON-Objekte gedacht.
Schauen wir uns noch die relevanten Kandidaten an, die in der großen Übersicht ja gar nicht zu sehen waren. Alles unter 100MByte RAM ist nutzbar:
gzip und bzip2 sind standardmäßig sparsam mit RAM, zstd greift schon gut zu.
Fazit
Ich glaube, dass ich mit zstd gut fahren werde. Die Kompressionsrate ist besser als bei gzip und bzip2, das Einpacken geht schnell und das Auspacken geht doppelt so schnell wie bei den Konkurrenten. Es packt so schnell aus, wie die Prüfsummenberechnung mit sha256 braucht. Das ist beachtlich.