Schnelles Dekomprimieren (das Komprimieren ist nicht zeitkritisch)
Hi,
ich bin auf der Suche nach einem schnellen Algoritmus zum dekomprimieren von byte Arrays. Die Kompression selber ist nicht zeitkritisch. Ich habe bisher die Klassen aus dem System.IO.Compression Namespace ausprobiert und dieses Projekt: Better Than Zip Algorithm For Compressing In-Memory Data
Kennt jemand noch was schnelleres? Von System.IO.Compression.DeflateStream zu IMCompressor konnte ich schon eine signifikante Verbesserung erkennen.
Wenn es dir nicht auf die Kompressionsrate ankommt, könntest du eine Lauflängen-Kodierung implementieren (siehe Lauflängenkodierung).
Weeks of programming can save you hours of planning
Die Kompressionsrate ist schon wichtig. Am Ende muss es ein Kompromiss zwischen Geschwindigkeit und Kompressionsrate geben.
Dann hab ich auch keine Alternative. Ich denke, die Verwendung des GZipStream wird wohl die beste Lösung sein.
Weeks of programming can save you hours of planning
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Danke für die Vorschläge, werde ich alles mal testen. Wie geschrieben, habe ich alles aus dem Compression Namespace ausprobiert und bin damit nicht zufrieden. Die Implementierung aus dem Codeproject Artikel ist ca. 25% schneller beim Entpacken.
Evtl. kannst du auch durch Techniken wie Caching oder paralleles Vorausentpacken wahrscheinlich benötigter Arrays die Performance deutlich verbessern.
Ja, das werde ich auch machen. Im Moment versuche ich das Entpacken selber erstmal zu optimieren.
Hallo Sascha M.,
Die Kompressionsrate ist schon wichtig. Am Ende muss es ein Kompromiss zwischen Geschwindigkeit und Kompressionsrate geben.
solange du nicht die genauen Anforderungen und Kriterien offenlegst, bleibt das ganze Spekulation. Auch die Kenntnis des Hintergrunds bzw. der Art der Daten würde vermutlich helfen. Und auch der Grund, warum das Entpacken so zeitkritisch ist.
herbivore
Hi,
die Daten sind Binärdateien, die eine sehr ineffektive Speicherung der Daten haben. Mit rar kann ich eine solche Datei im Extremfall Faktor 90 verkleinern. Daran kann ich aber leider nichts ändern.
Jetzt teile ich eine solche Datei in Blöcke auf, komprimiere die Blöcke und schreibe sie in eine neue Datei zurück mit ein paar Metadaten zum entpacken. Im Grunde ist es eine transparente Komprimierung, d.h. für den Benutzer ist es so als würde er mit der original Datei arbeiten. Die Performance beim Entpacken ist wichtig, weil ein Prozess permanent auf die Daten zugreift (ReadOnly).
Eigentlich ist es wie bei der NTFS Komprimierung. Datei bzw. Dateiblöcke sollen gepackt abgelegt und für den Prozess transparent entpackt werden. Problem bei der NTFS Komprimierung ist das Fragmentieren der Daten auf der Platte. Das hat den Zugriff enorm verlangsamt.
Jetzt suche ich also nach einer Möglichkeit die Daten schon komprimiert abzulegen, um die Fragmentierung zu verhindern.
Das sind so grob die Rahmenbedingungen...
Hallo Sascha M.,
beim Dekomprimieren fragmentiert doch nichts. Fragmentieren tuts doch nur, wenn Daten geschrieben werden (und deren Länge - zumindest nach der Kompression - anders ist also vorher). Das Schreiben/Komprimieren von Daten hast du als performance-unkritisch beschrieben. Wenn du dafür wirklich genug Zeit hast, kannst du die Datei doch von Anfang bis Ende neu schreiben, um ein Fragmentieren (weitestgehend) zu vermeiden. Oder übersehen ich was?
herbivore
Hi,
vielleicht habe ich es auch nicht richtig beschrieben. 🙂
Das beim Dekomprimieren nichts fragmentiert wird ist mir schon klar.
Der Ist-Zustand ist folgender. Ich habe eine Datei auf Platte in einem ineffektivem Format. Aus diesem Grund ist die NTFS-Komrimierung an. NTFS-Komprimierung fragmentiert und der Zugriff wird langsamer.
Jetzt möchte ich das Komprimieren durchführen, bevor die Datei auf der Platte landet. Also von Anfang bis Ende durchschreiben und die NTFS Komprimierung ausschalten.
Da aber eine ReadOnly Anwendung(die ich ändern kann) die Daten in unkomprimierter Weise erwartet, muss es transparent sein. Die Dateien haben eine Größe von 100Kb bis zu 1Gb und der Zugriff erfolgt Random. Die ReadOnly Anwendung holt z.B. 100 byte aus der 1Gb Datei ab Pos x und 10 Sekunden später 250 byte ab Pos y.
Hallo Sascha M.,
wenn du große Datenmengen am Stück lesen würdest, könnte eine stark komprimierte Datei sogar deutliche Performance-Vorteile haben, weil der Flaschenhals normalerweise nicht das Dekomprimieren ist, sondern die von der Platte zu lesende Datenmenge. Aber wenn du tatsächlich immer nur sehr kleine Datenmengen ausliest, dann wird sich ein (deutlicher) Overhead nur schwer oder gar nicht vermeiden lassen, denn du musst so oder so mindestens und bei unkomprimierten Daten meistens gleichzeitig höchstens einen Datenblock lesen. Bei komprimierten Dateien kommt eben noch die Zeit für die Dekompression dazu und - da man normalerweise nicht einfach mittendrin anfangen kann (zu lesen) und zu dekomprimieren - muss hier evtl. sogar (viel) mehr (davor) gelesen werden, bis man bis zur fraglichen Stelle dekomprimieren kann.
Eine Möglichkeit wäre es, wenn du immer soviele Daten komprimierst, bist die komprimierten Daten die Größe eines Clusters (also die Menge an Daten, die von einer Festplatte immer auf einen Rutsch gelesen werden) erreicht haben. Genauer vier oder acht Byte weniger als ein Cluster, denn in diese Bytes musst du dann immer den Offset (und die Länge) schreiben, an dem das jeweilige Datenpaket bezogen auf die unkomprimierten Daten beginnt. Dann kann man jeden Cluster für sich dekomprimieren.
Bleibt das Problem, dass man diesen Cluster erstmal (möglichst schnell und ohne viele andere Cluster zu lesen) finden muss. Dazu könnte man die Offsets evtl. auch in einer Art Inhaltsverzeichnis ganz an den Anfang (oder ganz ans Ende) der Datei schreiben.
Vielleicht ist es aber noch besser, wenn du die Cluster nicht - wie eben beschrieben - vollständig ausnutzt, sondern immer eine feste Datenmenge in einen Cluster schreibst. Die muss man natürlich so wählen, dass die Daten nach der Kompression nie länger sind als ein Cluster. Man hat also einen Verschnitt, der um so größer ist, je ungleichmäßiger sich die Daten komprimieren lassen. Dafür kann man dann aber auch direkt und exakt ausrechnen, welchen Cluster man lesen muss, um an die gewünschten Daten zu kommen.
Insgesamt scheint mir das Problem also nicht zu sein, wie schnell die Dekompression der Daten nun wirklich ist, sondern wie schnell und mit wie wenig Dateizugriffen man an die Daten kommt, die man dekomprimieren muss.
herbivore
Hi,
im Grunde mache ich schon das was Du beschrieben hast. Ich habe ein Inhaltsverzeichnis am Anfang der Datei. Kommt der Benutzer an und möchte die Daten an Pos x haben, schaue ich nach in welchem komprimierten Block Pos x ist und entpacke den. Je kleiner dieser Block, umso schneller ist mein Zugriff, aber desto größer die Datei. Der Zugriff auf die Daten, die entpackt werden müssen ist nicht das Problem. Meine Messungen habe dort ergeben, dass dies nur einen minimalen Unterschied macht. Das mit den Clustern werde ich mal testen, dort kann ich vielleicht noch etwas rausholen...
Hallo Sascha M.,
Je kleiner dieser Block, umso schneller ist mein Zugriff, aber desto größer die Datei.
grundsätzlich ist das richtig. Allerdings schiebst du ja, dass die Datei sehr redundant ist. Das spricht dafür, dass einige wenige Sequenzen sehr häufig auftreten. Diese könntest du vorab durch kürzere Codes ersetzen. Im Grunde schlage ich also eine Art Huffman coding vor, nur nicht auf Buchstabenebene, sondern auf Ebene der wiederkehrenden Sequenzen. Je häufiger und länger eine Sequenz ist, desto kürzer sollte der Code für sie sein.
Weil diese Ersetzung global erfolgt, spielt es eine geringere Rolle, wie oft eine bestimmte Sequenz innerhalb eines Clusters vorkommt. Deshalb wirken sich kleinere Blockgröße weniger stark auf die Gesamtgröße der Datei aus.
herbivore