Optimierungsvorschlag Prüfsummenmethoden

Deutscher Support für die Software AllDup
Post Reply
Anselm
Posts: 64
Joined: 21 Mar 2013, 21:04

Optimierungsvorschlag Prüfsummenmethoden

Post by Anselm »

Bei vielen Dateien mit dem selben Inhalt ist die Prüfsummen-Methode klar im Vorteil.

Die "Byte für Byte" Methode bietet bei vielen gleich großen,aber unterschiedlichen Dateien den Vorteil, dass sie einen Datenblock am Ende (und am Anfang durch die Blockgröße des Lesepuffers) der Datei nutzen kann, um schnell zu erkennen, dass die Dateien inhaltlich nicht gleich sein können.

Diese Idee könnte man doch auch für die Prüfsummenmethode nutzen. Beim Bestimmen der Dateien werden ein paar Bytes vom Ende (möglichwerweise Anfang, Mitte) gelesen und im Hauptspeicher gehalten. Nur wenn sie unterschiedlich sind, werden die Prüfsummen bestimmt.
goldkante
Posts: 164
Joined: 28 May 2017, 17:00

Re: Optimierungsvorschlag Prüfsummenmethoden

Post by goldkante »

Anselm wrote: Diese Idee könnte man doch auch für die Prüfsummenmethode nutzen. Beim Bestimmen der Dateien werden ein paar Bytes vom Ende (möglichwerweise Anfang, Mitte) gelesen und im Hauptspeicher gehalten. Nur wenn sie unterschiedlich sind, werden die Prüfsummen bestimmt.
Gibt es hierzu irgendwo im Forum eine Äußerung und/oder aufklärende Informationen, inwieweit dieses Vorgehen Performance einsparen würde/könnte?

Evtl. sogar vom Entwickler himself?

Ich versuche mich gerade schlau zu lesen bzgl. der Anwendung der Prüfsummen in AllDup, sowie deren Sinn/Zweck/Nutzungs-/Speichermöglichkeiten, finde zu diesem interessanten Thema hier aber nichts aussagekräftiges (außer dem Wenigen in der Hilfe und hier).
sdfgdhfgh
Posts: 34
Joined: 02 Feb 2014, 17:36

Re: Optimierungsvorschlag Prüfsummenmethoden

Post by sdfgdhfgh »

Disclaimer: Alle Äußerungen nach bestem Wissen basierend auf technischem Verständnis und Jahrelanger Nutzung von AllDup. Ich bin kein Entwickler von AllDup und mag mich gerade bzgl der konkreten Implementierung Irren. In diesem Fall bitte ich um Korrektur durch den Administrator.

Zur Kombination hash-basiert und "nur Ende":

Das lässt sich nicht allgemein sagen. Es hängt (mindestens) von den Datenbeständen und den Vorfiltern ab. Vergleichst du zwei Verzeichnisse mit identischen Daten und ordentlichem Vorfilter (durch Dateiname, Änderungszeit etc), so würde die vorgeschlagene Variante langsamer sein, da nach dem Vorfilter alle oder fast alle potentiellen Dubletten-Paare echte Dubletten sind. Von jeder Datei wird zunächst das Ende gelesen, das wegen des präzisen Vorfilters zumeist identisch ist, und anschließend wird noch die ganze Datei gelesen. Je nachdem wie groß das "Ende" im Verhältnis zur Gesamtdatei ist kann hier großer Overhead entstehen.
Das könnte man etwas reduzieren, indem man die zweite Prüfsumme auf den Datenteil ohne das Ende berechnet. Bei SSDs dürfte das dann fast kein unnötiger Overhead mehr sein, bei HDDs (mechanisch) kann das durch Seek dennoch langsamer sein, als gleich die ganze Prüfsumme zu berechnen.

Hast du jetzt aber Datenbestände mit vielen aufgeteilten Dateien in Blöcke identischer Größe (z.B. Jede Nutzdatei ist in Blöcke von exakt 100MB aufgeteilt) mit wenigen Dubletten und ohne ordentlichen Vorfilter oder Vorfilter-Möglichkeit, so bringt der hier vorgeschlagene Ansatz sehr viel, besonders wenn das Ende im Verhältnis zur Dateigröße klein ist und die Dateien nicht aus irgendwelchen Grünen oft ein identisches Ende haben, obwohl sie nicht identisch sind - was nicht zu erwarten ist.

Zu Hash vs Byte-für-Byte allgemein:

Ein Vorteil von Byte-für-Byte ist, dass nur die notwendigen Dateiteile für den Vergleich gelesen werden - es kann sehr feingranular abgebrochen werden, sobald der erste Unterschied auftaucht. Ein weiterer möglich Vorteil ist, dass die beiden Kandidaten parallel gelesen werden. Bei großen Dateien muss das so sein, um nicht enorm viel RAM zu verbrauchen. Bei kleinen Dateien kann ich nicht abschätzen, wie AllDup das umsetzt. Das kann ein Nachteil sein, wenn die Daten auf der selben, physisch identischen mechanischen Platte liegen (durch Seek).
Der große Nachteil von Byte-für-Byte ist, dass jedes Kandidatenpaar erneut geprüft werden muss, da AllDup "greedy" arbeitet, also schnell Ergebnisse erzeugen will. So wird Dubletten-Kandidat 1 mit Kandidat 2 verglichen. Taucht in der weiteren Verarbeitung ein Kandidat 3 auf, so muss er im günstigen Fall (K1=K2) mit einem, im ungünstigen Fall mit beiden Byte-für-Byte verglichen werden. Wenn sich diese 3 Dateien nun nur im jeweils zuletzt gelesenem Bit unterscheiden, werden die Dateien vollständig gelesen. Schon bei nur 3 Kandidaten also K1+K2 + K1+K3 + K2+K3 - jede datei wird doppelt gelesen.

Der große Vorteil von hash-basierter Suche ist, dass jede Datei nur einmal gelesen werden muss - allerdings einmal vollständig. Bei vielen gleichgroßen Dateien und schlechtem Vorfilter (= viele Kandidatenpaare sind keine echten Dubletten) werden so alle Dateien gelesen, die im Byte-für-Byte womöglich nach wenigen KB vom ende jeweils ausgeschlossen werden können. Weiterer Nachteil bei hash-basiert (in der aktuellen Implementierung, nicht konzeptbedingt) kann sein, dass die Prüfsummen sequentiell berechnet werden, Datei für Datei. Bei physisch getrennten Quellpfaden verschenkt man dadurch viel Leistung, wohl zum Schutz vor dem Leistungsverlust, selbiges auf der physisch selben mechanischen Platte zu tun (wiedermal: Seek). Hat man also zwei Pfade mit (fast) identischen Datenbeständen, physisch getrennte Laufwerke und einen guten Vorfilter (= viele Kandidatenpaare sind auch echte Dubletten), so verdoppelt sich die Suchzeit (bei gleichschnellen Datenquellen)

Wegen letzterer Beobachtung bin ich gerade hier ( http://www.allsync.biz/phpBB3/viewtopic.php?f=2&t=2031 ). Ich hoffe, die Erklärung bringt dich und evtl auch den einen oder anderen weiteren Leser weiter.
Anselm
Posts: 64
Joined: 21 Mar 2013, 21:04

Re: Optimierungsvorschlag Prüfsummenmethoden

Post by Anselm »

Hast du jetzt aber Datenbestände mit vielen aufgeteilten Dateien in Blöcke identischer Größe (z.B. Jede Nutzdatei ist in Blöcke von exakt 100MB aufgeteilt) mit wenigen Dubletten und ohne ordentlichen Vorfilter oder Vorfilter-Möglichkeit,
Ja, ich denke hauptsächlich hier hat man den Nachteil beim Hash-Basiertem Vergleich. Container-Formate, die viele gleich große Dateien haben, aber unterschiedlich sind. Je größer die Dateien um so schlechter. Gesplittete tar,zip,rar,7z Archive. Diskettenformate z.B. .d64, .d80, .adf. Oder auch vob Container.

Ich denke wenn man wenige Bytes vom Ende und von der Mitte nutzt z.B. 8 Byte und für den Vorfilter nutzt kann man für diese speziellen Fälle mit wenig Aufwand einen guten Performance Gewinn erzielen.
sdfgdhfgh
Posts: 34
Joined: 02 Feb 2014, 17:36

Re: Optimierungsvorschlag Prüfsummenmethoden

Post by sdfgdhfgh »

Auch heir wäre eine Rückmeldung dazu schön.
Administrator
Site Admin
Posts: 3673
Joined: 04 Oct 2004, 18:38
Location: Thailand
Contact:

Re: Optimierungsvorschlag Prüfsummenmethoden

Post by Administrator »

Byte-für-Byte:

Die zu vergleichenden Dateien werden beide geöffnet und dann Stück für Stück (sequentiell) eingelesen.
Der Vergleich wird abgebrochen, sobald ein Unterschied auftritt.
Beim erneuten Vergleichen einer Datei wird der physische Zugriff auf die Festplatte durch den Systemcache vermieden.


Hash:

Die Prüfsumme von Dateien wird nur dann erstellt, wenn 2 Dateien miteinander verglichen werden müssen.
Beispiel: Wenn Sie 1000 Dateien überprüfen und nur 2 Dateien die gleiche Größe besitzen, dann werden nur 2 Prüfsummen erstellt.
Post Reply