Diff Algorithm Choice and the Noise It Adds to a Review

The previous treatment of the unified diff read it as a fixed artifact whose losses are inherent to a line-oriented model. There is a second source of loss, and it is a design choice rather than a property of the format: which of the many valid edit scripts gets printed. A diff is defined by a longest common subsequence, but the longest common subsequence between two files is frequently not unique, and the tie-breaking rule decides what the reviewer sees. Two implementations can report the same set of changed lines and still present wildly different hunks, because they attribute different lines to “context” and different lines to “change”.

The visible consequence is that the same commit, viewed through two tools, can look like a clean three-line edit in one and a 400-line rewrite in the other. Neither is wrong. One is merely more useful for review, and understanding which property makes it useful requires looking at how the subsequence is chosen.

The minimum edit script and its bias

Myers’s algorithm computes a shortest edit script: the minimum number of deletions plus insertions that transforms one sequence into the other. It runs in time proportional to the edit distance times the input size, which is fast when the files are similar and degrades toward quadratic when they are not. The classic implementation refines the result with a divide-and-conquer step that finds the middle snake, and that step is where the presentation bias enters.

The recursion splits the edit graph in half at the point where the forward and backward searches meet. Any point on the optimal path is valid; implementations choose the first one found, typically biased toward the front of the file. Consider a function that is duplicated, with the second copy edited. Both “match the first copy and show the edit in the second” and “match the second copy and show the edit in the first” are minimal edit scripts, because either way one copy is deleted and one is inserted. Myers as commonly implemented prefers the earlier match, so the diff shows the first copy as unchanged and the second copy as rewritten, the opposite of what a reader knows happened. The diff is minimal and it is misleading.

A second bias is that minimum edit script is not the same as maximum readability. Moving a block of twenty lines upward by ten lines is a small semantic edit. The minimal script for it is twenty deletions and twenty insertions, with the block appearing twice, unless the algorithm happens to match the block across the shift, which depends on whether the intervening lines create a competing match. In large files with repeated boilerplate, the minimum script can fragment a single move into several scattered hunks.

There is a further cost in time. The greedy variant is bounded, but pathological inputs, such as a file and its reverse or two files that share almost nothing, push the search toward its worst case, and implementations cap the effort, falling back to a coarser result when the limit is hit. That fallback is invisible in the output: the diff is still a valid edit script, just not the minimal one, and it may contain large blocks reported as changed when a better script existed.

Patience: anchoring on unique lines

Patience diff takes a different route. It finds lines that occur exactly once in each file, computes the longest increasing subsequence of those unique-line matches, and treats the result as fixed anchors. Between consecutive anchors it recurses with the same rule; when a region contains no unique lines on both sides, it falls back to the ordinary algorithm.

The effect on review is substantial for the cases that matter. Because anchors are unique lines, they cannot be confused with their duplicates, so the “which copy was edited” problem disappears: the unique surrounding code pins the diff to the right location. Boilerplate such as a brace, a blank line, or an import that appears forty times is never an anchor, so it cannot drag the alignment. The classic pathology that patience fixes is a file consisting of many similar blocks, such as a list of data definitions or a sequence of near-identical case arms, where a conventional diff aligns the wrong pairs and reports an entire region as rewritten.

The cost is that patience can produce a longer edit script than the minimum. By refusing to use a duplicated line as an anchor, it sometimes declines a match that the optimal script would take, and the resulting diff contains more changed lines. It is therefore not a better diff by the metric Myers optimises; it is better by a different metric: the fraction of changed lines that a human would agree are changed. For review, that second metric is the one that matters, because the reviewer’s cost is per changed line and the reviewer’s error rate rises with lines that are not really changes.

Histogram and the sibling of patience

Histogram diff uses a related anchoring idea with a different frequency rule: it selects the line with the lowest occurrence count in the remaining region, preferring low-frequency lines even when they are not strictly unique, and recurses on both sides. In practice it behaves like patience on files with unique anchors and better on files without them, because it degrades to progressively more frequent lines instead of jumping straight to the generic algorithm.

Git’s default strategy has changed over its history and the selection is configurable per repository and per invocation, which means the diff a reviewer sees can depend on configuration rather than on the change. A commit reviewed under one setting and re-displayed under another shows different hunks for identical content, and inline comments anchored to positions in the first rendering do not necessarily line up in the second. This is a mundane operational problem that becomes acute during a rebase: the same logical change re-rendered after conflict resolution may present entirely different hunk boundaries.

What each strategy is good for

The strategies differ along a single axis: how much they are willing to trade optimality for stability of the presented structure.

Strategy	Optimises	Strength	Weakness
Myers (default)	Minimum edit script	Smallest diffs; fast on similar files	Misaligns duplicates; fragments moves
Patience	Unique-line anchoring	Correct attribution in repetitive files	Longer scripts; slower on large inputs
Histogram	Low-frequency anchoring	Graceful degradation without unique lines	Not guaranteed minimal; less predictable

The choice is not about correctness of patch application, since all three produce valid patches, but about how much interpretation the reviewer must supply. A diff that reports a block as moved when it was moved lets the reader confirm in one glance; a diff that reports the same block as deleted in one place and inserted in another forces a comparison the reader performs by hand, and hand comparisons are where reviewers make mistakes.

Rename and copy detection sit outside the line algorithm

Even the best line-level script cannot say that a file was renamed or a function was copied, because the hunk format has no vocabulary for it. Git adds that vocabulary in the header, by comparing the content of deleted and added files and declaring a rename when similarity exceeds a threshold. The similarity measure is a ratio of matched bytes to total bytes, and the threshold is configurable; the default sits at one half, meaning that a file which kept half its content counts as a rename.

The threshold is a knob with two failure directions. Set it too high and genuine renames of heavily edited files fall back to delete-plus-add, flooding the review with code the reader has already seen in another form. Set it too low and unrelated files with common boilerplate, such as two similar service skeletons or two license headers over different content, are declared renames, which suppresses review of the added file entirely because the tool presents it as “renamed from” with a small diff. Both failures are silent. Nothing in the output marks the classification as a guess.

The practical consequence for a review process is that file-level moves and large-scale reorganisations are better reviewed with rename detection made explicit and with the file list inspected separately from the hunks. The hunks tell the reader what changed within files; only the header block tells them what happened to files.

Practical consequence for reading a diff

Three habits follow from the mechanics rather than from taste. First, when a hunk looks implausibly large for the described change, suspect the alignment before suspecting the author: re-run the comparison with a different algorithm and compare hunk counts. Second, when the change is a move or a reorganisation, read the file list and the rename markers first, because the hunks are the least informative view of that class of change. Third, when a hunk boundary sits somewhere arbitrary, that is usually the algorithm’s recursion point showing through, not a signal about the author’s editing process.

The next question is what a reviewer should do with a diff once it is rendered faithfully: how a change gets partitioned into units that can be reviewed one at a time, which is the decomposition problem and is a matter of intent rather than of file layout.