2 Textdateien vergleichen

[TigerLilly]

Vergleich ist via File/Stream und CompareMem, Blockgröße 4096.

[Michael II]

Hashes - zum Beispiel MD5 sind v.a. gut um zu checken, ob zwei Bitfolgen (hier Files) voneinander verschieden sind. Wenn man aber wie hier gefordert sicher auf Gleichheit von zwei Files checken will und allein zum Beispiel MD5 verwendet, dann fliegt einem das sogar bei reinen Textfiles sowas von rasch um die Ohren.

Zwei Beispiele: MD5 Files enthalten irgendwelche Bitfolgen. MD5 bildet jede Bitfolge eindeutig auf einen 128Bit Wert ab. Bei allen Files mit genauer Länge 128Bit = 16 Bytes könnten also all diese Mini-Files effektiv einen voneinander verschiedenen Hash aufweisen. Nehmen wir nur eine einzige weitere Bitfolge zum Beispiel 0 oder 10 oder was auch immer dazu hat man bereits sicher Kollisionen. - Bei einer Bitfolge mit genauer Länge 32 Bytes wird es im Schnitt 2^16-1 weitere Bitfolgen der Länge 32 Bytes geben, welche denselben Hash aufweisen.

Gesuchtes Beispiel? - Das kann doch bei Textfiles nicht passieren...!
MD5 bildet alle Bitfolgen dieser Welt auf jeweils einen 128Bit Wert ab. Das sind 2^128 = 3*10^38 voneinander verschiedene Werte. Wenn wir alle Textfiles mit zum Beispiel genau 39 Ziffern betrachten (und solche Files gibt es in der Praxis in Massen), dann benötigten wir eine Hashfunktion mit 10^39 möglichen Werten um all diese Files voneinander unterscheiden zu können; MD5 liefert aber nur 3*10^38.

Hashes sollten in diesem Thread zwar vom Tisch sein: Dennoch zum Speedvergleich Hash vs. CompareMem. Da muss CompareMem sowas von gewinnen. Die Gründe liegen auf der Hand. Wenn dem in Tests nicht so sein sollte, dann will ich je den Code sehen...

[TigerLilly]

Alles gut. Tatsächliches Vergleichen ist besser, Hashes können Kollisionen haben + damit wären unterschiedliche Dateien als gleich beurteilt. Ich wollte nur mehr wissen, was die Laufzeiten anbelangt.

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen, aber auch da ist der Vergleich schneller +hat den Vorteil, uU vorzeitig abbrechen zu können.

[himitsu]

CompareMem bricht beim ersten Unterschied ab,
während er Hash immer alles durchgehen muß.

Allerdings wird beim Hash immer nur auf einen Speicherbereich gleichzeitig zugegriffen werden,
während beim Direktvergleich eventuell öfters im Cache die Speicherbereiche umgeschaltet/neugeladen werden müssen.
Dagegen wird bei einem Hash aber auch bissl was "berechnet", was wieder bissl Zeit braucht.



Und ja, auch unterschiedliche Dateien können den selben Hash besitzen.
OK, ein guter Hash-Algorithmuß sollte kleinere Änderuungen gut abfangen, aber dennoch ist es möglich.

Ein MD5 ist 128 Bit (4 Integer bzw. 16 Byte) groß und kann somit 2^128 verschiedne Werte speichern.
also bei 17 Byte Dateigröße gibt es durchschnittlich 256 Datei-Versionen mit dem selben Hash, und je größer um so "schlimmer",
auch wenn es "statistisch" relativ unwahrscheinlich ist, dass im "realen" Umfeld zwei Dateien den gleichen Hash haben werden,
da es immerhin 340.282.366.920.938.463.463.374.607.431.768.211.456 unterschiedliche Hashs gibt und bei den Dateien auch nie "alle" Bit-Versionen existieren, aber unmöglich ist es nicht.



Der Hash ist für einen ersten Schnellen vergleich gut, z.b. um mehrere Dateien in einer Liste abzugleichen, aber will man wirklich auf "Gleichheit" prüfen, dann ist nur der Direktvergleich 100%ig sicher.
Ist der Hash aber schon unterschiedlich, dann kann der Direktvergleich auch nichts Anderes mehr aussagen. (je nach Komplexität der Daten kann man bei schnellem Kleinkram wie CRC32 anfangen, bis hin zu größeren/komplexeren Hashs)


Im Delphi findet man mehrere Hashs, wie z.B. CRC32, MD5, SHA1, SHA2, SHA512 oder BobJenkins und bis runter zu Word / 16 Bit (TIdHash16).

[Michael II]

Zitat von TigerLilly:

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen,

Was dann auch wieder eine sehr, sehr einfache Hashfunktion mit noch mehr Kollisionen wäre.... - ich mach jetzt kein Beispiel... .

[Uwe Raabe]

Bei meinen Versuchen braucht THashMD5 ca. 9x soviel Zeit wie ein CompareMem auf 4k Blöcke bei identischen Dateien von ca. 600kB

Vergrößere ich die Blöcke auf 32k, steigt der Faktor auf ca. 30!

[KodeZwerg]

Zitat von Uwe Raabe:

Bei meinen Versuchen braucht THashMD5 ca. 9x soviel Zeit wie ein CompareMem auf 4k Blöcke bei identischen Dateien von ca. 600kB

Vergrößere ich die Blöcke auf 32k, steigt der Faktor auf ca. 30!

Hallo Uwe!

Wir hatten ja das Thema Benchmark schon einmal, wo ich eher synthetisch vorgegangen war weil mir das hier schwer fällt:
"eine methode so zu gestalten das sie nicht den Cache benutzt"

Von daher meine Frage, könntest Du Deinen Bench-Code bitte posten, daran bin ich sehr interessiert!

[TigerLilly]

Zitat von Michael II:

Zitat von TigerLilly:

Eine Alternative zum Hash wäre gewesen, die Buchstaben in jeder Datei zu zählen und diese Summen dann zu vergleichen,

Was dann auch wieder eine sehr, sehr einfache Hashfunktion mit noch mehr Kollisionen wäre.... - ich mach jetzt kein Beispiel... .

Jein. Ja, weil du recht hast, es kann Dateien geben, die sich nur durch Vertauschungen unterscheiden. Nein, weil es in diesem Fall auf Grund der daten nicht sein kann, dass es nur Vertauschungen gibt.

[KodeZwerg]

naja, "abc" ist beim zählen das selbe wie "xyz", also das würde ich generell ausschliessen aber kommt, wie du gerade geschrieben hast, auf die vor-ort situation an.

[Uwe Raabe]

Zitat von KodeZwerg:

Von daher meine Frage, könntest Du Deinen Bench-Code bitte posten, daran bin ich sehr interessiert!

Klar, kein Problem. Das Caching des Betriebssystems kann ich natürlich so nicht umgehen, aber ich kann adäquate Voraussetzungen für ein qualifiziertes Ergebnis schaffen. Da ich hier auf einer NVMe SSD arbeite, spielt das eh keine große Rolle.

Delphi-Quellcode:

program CompareFileBench;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Classes,
  System.Hash,
  System.Diagnostics;

function AreFilesEqual(const FileNameA, FileNameB: string; BlockSize: Integer = 4096): Boolean;
var
  a: TBytes;
  b: TBytes;
  cntA: Integer;
  cntB: Integer;
  readerA: TStream;
  readerB: TStream;
begin
  Result := False;
  readerA := TFileStream.Create(FileNameA, fmOpenRead);
  try
    readerB := TFileStream.Create(FileNameB, fmOpenRead);
    try
      SetLength(a, BlockSize);
      SetLength(b, BlockSize);
      repeat
        cntA := readerA.Read(a, BlockSize);
        cntB := readerB.Read(b, BlockSize);
        if cntA <> cntB then Exit;
        if cntA = 0 then Break;
        if not CompareMem(@a[0], @b[0], cntA) then Exit;
      until cntA < BlockSize;
      Result := True;
    finally
      readerB.Free;
    end;
  finally
    readerA.Free;
  end;
end;

procedure Test;
var
  c1: string;
  c2: string;
  I: Integer;
  sw: TStopwatch;
begin
  c1 := '<some file>';
  c2 := '<some other file with the same content>';

  { Dummy call to fill the cache }
  AreFilesEqual(c1, c2, 16*1024);
  sw := TStopwatch.StartNew;
  for I := 1 to 1000 do
    AreFilesEqual(c1, c2, 16*1024);
  Writeln(sw.ElapsedMilliseconds);

  { Dummy call to fill the cache }
  THashMD5.GetHashBytesFromFile(c1);
  THashMD5.GetHashBytesFromFile(c2);
  sw := TStopwatch.StartNew;
  for I := 1 to 1000 do begin
    THashMD5.GetHashBytesFromFile(c1);
    THashMD5.GetHashBytesFromFile(c2);
  end;
  Writeln(sw.ElapsedMilliseconds);
end;

begin
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.