How Diff Chooses Changes and Why Git Has Several Algorithms
A diff result seems obvious until two versions contain repeated lines, reordered functions, or several equally plausible matches. The program cannot see the author's intent. It receives two sequences and must first decide which elements survived, then describe everything else as insertions and deletions.
That problem often has more than one minimum solution. Two edit scripts can contain the same number of operations, yet one keeps a new function together while another aligns braces and scatters the change across awkward hunks. Fast computation did not end the evolution of diff because edit count is only one concern; time, memory, stable alignment, and readability matter too.
Unix diff searched for the lines that survived
The diff utility entered Fifth Edition Unix in 1974. In July 1976, James Hunt and Douglas McIlroy published the Bell Labs report An Algorithm for Differential File Comparison, which explained how the program was engineered. It aimed to produce a minimum list of line changes that transformed one file into another without consuming memory proportional to the product of their lengths on ordinary inputs.
Its central problem was the longest common subsequence, or LCS. Once the longest sequence of lines appearing in the same order in both files has been selected, those lines can remain while the rest are represented as insertions and deletions. LCS length is directly related to the size of a shortest edit script when a replacement counts as one deletion followed by one insertion.
The Hunt and McIlroy algorithm did not fill the straightforward dynamic-programming rectangle described in the old version of this article. It gained practical efficiency by selecting candidate matches, hashing lines, sorting them into equivalence classes, and merging candidates with binary search. The report observed behavior close to the sum of file lengths on normal document revisions, while acknowledging a product-of-lengths worst case. Repeated lines created especially many possible correspondences and remained difficult input.
Myers connected LCS to a shortest path
In 1986, Eugene Myers published An O(ND) Difference Algorithm and Its Variations, expressing LCS and shortest edit script as two views of a path through an edit graph. One axis contains the first sequence and the other the second. A horizontal edge is a deletion, a vertical edge is an insertion, and a cost-free diagonal edge is available when the two elements match.
The algorithm considers paths with zero edits, then one, two, and so on until a path reaches the end of both sequences. On each diagonal it only needs to retain the furthest position reached because a path that arrived earlier cannot offer an advantage. After every edit, it follows the longest possible run of diagonal matches, commonly called a snake.
In the paper's notation, N is the sum of the two sequence lengths and D is the length of a minimum insertion-and-deletion script. The basic algorithm takes O(ND) time, which suits similar files because D is usually far smaller than N for a modest commit. Myers also described a linear-space refinement and derived O(N + D²) expected time under the paper's stochastic model.
A shortest path gives a minimum operation count but not always a unique placement for those operations. Repeated elements let different diagonal matches produce different hunk boundaries and different stories for the reader. An alignment can be optimal in D and still be the less intelligible explanation of a change.
What default diff means in Git
The current Git documentation describes default and myers as the basic greedy diff and still lists it as the default. That establishes a lineage from Myers; it does not mean Git contains nearly untouched 1986 code. Its modern implementation lives in the xdiff subsystem, works on prepared lines, and participates in a much wider output pipeline.
Several decisions can change the result even when the named algorithm stays the same. Git defines line boundaries, can invoke custom diff drivers, formats hunks, and enables an indent heuristic that shifts hunk boundaries towards more readable locations. Rename detection, word diff, and moved-line coloring happen at other stages rather than becoming properties of Myers itself.
The minimal mode remains close to the default path but spends additional time to ensure the smallest possible diff. It is useful when edit count matters more than speed, although fewer operations do not necessarily explain a refactoring more clearly.
Patience and histogram choose different anchors
Patience diff begins with common lines that occur exactly once on each side and uses them as unambiguous alignment points. It then compares the ranges between those anchors separately. In source code, this can prevent repeated blank lines, braces, or boilerplate calls from being chosen as the main matches, so a moved block often remains visually coherent.
The approach has limits. Not every region contains unique lines, and its selected anchors do not promise a globally minimum edit script. Patience is better understood as an alternative alignment strategy that is often easier to read, not as an algorithm guaranteed to win every refactoring.
Git describes histogram as an extension of patience that supports low-occurrence common elements in addition to strictly unique ones. That supplies more meaningful anchors when few lines are truly unique. Results still depend on the file, so Git exposes --diff-algorithm=myers|minimal|patience|histogram and the diff.algorithm configuration rather than declaring one permanent choice for all content.
Tokenization comes before the diff
A diff algorithm does not compare abstract text. It compares a sequence of tokens. A line is the usual token for a patch, but the same method can align words, characters, sentences, or array elements. Granularity changes both N, D, and the meaning of the output: line mode suits code, word mode explains an edited sentence, and character mode exposes a single changed mark in a short string.
The alignment then needs a presentation. Unified output with --- and +++ file headers and @@ hunk markers is a format, not a different LCS algorithm. The same internal changes can appear as one patch stream, two columns, or highlighted spans inside a line.
How Text Diff works
The Text Diff loads jsdiff 7.0.0 and performs the comparison in the browser; the entered texts are not uploaded. The jsdiff library is based on the Myers paper. It tokenizes each input at the requested granularity and finds a minimum set of single-token insertions and deletions.
Lines mode treats each complete line as a token and renders one colored list with line numbers. Words and Chars show inline changes at word or character granularity. Statistics count added, removed, and unchanged units in the current mode, so those numbers refer to lines only while Lines is selected. The inputs sit in two columns, but the diff result itself is not a side-by-side table.
Ignore whitespace also behaves differently by mode. Lines passes the option to diffLines; Words and Chars first collapse runs of spaces and tabs. Copy unified diff always builds a fresh patch from the complete original texts with createTwoFilesPatch, regardless of the on-screen mode. Whitespace ignoring affects that copied patch only when Lines is active.
The copied output includes familiar ---, +++, and @@ markers, but the tool does not reproduce Git's complete processing pipeline. It has no repository context, custom diff drivers, rename detection, indent heuristic, patience, or histogram mode. It is a local comparison of two texts that can produce ordinary unified output, not a browser implementation of every stage in git diff.
Related tools
Frequently asked questions
Who created Unix diff?
The diff utility appeared in Fifth Edition Unix in 1974. James Hunt and Douglas McIlroy documented its practical algorithm in a 1976 Bell Labs technical report. It found a longest common subsequence of lines, but selected candidate matches and used hashing, equivalence-class sorting, and binary search to make real files tractable.
What did the Myers algorithm change?
Eugene Myers represented the problem as a shortest-path search through an edit graph in 1986. If N is the combined sequence length and D is the minimum number of insertions and deletions, the basic algorithm takes O(ND) time. It is consequently efficient for similar files where D is much smaller than N.
Which algorithm does git diff use by default?
Current Git documentation calls default and myers the basic greedy diff and lists it as the default. Actual output also depends on configuration, tokenization, and the default indent heuristic that shifts hunk boundaries for readability. Git is based on the Myers family of ideas, not an untouched copy of the 1986 paper.
How do minimal, patience, and histogram differ in Git?
Minimal spends extra time to produce the smallest possible diff. Patience uses common lines that occur once on each side as stable alignment points, which can help with moved blocks and repetitive syntax. Histogram extends that idea to low-occurrence common lines. No mode produces the clearest result for every file.
Which modes does Text Diff provide?
The tool compares lines, words, or characters with jsdiff 7.0.0, which is based on the Myers algorithm. Its display is one colored change stream with statistics in the unit of the selected mode. A separate button creates unified output with ---, +++, and @@ headers from the original texts, independently of the on-screen granularity.
