How Diff Works: Unified Diff Format, the Myers Algorithm, and Reading Patches Fluently

git diff, code review, patch files, merge conflicts — a developer’s working life is framed by diffs. Most of us read them daily without ever asking how they’re produced, which works fine until the day it doesn’t: a diff that insists you rewrote a function you only moved, a merge conflict that makes no sense, or a 10,000-line patch for a one-word change. This guide explains what’s actually going on: the algorithm that finds the difference, the unified format that encodes it, and why diffs sometimes look “wrong” even when they’re technically correct.

The Problem Diff Actually Solves

Given two files, “the difference” sounds obvious until you try to define it. Change one line in the middle — easy. But move a paragraph from the top to the bottom and there are suddenly many valid descriptions: delete 40 lines here, insert 40 lines there — or delete the 3 lines above it, reinsert them above it — and so on, exponentially many of them. A diff tool must pick one, and the sensible criterion is: the smallest possible edit script — the fewest line insertions and deletions that transform file A into file B.

Reframed mathematically, this is the longest common subsequence (LCS) problem. If you find the longest sequence of lines that appears in both files in the same order (not necessarily contiguous), then everything else is the diff: lines in A but not the LCS are deletions, lines in B but not the LCS are insertions. Minimal edits = maximal common lines.

Myers: The Algorithm Behind Git Diff

Computing LCS naively is quadratic in both time and memory — fine for a paragraph, painful for a 50,000-line file. The algorithm Git uses, published by Eugene Myers in 1986, finds the minimal edit script in O((N+M)·D) time, where D is the size of the difference itself. The consequence that matters in practice: diff cost scales with how different the files are, not just how big they are. Two nearly identical huge files diff fast; two totally different small files diff fast too; the worst case is large files with large changes.

Myers’ insight is elegant: build a grid where the X axis is file A and the Y axis is file B, and finding the minimal diff becomes finding a shortest path from corner to corner, moving right (deletion), down (insertion), or diagonally (matching line, free). Git’s implementation adds heuristics on top — like shifting hunks so changes align with blank lines and function boundaries — which is why its output usually feels natural to read.

Reading Unified Diff: The Format Decoded

The unified diff format (what git diff and diff -u emit) packs the edit script into a compact, human-readable text. Anatomy of one hunk:

--- a/src/config.js
+++ b/src/config.js
@@ -10,7 +10,7 @@ function loadConfig() {
   const env = getEnv();
-  const timeout = 3000;
+  const timeout = 5000;
   return { env, timeout };
 }

• --- a/... / +++ b/... — the “before” and “after” files (a/ and b/ prefixes are a Git convention).
• @@ -10,7 +10,7 @@ — the hunk header: this hunk starts at line 10 in the old file (spanning 7 lines) and line 10 in the new file (also 7 lines). When the counts differ, e.g. -10,7 +10,9, the hunk added two net lines. The text after the second @@ is a context hint, usually the enclosing function.
• (space) — context line, present in both files.
• - — line removed; + — line added. A modified line always appears as a -/+ pair: there is no “change” operation, only delete + insert.

By default you get 3 lines of context above and below each change; git diff -U10 widens it, and tools like our Diff Checker render the same information side-by-side with highlighting, which is often easier for large prose or config comparisons than the raw patch format.

Why Diffs Sometimes Look Wrong

Understanding the algorithm explains the classic annoyances:

• “I only moved a function, but the diff shows a rewrite.” Line-based diff has no concept of moves — a move is literally a delete plus an insert. Some tools detect moved blocks heuristically (Git has git diff --color-moved), but the underlying edit script can’t express “moved.”
• Diff noise from reformatting. If a formatter reindents the file, every touched line is a change — the minimal edit script faithfully reports that yes, these 2,000 lines are different. Whitespace-insensitive modes (git diff -w) exist for exactly this.
• A better diff existed but wasn’t found. The shortest-path search is anchored on lines that match exactly. If you changed every line slightly (bumped a version number in each), the LCS collapses and the diff degrades to “delete everything, insert everything” — correct, but useless.
• JSON and other structured data. Line-based diff of pretty-printed JSON is decent, but reorder one key and the noise drowns the real change. Structure-aware tools compare parsed values instead of text: our JSON Diff shows which keys and values actually changed, regardless of key order or formatting — the right tool when the data is structured.

Practical Tips

• Small, focused commits aren’t just hygiene — they’re diff ergonomics. Reviewers (and future you) read edit scripts; the smaller D is, the clearer the story.
• Rename detection (git status showing renamed:) is a similarity heuristic applied after diffing, not magic: Git diffs the deletion against all additions and pairs the most similar.
• For prose and docs, word-level diff (or --word-diff in Git) is usually more readable than line-level.
• The inverse operation is patch / git apply: a unified diff plus a clean context match is all that’s needed to replay the change — which is why context lines exist in the format at all. They’re the anchor that lets patches survive small drift in the target file.

Quick Reference

• Diff = minimal insert/delete script = complement of the longest common subsequence.
• Myers’ algorithm: cost scales with the size of the difference, shortest-path on an edit grid; it’s what git diff runs.
• @@ -a,b +c,d @@ = old start,count / new start,count; - delete, + insert, space context; a “changed” line is a -/+ pair.
• Moves don’t exist in diff — they’re delete + insert; reformatting is indistinguishable from rewriting.
• Structured data deserves structural diff: compare parsed JSON, not text lines.