Optimierung einer Deflate-Kompression

[3_of_8]

Morgen.

Ich habe Klassen zum Parsen einer GZIP-Datei und für die Dekompression zur Dekodierung von Deflate-Daten.

Beschrieben ist das ganze in den RFCs 1951 und 1952.

Das ganze funktioniert, das größte Problem ist aber, dass das ganze furchtbar lahm ist. Während gzip auf meinem alten 300MHz (vielleicht auch etwas mehr) Server mit Linux bei einer 4,5 MB-Datei für die Dekompression irgendwo im Bereich <200ms liegt, braucht mein Code dafür auf meinem 1,6 GHz-Notebook schon 2,7s. Auf meinem 2,66 GHz-PC braucht mein Programm schon um die 8s, auf meinem Server von vorhin noch einmal deutlich mehr.

Dabei habe ich schon alle möglichen Optimierungen versucht. Zuerst hatte ich einen Bitbaum, habe alle Bits einzeln eingelesen und dann über den Baum den Wert herausgefunden. Dann habe ich versucht, Bits zusammenzufassen, soweit möglich, und eine Tabelle aller Codes für jede Bitlänge anzulegen. Das hat aber so gut wie keine Verbesserung der Geschwindigkeit gebracht. Dann habe ich eine Tabelle aller Codes auf die Maximalanzahl von Bits ausgerichtet erstellt. Das hat schonmal eine deutliche Geschwindigkeitserweiterung gebracht, nämlich von 3,7s auf 2,7s. Das ist aber immer noch viel zu langsam.

Wie könnte man es noch weiter optimieren?

Ich habe ein Testprojekt als Anhang hochgeladen und eine .tar.gz-Datei zum Testen findet ihr hier.

(Hinweis: Die .tar.gz-Datei im Beispielprojekt im Anhang ist eine andere als die, mit der ich die Zeitwerte oben gemessen habe. Die Datei im Anhang liegt bei meinem Notebook bei zwischen 3,9s und 5,1s.)

[jbg]

Hast du schon mal dran gedacht einen Puffer für die I/O Operationen zu nutzen. Bei einem "AStream.Read(b, 1);" ist der Overhead des Funktionsaufrufs größer als der Nutzen.

[3_of_8]

Ich habs schonmal probiert, aber es hat nichts gebracht, bzw. es hat das ganze sogar noch langsamer gemacht, als es eh schon war.

Wie es aussieht, ist ist die zeitaufwändigste Operation das Einlesen der dynamisch komprimierten Blöcke. Die schlägt ungefähr 500-1000 mal so stark zu Buche wie alles andere. Ich verstehe auch nicht, warum ein Eingabepuffer keine Verbesserung bringt.

EDIT: Oha. Ich hab das ganze nochmal probiert, den Code neu geschrieben, mit einem Eingabepuffer von 32KB. Jetzt ist die Zeit zwischen 0,2 und 0,5 Sekunden. Ich habe keine Ahnung, warum der letzte Versuch mit Eingabepuffer keine Verbesserung gebracht hat.

[Skasch]

Hi,

nur zur Information hab ich meine Variante der gzip Decompression mal angefügt.
Hierfür benutze ich schlicht und ergreifend die verbesserte version der Borland ZLib von www.dellapasqua.com.

Ein paar Änderungen waren dazu jedoch nötig:

1) Um GZIP-Streams lesen zu können muss das ZLib Object anders initialisiert werden, nämlich so, dass kein Header und keine Adler-Checksum verwendet wird.
Der parameter "windowBits" muss also mit negativem Wert belegt werden und DeflateInit2(..) muss verwendet werden statt DeflateInit(..).
Zur Info: DeflateInit(..) ruft implizit DeflateInit2(..) auf.
2) Die Implementation im original ZLibEx.pas hat kein "rewind" auf den unbenutzten Part des gelesenen streams ausgeführt.
Jetzt schon ;-)

Speichern als GZIP ist auch im TZCompressionStream aufgenommen aber bislang ungetestet.

Performance:
Da der Dateilink auf test.tar.bz nicht mehr geht hab ich eine Datei mit ca. 3,5Mb entpackt und komme dann auf max 0,35ms auf nem alten 988MHz Schlepptop.

"jbg" hat schon bemerkt dass die Implementation der AdDeflate.pas ziemlich unwirtschaftlich in Punkto CPU-Costs ist, dem kann ich nur beipflichten.
Der Weg über ZLib ist wohl wesentlich effektiver.

Gruss,

O.

[3_of_8]

Schau dir mal meinen Edit an. Ich hab das ganze nochmal mit Eingabepuffer geschrieben und jetzt ist es ziemlich schnell. Bei der ZLIB hat man möglicherweise das Problem, dass die Borland-Header möglicherweise nicht für Linux, Mac usw. verfügbar sind. Da ist eine Unit, die komplett unabhängig von Drittbibliotheken ist, meiner Meinung nach sinnvoll.

[Skasch]

Hi 3_of_8,

welche "Borland-Header" meinst Du?
Das zlib von Delphi baut doch auf die Objekte Adler32 und deflate von Mark Adler und Phil Katz auf. Die sind in ansi-c geschrieben und für MAC und Linux verfügbar.
ZLib ist lediglich ein Wrapper für die genannten *.obj Binaries.

Meines Erachtens nach ist es leichter auf einen Standart aufzubauen, da dann die Kompatibilität mit anderen Z-Streams gewährleistet ist, meinst Du nicht?

Da die Bibliotheken tausendfach getestet sind und wirklich sehr schnell sind verwende ich diese.

AdDeflate.pas ist schon ok, baut aber eben nicht auf die Standart implementationen auf und kann nicht als GZIP komprimieren, was die zlib kann.


Gruss

O.