Two files, one question: what changed? It sounds like something you could answer by walking both files in step and stopping at the first mismatch. That approach falls apart on the first inserted line, because everything after it looks different even though nothing after it was touched.
The Problem Is Finding the Shortest Story
A diff has to choose between explanations. If a line vanishes from the middle of a file, one explanation is that a single line was deleted. Another is that every line from that point down was replaced with the line below it. Both explanations produce the same result, and only the first is useful.
So diff algorithms optimise for the shortest edit script: the fewest insertions and deletions that turn version A into version B. That is the same as finding the longest common subsequence of the two files, the longest set of lines that appear in both, in the same order, without needing to be adjacent. Every line outside that subsequence is an edit.
The classic dynamic programming solution for a longest common subsequence fills an N by M grid, which costs time and memory proportional to the product of the two file lengths. Two files of 10,000 lines each would mean 100 million cells. That is why the algorithms that actually ship are all attacks on the same problem from cheaper angles.
The Algorithms Behind the Tools You Use
All five answer the same question. They differ in how much they cost and in which of several equally short answers they pick.
| Algorithm | Published | Where you meet it |
|---|---|---|
| Hunt-McIlroy | 1976 | The original Unix diff, Bell Labs technical report #41 |
| Myers greedy | 1986 | GNU diff, Git's default, the checker on this site |
| Myers linear space | 1986 | The same result on large files without the memory |
| Patience | 2006 | git diff --patience, originally Bazaar |
| Histogram | 2011 | git diff --diff-algorithm=histogram, JGit's default |
What Myers Actually Does
Eugene Myers published "An O(ND) Difference Algorithm and Its Variations" in Algorithmica in 1986, and it remains the algorithm most diffs run. Its insight is that the cost should scale with how different the files are, not with how big they are. N is the combined length, D is the number of edits, and the running time is proportional to N times D.
The trick is to stop thinking about a grid and start thinking about a path. Picture version A along the top edge and version B down the side. Moving diagonally means the next line matches on both sides and costs nothing. Moving right deletes a line, moving down inserts one, and each costs one. The shortest edit script is the cheapest path from the top left corner to the bottom right.
Myers walks outward one edit at a time, tracking only the furthest point reachable for each edit count, and following every free diagonal as far as it goes before spending anything. The first time a path reaches the far corner, the number of edits it took is the answer, and the recorded path is the edit script. For two versions of the same document, where D is small, this finishes almost instantly no matter how long the files are.
One consequence is worth knowing: trimming the identical run at the start and the identical run at the end before doing any of this costs one pass and usually removes most of the input. Every practical implementation does it, including this one.
How this checker lines up a rewritten line
Myers reports a rewritten line as a deletion and an insertion, because that is what it is. To show it as one edit, a removed line and an added line in the same position are diffed again at word level, and the word highlighting is kept only if the two still share at least 30% of their text. Below that they are genuinely different lines, and highlighting the fragments they happen to share hides the change instead of showing it.
The Shortest Diff Is Not Always the Clearest
Add a function to a source file and the diff often attributes the new closing brace to your function and the old one to the function above it. The edit script is correct and minimal. It is also aligned in a way no human would choose, because a closing brace on its own line matches any other closing brace, and the algorithm has no reason to prefer one over another.
Bram Cohen's patience diff, written for Bazaar in 2006, attacks this by anchoring on rarity. It first finds the lines that appear exactly once in both versions, which tend to be the meaningful ones such as a function signature, then treats those as fixed points and recurses into the regions between them. Common filler like a blank line or a lone brace never gets to anchor anything. The histogram algorithm, added to Git in 2011 and used by default in JGit, extends the same idea by ranking lines by how often they occur and aligning the rarest first.
Git still defaults to Myers. A 2019 study in Empirical Software Engineering compared the algorithms across a large sample of real commits and found the output identical for the overwhelming majority of them, which is a reasonable argument against changing a default that millions of tools depend on. Where the two disagree, histogram usually reads better. If you review code and have never touched the setting, git config --global diff.algorithm histogram is a one-line change worth trying.
Four Things That Make a Diff Noisier Than the Change
Most of the time a diff looks wrong, the algorithm is right and the input is carrying differences nobody meant to make.
Line endings
A file saved on Windows ends its lines with a carriage return and a line feed. The same file saved on macOS or Linux uses a line feed alone. To a byte-comparing tool every single line has changed. This checker reads all three conventions as a line break, so a cross-platform save is invisible.
Reformatting mixed in with edits
Re-indenting a block, or a formatter reflowing it, rewrites lines that mean exactly what they meant before. That is what the ignore-whitespace option is for: it trims each line and treats any run of spaces or tabs as one space before matching, so only real edits survive.
Prose that has no line structure
An article usually arrives as a few enormous lines, one per paragraph. Comparing by line then marks a whole paragraph as changed because one word moved. Comparing by word ignores line boundaries and marks the words themselves, which is the right granularity for drafts.
Characters you cannot see
A non-breaking space pasted from a web page, a curly quote substituted by a word processor, or a zero-width space carried in from a CMS all count as different characters. If two lines look identical and still diff, character mode will point at the culprit.
Compare two versions now
Side by side or unified, by line, word or character.
Reading a Unified Diff
The side-by-side view is easier to read, but the format you will meet in code review, mailing lists and patch files is unified diff, and it is worth being able to read one without a tool.
Two header lines name the versions, one marked with three minus signs and one with three plus signs. After that, each changed region is a hunk introduced by a line of the form @@ -12,7 +12,9 @@, meaning the region starts at line 12 of the original and covers 7 lines there, and starts at line 12 of the new version and covers 9 lines there. Inside the hunk, a line beginning with a minus sign was removed, a plus sign means added, and a space means it is context shown so you can see where you are.
Context is conventionally three lines on each side of a change, which is where the collapsed sections in this tool get their size. It is enough to locate a hunk in a file you know, and it is why a one-line change usually shows as seven lines of patch.
Frequently Asked Questions
Related Tools
Keep Reading
Word Count Targets: What Editors, Platforms and Google Expect
Two counters can disagree by five percent on the same paragraph. Here is how counting actually works, and the targets worth writing to.
JSON Errors Explained: Trailing Commas, NaN and Other Rejections
Why valid-looking JSON fails to parse, how to read a parser's error position, and the number precision bug that silently corrupts large IDs.
camelCase, snake_case, kebab-case: Which Case Goes Where
The convention each language expects, the one language where capitalisation changes behaviour, and why acronyms break every rule.
Why Character Counts Disagree: Emoji, Accents and SMS Segments
One emoji can cost seven characters, and a single curly apostrophe can triple your SMS bill. The three definitions of a character, and when each applies.