Diff Algorithms: How Git, VS Code, and Browsers Compare Text

Diff is one of the most-used algorithms in software — Git uses it for every commit, VS Code uses it for every save, browsers use it to render virtual DOM updates, AI coding tools use it to apply edits. Yet most developers have never thought about how it works. Here's the practitioner's tour.

The fundamental problem

Given two strings A and B, find the smallest set of insertions and deletions that transforms A into B. The output is a "diff" — a sequence of edit operations.

This is the Longest Common Subsequence (LCS) problem. Find the longest sequence of characters that appears in both — everything else is an insertion or deletion.

Why naive LCS is too slow

The dynamic programming LCS algorithm runs in O(M*N) where M and N are the lengths of the two strings. For two 10,000-line files, that's 100 million operations. Acceptable but slow.

Myers diff (1986) — the workhorse

Eugene Myers' 1986 algorithm runs in O((M+N)D) where D is the size of the difference. For files that are mostly the same with small changes, D is tiny — making the algorithm essentially linear.

Myers diff is what:

• Git uses by default
• diff and diff -u use
• Most languages' standard library uses

The trick: instead of computing every cell of the M*N grid, Myers walks diagonals greedily, finding the shortest "edit script" by exploring only the regions where the strings actually differ.

Patience diff (2008)

Bram Cohen (BitTorrent) noticed that Myers diff sometimes produces ugly diffs — it can match unrelated common lines (like blank lines or closing braces) producing nonsensical alignment.

Patience diff:

1. Find lines that appear exactly once in both files
2. Use those as anchor points
3. Recursively apply Myers between anchors

Result: human-friendly diffs that align "real" changes correctly. Git supports it via diff.algorithm = patience.

Histogram diff (2010)

Histogram diff is a refinement of patience that uses line frequency. Lines that appear once are best anchors; lines that appear many times are noise. Often produces even better diffs than patience.

Git: git config diff.algorithm histogram.

Heckel diff (1978, revived in 2024)

Paul Heckel's 1978 algorithm was largely forgotten because it produces "wrong" diffs in edge cases. But for the AI-generated code applications that emerged in 2023-24 (Cursor, Aider, Continue), Heckel-style diffs work beautifully because they handle insertions and re-orderings naturally.

Modern AI coding tools often use Heckel variants combined with confidence scoring.

Word-level vs line-level vs character-level

The right granularity depends on what you're diffing. Our diff tool defaults to line-level with character-level highlighting within changed lines — best of both.

Three-way merge (the diff cousin)

When two people edit the same file from a common ancestor, you need three-way merge:

1. Diff ancestor → mine
2. Diff ancestor → theirs
3. Combine, flagging conflicts

Git uses Myers for the diffs and a recursive strategy for combining. When changes overlap, you get conflict markers <<<<<<<.

Real-world performance

Beyond text: structural diff

Code-aware diffs (difftastic, semantic-diff) parse the syntax tree and diff that:

• Reformatting (whitespace, brace style) shows as no change
• Renaming a variable shows as one logical change, not many
• Reordering function definitions doesn't show "all changed"

Cost: 10-100x slower than text diff. Worth it for code review.

Browsers: virtual DOM diff

React's reconciliation is a tree diff specialised for UI:

• Compares old and new virtual DOM trees
• Computes minimum DOM operations (insert, remove, move, update attribute)
• Uses keys to identify reordered elements (the famous "key" prop)

This is why the lack of key on list items causes performance problems — without keys, the diff can't tell "this item moved" from "this item changed."

Tools and config

Get better Git diffs:

# Use histogram diff (best human readability)
git config --global diff.algorithm histogram

# Show word-level changes within lines
git diff --word-diff=color

# Show moved blocks differently
git config --global diff.colorMoved zebra

Tools

• Diff checker — paste two texts, see differences side-by-side
• difftastic — syntax-aware diff for code review
• delta — beautified Git diff renderer

Bottom line

Myers diff is fine for most uses. Switch Git to histogram for nicer code diffs. Use word-level diff for prose. Use structural diff for code review. The AI era is reviving older algorithms (Heckel) for new use cases — diff is far from a "solved" field.