How Diff Algorithms Work
When you compare two files, the tool has to decide which lines are the same, which are new and which disappeared. That sounds obvious to a human, but a computer needs a precise rule. The rule almost every diff tool uses is beautifully simple to state and surprisingly deep to implement: find the longest sequence of lines the two files share, and describe everything else as an insertion or a deletion.
The longest common subsequence
The heart of a diff is the Longest Common Subsequence, or LCS. A subsequence keeps the original order but is allowed to skip items, so the LCS of the two files is the largest set of lines that appear, in the same order, in both. Anything in the old file that is not part of the LCS must have been deleted; anything in the new file that is not part of it must have been added. That single insight turns a fuzzy comparison into a concrete calculation.
A textbook LCS uses dynamic programming: a table where each cell reuses the answers to smaller sub-problems. It is correct and easy to understand, but it needs memory proportional to the two lengths multiplied together, which is too much for large files. That cost is exactly why real tools reach for something smarter.
The Myers algorithm
In 1986 Eugene Myers published the algorithm that most modern tools, including Git, still use. It reframes the problem as finding the shortest path through an edit graph — a grid where moving diagonally means a line matched, moving right means a deletion and moving down means an insertion. The fewer non-diagonal moves the path takes, the smaller the diff. Myers finds that shortest path in time proportional to the file size times the number of differences, so when two files are nearly identical it is extremely fast.
This focus on the number of differences is the key to performance. Most edits change a handful of lines in a large file, and Myers does work in proportion to that handful, not to the whole document. DiffScope builds on the same family of algorithms, which is why it stays responsive even on long files.
Why one change has many valid diffs
A minimal edit script is rarely the only minimal edit script. If you add a function that ends the way the previous one did — a closing brace, then a blank line — the algorithm can attribute that shared closing brace to either function and still produce a diff of exactly the same size. Apply either version and the resulting file is byte-identical, so both are correct; they simply read very differently to a human.
That is why diff tools layer heuristics on top of the mathematics. Git’s indent heuristic, on by default since version 2.14, slides an ambiguous hunk boundary up or down so that it lands where the indentation suggests a block really begins, turning a confusing split-brace diff into a plain “a new function was added”. The patch itself does not change — only where the tool chose to draw the edge.
Patience and histogram diffs
Minimising the number of edits is not the same as matching the right lines. Myers will happily pair the closing brace of one function with the closing brace of a completely unrelated one if that shortens the edit script, and the result is a diff that interleaves two blocks which have nothing to do with each other. Patience diff, devised by Bram Cohen, changes the matching rule: it first finds the lines that occur exactly once on each side, takes the longest increasing run of those unique lines as anchors, and only then diffs the regions between them. A line that appears once is far more likely to be a genuine counterpart than a brace that appears two hundred times.
Histogram diff is Git’s refinement of the same idea. It builds an occurrence table for the lines of a file and splits on the least common shared line instead of insisting on strict uniqueness, so it still finds useful anchors in files that have no unique lines at all, and in practice it runs faster. Either one can be selected with --diff-algorithm=patience or --diff-algorithm=histogram, or set once as diff.algorithm in your config. When the diff of a reorganised file looks nonsensical, try them before concluding that the change itself is strange.
From lines to words
Line-level diffing is the right first pass, but it is coarse: change one character and the whole line is marked removed and re-added. To fix that, a diff tool runs the same algorithm a second time at a finer grain. When it sees a removed line immediately followed by an added line, it treats them as a modified pair and diffs them word by word, so only the parts that actually changed light up.
The result is the layered highlighting you see in a good review tool: red and green for whole lines that appeared or vanished, and a sharper accent inside a modified line for the exact words that differ. Paste two versions into DiffScope and you can watch both layers at once.
The takeaway
A diff finds the longest run of shared lines and calls the rest insertions or deletions. The Myers algorithm makes that fast by working in proportion to the number of changes — and a second word-level pass shows exactly what moved inside each edited line.
Open the tool and try it now
More guides
Line Diff vs Word Diff: When to Use Each
The same change can be shown as whole swapped lines or as a few highlighted words. Here's why both granularities exist and when each one is clearer.
Reading a Git Diff Without the Guesswork
Those @@ headers and +/- lines look cryptic until you know the pattern. Here's how to read a unified diff line by line and never lose your place.
Comparing Config Files Safely
Config drift causes real outages. Here's how to diff configuration files so you catch the meaningful change without leaking secrets or drowning in noise.