Git-Diff-Algorithmen im Vergleich: Myers, Patience, Histogram

1. Warum der gewählte Diff-Algorithmus überhaupt einen Unterschied macht

Ein Diff zwischen zwei Dateiversionen ist mathematisch betrachtet nie eindeutig: Es gibt fast immer mehrere gültige Wege, eine Datei in eine andere zu überführen, und ein Diff-Algorithmus muss sich für einen davon entscheiden. Genau darin unterscheiden sich die in Git verfügbaren Algorithmen, sie optimieren unterschiedliche Kriterien und erzeugen dadurch bei identischem Ausgangsmaterial teils sehr verschiedene, aber jeweils technisch korrekte Diffs.

Für ein Review ist das keineswegs nur eine akademische Feinheit: Ein Diff, der eine verschobene Funktion als vollständiges Löschen und Neuhinzufügen darstellt, kostet einen Reviewer deutlich mehr Zeit und Aufmerksamkeit als ein Diff, der dieselbe Funktion klar als unverändert verschobenen Block erkennt und nur die tatsächlich geänderten Zeilen daneben markiert.

2. Myers-Algorithmus: Git-Standard und seine Funktionsweise

Der Myers-Algorithmus ist der Standardalgorithmus in Git und basiert auf der Suche nach der längsten gemeinsamen Teilfolge zweier Zeilenlisten, kurz LCS. Er berechnet die kürzestmögliche Bearbeitungssequenz aus Einfüge- und Löschoperationen, die eine Datei in die andere überführt, und ist dabei mathematisch nachweisbar optimal in Bezug auf die Anzahl der erzeugten Diff-Zeilen.

Genau diese Optimierung auf minimale Zeilenzahl kann jedoch zu unerwarteten Ergebnissen führen: Der Algorithmus kennt keinen Begriff von semantischer Bedeutung und kann daher zufällig passende, aber inhaltlich völlig unabhängige Zeilen als zusammengehörig interpretieren, etwa eine schließende geschweifte Klammer, die an vielen Stellen einer Datei identisch aussieht.

# Myers ist der Standard, muss also nicht explizit angegeben werden
git diff --diff-algorithm=myers

3. Patience Diff: eindeutige gemeinsame Zeilen als Anker

Patience Diff verfolgt eine andere Strategie: Es sucht zunächst gezielt nach Zeilen, die in beiden Dateiversionen jeweils genau einmal vorkommen, und nutzt diese eindeutigen Zeilen als feste Ankerpunkte. Zwischen zwei aufeinanderfolgenden Ankern wird der Diff rekursiv erneut berechnet, wodurch sich der Algorithmus deutlich stärker an eindeutigen Strukturmerkmalen des Codes orientiert als der rein zeilenbasierte Myers-Algorithmus.

Dieser Ansatz zahlt sich besonders bei verschobenen Codeblöcken aus: Eine eindeutige Funktionssignatur oder ein charakteristischer Kommentar dient als verlässlicher Ankerpunkt, wodurch der gesamte dazwischenliegende Block eher als zusammenhängende Verschiebung erkannt wird, statt in viele kleine, verwirrende Einzeländerungen zerlegt zu werden.

git diff --diff-algorithm=patience

4. Histogram Diff: Weiterentwicklung von Patience mit besserer Performance

Histogram Diff baut konzeptionell auf der Idee von Patience Diff auf, verwendet zur Suche nach eindeutigen Ankerzeilen aber eine Häufigkeitstabelle, ein sogenanntes Histogramm, statt einer aufwendigeren Suche nach der längsten gemeinsamen Teilfolge an jeder Stelle. Dadurch bleibt das grundlegende Verhalten dem von Patience Diff sehr ähnlich, die Berechnung selbst läuft aber in der Praxis merklich schneller ab.

Wegen dieser Kombination aus patience-ähnlicher Ergebnisqualität und besserer Performance ist Histogram in vielen Projekten inzwischen die bevorzugte Alternative zum Myers-Standard, auch außerhalb von Git: Andere Werkzeuge wie JGit verwenden Histogram bereits standardmäßig, weil es bei realistischen Codeänderungen einen guten Kompromiss zwischen Lesbarkeit und Rechenaufwand darstellt.

git diff --diff-algorithm=histogram

5. Der Minimal-Algorithmus und wann er sinnvoll ist

Der Minimal-Algorithmus ist im Kern eine Variante des Myers-Algorithmus, die zusätzlichen Rechenaufwand investiert, um die absolut kürzestmögliche Diff-Ausgabe zu garantieren, selbst wenn der reguläre Myers-Algorithmus aus Performancegründen bereits vorher eine nahezu optimale, aber nicht ganz minimale Lösung akzeptiert hätte.

In der Praxis lohnt sich Minimal vor allem bei sehr kleinen, aber kritischen Diffs, etwa bei automatisiert generierten Patches, die anschließend maschinell weiterverarbeitet werden und bei denen jede überflüssige Diff-Zeile echten Mehraufwand verursacht. Für den alltäglichen Review-Einsatz bringt Minimal gegenüber Myers dagegen selten einen spürbaren Unterschied.

git diff --diff-algorithm=minimal

6. Diff-Algorithmus gezielt pro Aufruf wählen

Für einen einmaligen Test lässt sich der Algorithmus direkt über die Kommandozeilenoption --diff-algorithm bei jedem einzelnen Aufruf von git diff, git show oder git log -p festlegen, ohne die dauerhafte Konfiguration zu verändern. Das eignet sich gut, um bei einem verwirrenden Diff schnell auszuprobieren, ob ein anderer Algorithmus ein klareres Bild liefert.

Gerade bei umfangreichen Refactorings, bei denen ganze Methoden oder Klassen innerhalb einer Datei verschoben wurden, lohnt sich dieser schnelle Vergleich fast immer: Ein Wechsel von Myers zu Histogram macht in solchen Fällen häufig den Unterschied zwischen einem unlesbaren Wust aus Löschungen und Einfügungen und einem klar erkennbaren, verschobenen Block.

# Bei einem unklaren Diff schnell einen anderen Algorithmus ausprobieren
git diff --diff-algorithm=histogram HEAD~1

7. Algorithmus dauerhaft konfigurieren

Statt den Algorithmus bei jedem Aufruf erneut anzugeben, lässt sich über git config diff.algorithm ein Standardwert für das gesamte Repository oder global für alle Repositories eines Nutzers hinterlegen. Viele Teams setzen dabei inzwischen histogram als neuen Standardwert, weil es in der Praxis selten schlechtere Ergebnisse als Myers liefert und bei verschobenem Code klar überlegen ist.

Diese Einstellung wirkt sich auch auf Werkzeuge aus, die intern auf git diff zurückgreifen, etwa viele grafische Git-Clients und IDE-Integrationen, sofern diese die Git-Konfiguration korrekt respektieren und keinen eigenen, fest verdrahteten Diff-Algorithmus mitbringen.

# Histogram als dauerhaften Standard für dieses Repository setzen
git config diff.algorithm histogram

# Oder global für alle Repositories des aktuellen Nutzers
git config --global diff.algorithm histogram

8. Indent-Heuristik als Ergänzung zum Algorithmus

Unabhängig vom gewählten Algorithmus setzt Git standardmäßig zusätzlich eine sogenannte Indent-Heuristik ein, die Diff-Grenzen bevorzugt an Zeilen mit geringerer Einrückung ausrichtet, etwa am Ende eines Blocks statt mitten in einer Bedingung. Das führt in der Praxis häufig zu intuitiveren Diffs, weil Klammern und Blockgrenzen eher zusammen bleiben, statt willkürlich mitten im Code aufzureißen.

Die Heuristik ist seit einigen Git-Versionen standardmäßig aktiviert und lässt sich über diff.indentHeuristic bei Bedarf gezielt deaktivieren, was aber in der Praxis nur selten sinnvoll ist. Sie arbeitet unabhängig vom gewählten Diff-Algorithmus als zusätzlicher Nachbearbeitungsschritt, kombiniert sich also mit Myers ebenso wie mit Histogram oder Patience.

# Indent-Heuristik explizit deaktivieren, standardmäßig ist sie aktiv
git config diff.indentHeuristic false

9. Praxisbeispiel: verschobene Funktion und wie sich die Algorithmen unterscheiden

Wird eine Hilfsfunktion innerhalb einer Datei nach unten verschoben und gleichzeitig eine neue Funktion an ihre alte Stelle geschrieben, interpretiert Myers das Ergebnis oft als eine Reihe verschachtelter Löschungen und Einfügungen quer über die gesamte Datei, weil der Algorithmus rein auf minimale Zeilenzahl optimiert, ohne semantisches Verständnis für zusammengehörige Blöcke.

Patience und Histogram erkennen dagegen anhand eindeutiger Zeilen wie der Funktionssignatur meist zuverlässig, dass es sich um eine reine Verschiebung handelt, und stellen die verschobene Funktion als unverändert dar, während nur die tatsächlich neue Funktion als Einfügung markiert wird. Bei Codeänderungen mit vielen wiederholten, generischen Zeilen, etwa kurzen schließenden Klammern, liefert Myers dagegen manchmal überraschend kompaktere Ergebnisse als die anderen Algorithmen.

10. Zusammenfassung

11. FAQ: Diff-Algorithmen