Text Diff Algorithms: How Git, Patches, and Diff Tools Work

Every code-review tool, every git diff output, every patch file you have ever read traces back to a small number of algorithms invented between 1976 and 2009. Knowing which one your tool uses — and what assumption it makes — is the difference between reading a diff in 30 seconds and staring at a confusing one for ten minutes wondering whether the refactor actually preserved behaviour.

What a diff actually is

A diff is an edit script: a minimal sequence of insertions and deletions that transforms file A into file B. For two files of total length N with D differences, there are many possible scripts. A diff algorithm picks one according to some optimisation criterion — usually the smallest D, but not always.

Two corollaries follow. First, the same file change can legitimately produce different-looking diffs from different tools; they are all correct in the sense that applying them reconstructs file B. Second, “readable diff” is a weaker constraint than “smallest diff,” and the two often disagree. You can compare two files yourself with our text diff tool and see the unified output side by side.

Myers diff — the default everywhere

Eugene Myers's 1986 paper An O(ND) Difference Algorithm and Its Variations defined the algorithm that GNU diff, Git, Mercurial, SVN, and most editors still use by default. It frames the diff problem as finding the shortest path through an edit graph: each diagonal step is a matching line, each horizontal step deletes a line from A, each vertical step inserts a line from B. The shortest path corresponds to the minimum-edit script.

Time complexity is O(N × D) where N is total file length and D is the number of differences. For typical source files with small edits the algorithm is essentially linear; for files that have been rewritten end-to-end it degrades, which is why Git limits the analysis with diff.algorithm and diff.renameLimit defaults.

Myers's weakness is that it minimises diff size without any sense of structure. After moving a block of code, Myers often pairs up the closing brace of one function with the closing brace of a different one because that produces fewer total changed lines. The result is technically minimal and humanly bewildering.

Patience diff — designed for readability

Bram Cohen (the author of BitTorrent) introduced the Patience diff in 2007 specifically to fix Myers's refactor-readability problem. The algorithm:

1. Find all lines that appear exactly once in both files. These are unique anchor lines.
2. Compute the longest common subsequence of the unique anchors (using the patience-sort algorithm — hence the name).
3. Recursively diff each region between consecutive anchors using the same procedure, falling back to Myers when no unique anchors remain.

The result aligns the diff around the lines a human would recognise as “the same thing” — function signatures, unique comments, class declarations. Patience is slower than Myers in worst case but produces far more readable output for typical code changes. Enable it in Git with git diff --patience or globally with git config diff.algorithm patience.

Histogram diff — Patience, refined

Histogram diff was introduced by JGit (the Java Git implementation) and later ported into upstream Git. It improves on Patience by being smarter about which anchor lines to choose: instead of requiring uniqueness, it picks the rare lines with the lowest occurrence count in both files. Common lines (closing braces, blank lines) are deprioritised; rare lines (function names, distinctive strings) become anchors.

Histogram is the recommended default for most repositories today. It produces output similar to Patience for typical cases and noticeably better for files with many repeated lines (such as data files, fixtures, and configuration with lots of indentation). Enable globally with git config --global diff.algorithm histogram.

Reading a unified diff hunk

Unified diff (-u) is the de facto exchange format. A hunk looks like:

@@ -42,7 +42,9 @@ class UserController {
   const user = await User.findById(id);
   if (!user) {
-    return res.status(404).end();
+    logger.warn({ id }, "user not found");
+    return res.status(404).json({ error: "not found" });
   }
   return res.json(user);
 }

The @@ line is the hunk header. It says: the old file starts at line 42 and spans 7 lines; the new file starts at line 42 and spans 9 lines. The trailing text after the second @@ is a section heading — for code it is usually the enclosing function or class, picked by Git from a per-language heuristic.

Lines without a prefix are unchanged context. Lines starting with - exist only in the old file; lines starting with + exist only in the new file. The default context is three lines on each side; -U10widens it, useful when the change's effect depends on a statement just out of view.

Whitespace and line endings

The single largest source of confusing diffs is whitespace. Common offenders:

• Trailing whitespace. An editor that strips trailing spaces on save will flag every touched line. Configure core.whitespace and git diff --ignore-space-at-eol to keep the diff focused on real changes.
• Mixed indentation. Switching from tabs to spaces (or vice versa) is a full-file diff even if no logic changed. Use git diff -w to ignore all whitespace differences when reviewing such changes.
• Line endings. CRLF vs LF differences make every line look modified. Set up .gitattributes with * text=auto to normalise on commit.
• Final newline. Files without a trailing newline show \ No newline at end of file in the diff. Some tools add the newline silently on save, producing one-line diffs that look like noise.

Binary files

Diff algorithms operate on lines. Files without natural line breaks — images, executables, PDFs — produce useless output when diffed textually. Git detects binary content by looking for null bytes in the first 8 KB; when found, the diff reduces to Binary files a/x and b/x differ.

For binary content that should be diffable (DOCX, XLSX, design files), .gitattributes can register a custom textconv filter that converts the file to a textual representation before diffing. diff=word, diff=exif, and similar built-ins ship with Git.

Three-way merge and why conflicts happen

When you merge branch B into branch A, Git looks at three versions: the common ancestor C, the A version, and the B version. The merge proceeds line by line:

• Line unchanged from C to A but modified in B → take B.
• Line modified in A but unchanged in B → take A.
• Line modified identically in both → take either; no conflict.
• Line modified differently in A and B → conflict.

Conflicts are flagged in the working file with <<<<<<<, =======, and >>>>>>> markers showing both versions. The ancestor version can be included too with merge.conflictStyle diff3, which makes resolution much easier because you can see what each side started from.

Choosing an algorithm in practice

For day-to-day work, Histogram is the best default and the one most teams should configure globally. Patience produces very similar results and remains useful for very large files where Histogram's memory usage becomes noticeable. Myers is the right choice for machine-to-machine pipelines that consume diffs programmatically, because its output is the canonical minimum.

Code-review tools (GitHub, GitLab, Gerrit) all default to Myers because of legacy; their UIs do not always expose the algorithm choice. When a review diff looks misaligned, download the patch and re-render locally with git diff --histogram — the result is often much easier to read.

The honest takeaway

Switch your global Git algorithm to Histogram and never think about it again for most repositories. When a diff confuses you after a refactor, re-render with a different algorithm before assuming the change is wrong. Normalise whitespace and line endings at the repository level so reviewers spend their time on logic, not formatting. And remember that the diff is a presentation, not the truth — the truth is the two files, and a diff is just one of many valid ways to describe the path between them.