On March 30, 2010, BitTorrent creator Bram Cohen published a short note explaining how patience diff avoids misleading line matches. When you edit a source code file by adding a new function at the beginning and removing an obsolete one from the end, standard diff tools can produce confusing alignments. Instead of showing one clean insertion and one deletion, the comparison algorithm aligns isolated closing braces and blank lines across entirely unrelated functions, making every surviving routine look mangled.
Git’s default diff algorithm is a variant of Eugene Myers’s algorithm, which finds a Longest Common Subsequence, or LCS. The goal of an LCS algorithm is purely numerical: find the longest matching sequence of lines between two texts so the generated patch contains the fewest total edits. To a mathematical solver, a closing curly brace on a line by itself is just as valid a match as a distinct function signature. When code blocks are reordered, matching these repetitive boilerplate lines produces patches that are technically minimal but visually incoherent to human reviewers.
When Braces Match Too Well
Cohen illustrated the breakdown with a simple sequence: imagine a file containing functions F1, F2, and F3 that is updated to become F4, F1, and F2. A developer looking at the change immediately sees that F4 was added to the top and F3 was dropped from the bottom, while F1 and F2 remained intact. An automated diff tool, however, compares lines without understanding program structure.
Because the functions share identical opening braces, closing braces, and blank separator lines, an LCS-based comparison can align the boilerplate lines of F1 with F4, F2 with F1, and F3 with F2. Instead of presenting one addition and one removal, the diff claims that every function in the file was altered. When developers attempt to merge concurrent changes to those same functions, these artificial misalignments can cause merge conflicts where a clean automatic merge was possible.
Anchoring on Distinctive Landmarks
Patience diff, the approach Cohen described, starts from a different premise: human readers do not treat all lines as equals. Lines like }, return;, or blank lines can recur many times in a single file. Unique shared lines, by contrast, are more likely to provide meaningful landmarks. A function declaration or an unusual variable initialization often appears exactly once in the entire file.
As James Coglan explains in his 2017 analysis, patience diff searches each region for lines that appear exactly once on each side. In Cohen’s revised 2010 procedure, the algorithm first matches identical lines at the beginning and end, then searches the remaining region for unique shared lines. Repeated lines are ignored during this initial search. By isolating these unique shared lines, the algorithm selects landmarks that are more likely to contain meaningful content than repeated punctuation.
Patience Sorting and Non-Crossing Matches
Finding unique lines on both sides is not enough on its own, because line order can change. If a function was moved from the bottom of a file to the top, connecting its unique lines to their counterparts would draw lines that cross other matches. For these pairs to form a common subsequence, their positions must increase in both documents.
To select the largest valid set of non-crossing anchors, patience diff borrows a technique from patience sorting, a card-game algorithm related to solitaire. After ordering the candidate pairs by their position in the original file, the algorithm finds the Longest Increasing Subsequence of their positions in the new file. This step discards crossing matches and leaves an ordered chain of landmark anchors that divides both files into smaller, independent sub-sections.
Heuristics, Fallbacks, and Real-World Limits
In his 2010 note, Cohen clarified an important practical boundary. While earlier descriptions explored recursively searching for unique lines within sub-sections, Cohen stated that he dropped the recursive pass because it was computationally costly and rarely discovered additional useful matches. In 2017, James Coglan published an implementation analysis describing patience diff as fundamentally a document partitioning heuristic rather than a standalone diff generator. When a sub-section between anchors contains no unique lines, the algorithm must fall back to a standard solver like Myers to compare the remaining text.
Git offers --patience as well as --histogram, an extension that accommodates common elements with low occurrence counts, while maintaining Myers as its default algorithm. Patience diff does not understand programming language syntax trees, and it does not guarantee the shortest edit script, which Git provides through the separate --minimal option.
Comparison algorithms work best when they recognize that not all lines carry equal weight. By prioritizing unique shared lines as landmarks, patience diff can produce clearer alignments even when the resulting edit script is not the shortest possible.
Related stories
Sources
- Patience Diff Advantages (Bram Cohen, March 30, 2010)
- Git Documentation: diff-options (git-scm.com)
- The patience diff algorithm (James Coglan, September 19, 2017)
- Implementing patience diff (James Coglan, September 28, 2017)
- Featured image: Colin; Wikimedia Commons; CC BY-SA 4.0 (adapted from the original)
SIGNAL TITANS
Leave a Reply