Comparing the same two files can give different results depending on the diff algorithm. All of them produce a "correct" diff, but they choose differently which lines to pair as equal, and that changes how easy the result is to read. git offers four through the --diff-algorithm option.
| Value | Description in the git docs | Characteristics |
|---|---|---|
myers (default) | The basic greedy diff algorithm; currently the default | Fast and usually close to minimal |
minimal | Spends extra time to make sure the smallest possible diff is produced | Always minimal; can be slow on large inputs |
patience | Uses the patience diff algorithm | Anchors on unique lines |
histogram | Extends patience to support low-occurrence common elements | Anchors on rare lines |
There are also short forms such as git diff --patience and git diff --histogram, and you can change the default with git config diff.algorithm histogram.
Myers: the default that finds a minimal edit
The Myers algorithm finds a path that minimizes the number of deletions and additions (see How diff works for the principle). The trouble comes when there are several choices for which lines to treat as equal. Code is full of very common lines such as }, {, blank lines, and return, so the algorithm can pair semantically unrelated lines and still have the same minimal number of edits.
The same change, two results
Suppose you insert a new function h between functions f and g, as below. Both of the following diffs have the same number of edits: 4 added lines.
@@ -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() {The first shows the new function as a whole, but the second treats the closing brace of the existing function f as the brace of the new function, so the addition is cut awkwardly. Shapes like this arise from the search order, and recent versions of git fix many of them with a heuristic that shifts the boundaries of changed blocks to more readable positions based on indentation (--indent-heuristic, on by default).
Patience: match unique lines first
Patience diff, proposed by Bram Cohen, first looks for lines that appear exactly once in each file. Unique lines, such as a function declaration int h() {, are certain to match. From these unique lines it picks the longest list that is in the same order on both sides (the longest increasing subsequence) as anchors, and then compares only the small regions between anchors again.
- Pros: it is not pulled around by common lines such as
}or blank lines, so changes to whole functions or paragraphs show up as blocks. - Cons: on input with few unique lines (data with repeated lines, logs), it cannot find anchors and is no different from an ordinary diff, or it may even lump things into large blocks.
Histogram: prefer rare lines
The histogram algorithm was developed in JGit (a git implementation written in Java) and later added to git. Whereas patience looks only at "lines that occur exactly once", histogram counts how often each line occurs and picks the least frequent lines as anchors. So even when there are no unique lines, it can anchor on relatively rare ones. The git documentation describes it as extending "the patience algorithm to support low-occurrence common elements". In practice, like patience, it often produces results that preserve the structure of code well.
Which one to use
- Everyday code review: the default is enough. If a result looks oddly split, view it again with
--histogram. - Large refactorings that move functions or add several at once:
--histogramor--patiencekeeps blocks together better. - When you need the exact minimal number of changed lines:
--minimal. - Data files with lots of repetition: sorting and normalization may matter more than the algorithm. For JSON, see Comparing JSON.
Whichever algorithm you use, applying the result reconstructs the same file. Only the shape a person reads changes.
In this tool
This site compares lines with a Myers-family algorithm, then pairs changed lines as "modified" based on how similar their contents are and compares inside those lines again. So even if the line-level result is split a little awkwardly, you can see right away which words changed. Put the example above into the Text Diff Checker and compare how it looks in unified and split views. How to read the result is covered in How to read a unified diff.