Myers, Patience, Histogram — diff-Algorithmen im Vergleich

Selbst beim Vergleich derselben zwei Dateien kann das Ergebnis je nach diff-Algorithmus unterschiedlich ausfallen. Alle Ergebnisse sind „korrekte“ diffs, aber sie ordnen unterschiedliche Zeilen einander als gleich zu und sind deshalb unterschiedlich gut lesbar. git bietet mit der Option --diff-algorithm vier Varianten an.

Es gibt auch Kurzformen wie git diff --patience und git diff --histogram, und mit git config diff.algorithm histogram lässt sich der Standard ändern.

Myers: der Standard, der die minimale Bearbeitung sucht

Der Myers-Algorithmus sucht den Weg mit der geringsten Zahl von Löschungen und Einfügungen (zum Prinzip siehe Wie diff funktioniert). Schwierig wird es, wenn es mehrere Möglichkeiten gibt, welche Zeilen als gleich gelten. Code enthält viele sehr häufige Zeilen wie }, {, Leerzeilen oder return. Selbst wenn der Algorithmus inhaltlich unzusammenhängende Zeilen paart, kann die Zahl der Bearbeitungen genauso minimal sein.

Dieselbe Änderung, zwei Ergebnisse

Angenommen, zwischen den Funktionen f und g wird eine neue Funktion h eingefügt. Die beiden folgenden diffs bestehen jeweils aus 4 hinzugefügten Zeilen und haben damit dieselbe Zahl von Bearbeitungen.

@@ -1,6 +1,10 @@ int f() {     return 1; }++int h() {+    return 3;+}  int g() {     return 2;

@@ -1,5 +1,9 @@ int f() {     return 1;+}++int h() {+    return 3; }  int g() {

Im ersten erscheint die neue Funktion als Ganzes. Im zweiten wird die schließende Klammer der bestehenden Funktion f als Klammer der neuen Funktion behandelt, und der hinzugefügte Teil ist ungeschickt zerschnitten. Solche Formen entstehen durch die Suchreihenfolge. Neuere git-Versionen korrigieren vieles davon mit einer Heuristik, die die Grenzen eines Änderungsblocks anhand der Einrückung lesefreundlich verschiebt (--indent-heuristic, standardmäßig aktiv).

Patience: zuerst die eindeutigen Zeilen abgleichen

Patience diff wurde von Bram Cohen vorgeschlagen. Zuerst sucht es Zeilen, die in beiden Dateien jeweils genau einmal vorkommen, denn eine eindeutige Zeile wie die Funktionsdeklaration int h() { hat einen klaren Partner. Aus diesen eindeutigen Zeilen wählt es die längste Liste in passender Reihenfolge (längste aufsteigende Teilfolge) als Ankerpunkte und vergleicht nur die kleinen Abschnitte zwischen den Ankern erneut.

• Vorteil: Es lässt sich nicht von häufigen Zeilen wie } oder Leerzeilen in die Irre führen, sodass Änderungen an Funktionen oder Absätzen als zusammenhängende Blöcke erscheinen.
• Nachteil: Bei Eingaben mit kaum eindeutigen Zeilen (Daten mit sich wiederholenden Zeilen, Logs) findet es keine Anker. Dann unterscheidet es sich kaum von einem gewöhnlichen diff oder fasst Änderungen sogar zu großen Blöcken zusammen.

Histogram: selten vorkommende Zeilen zuerst

Der histogram-Algorithmus wurde in JGit (einer in Java geschriebenen git-Implementierung) entwickelt und später in git übernommen. Während patience nur „genau einmal vorkommende Zeilen“ betrachtet, zählt histogram, wie oft jede Zeile vorkommt, und wählt die seltensten als Ankerpunkte. So kann es auch ohne eindeutige Zeilen relativ seltene Zeilen als Anker verwenden. Die git-Dokumentation beschreibt das als Erweiterung des patience-Algorithmus, die „selten vorkommende gemeinsame Elemente unterstützt“. In der Praxis liefert es oft ähnlich wie patience Ergebnisse, die die Struktur des Codes gut erhalten.

Was soll man verwenden?

• Alltägliche Code-Reviews: Der Standard reicht aus. Wirkt ein Ergebnis seltsam zerschnitten, sehen Sie es sich mit --histogram noch einmal an.
• Große Refactorings, bei denen Funktionen verschoben oder mehrere hinzugefügt werden: --histogram oder --patience halten Blöcke besser zusammen.
• Wenn die Zahl der geänderten Zeilen exakt minimal sein muss: --minimal.
• Datendateien mit vielen Wiederholungen: Sortieren und Normalisieren kann wichtiger sein als der Algorithmus. Für JSON siehe JSON vergleichen.

Egal welcher Algorithmus verwendet wird: Die daraus wiederhergestellte Datei ist dieselbe. Anders ist nur, wie das Ergebnis für Menschen aussieht.

In diesem Werkzeug

Diese Seite vergleicht Zeilen mit einem Algorithmus der Myers-Familie, paart dann inhaltlich ähnliche geänderte Zeilen als „geändert“ und vergleicht ihren Inhalt erneut. Selbst wenn das zeilenweise Ergebnis etwas ungeschickt zerschnitten ist, sehen Sie deshalb sofort, welches Wort sich geändert hat. Fügen Sie das Beispiel oben in den Textvergleich ein und vergleichen Sie die Darstellung in der vereinheitlichten und der geteilten Ansicht. Wie man das Ergebnis liest, erklärt Unified Diff lesen.

Zum Textvergleich