Two engineers on the same pull request see different diffs. One reviewer sees a block of seven lines moved from one helper into another, with git's default coloring showing the entire extractClaims function rewritten. The other reviewer, who set git config --global diff.algorithm patience six months ago and forgot, sees the same commit as a clean addition to the new helper and a clean deletion from the old one. Neither diff is wrong. The input has multiple valid alignments, and the two algorithms picked different ones.
This is the central thing to understand about line-based diff tools. There is no canonical answer to "what changed between these two files." A diff is the output of an alignment algorithm whose job is to find a minimum-cost edit script, and different algorithms have different definitions of cost. Once you accept that, the dialect war between Myers, patience, histogram, and structural diff stops being mysterious.
The Myers algorithm (1986): the line-diff baseline
Eugene Myers published "An O(ND) Difference Algorithm and Its Variations" in *Algorithmica* in 1986. It is still the algorithm diff, git diff, svn diff, and most other line-based tools reach for by default. The output is a minimum edit script: the shortest sequence of insertions and deletions that transforms file A into file B, measured in lines.
Myers is fast (linear in the size of the smaller input plus the edit distance), correct in the sense of "produces a valid edit script of minimum length," and oblivious to the meaning of the lines. The algorithm operates over an array of tokens. Whether each token is a line, a character, a word, or a byte is the caller's choice. The math doesn't care.
The problem is that "minimum number of inserted and deleted lines" is a weak proxy for "what a human would call the change." Common lines like closing braces and blank lines and return statements get matched eagerly. If file A and file B both contain a } at line 47, Myers will match them, even if the surrounding context makes that obviously the wrong call. The resulting diff is technically minimal but reads like a jigsaw puzzle, especially when a developer refactors by moving a function from one place to another.
Patience diff: when Myers picks bad anchors
Patience diff was proposed by Bram Cohen (the BitTorrent author) in the early 2000s, originally for the Codeville version-control system and later picked up by Bazaar and Git. The algorithm is:
- Find all lines that appear exactly once in each file. These are the "unique" lines.
- Of those, find the longest common subsequence. These become the anchor points.
- Between consecutive anchors, recurse: do the same thing on each gap.
- When no more unique anchors remain in a gap, fall back to Myers.
The effect is to align around content that is unambiguously the same line in both files (function signatures, distinctive comments, unusual variable names) and to avoid matching the noise of repeated structural tokens. The diff that comes out usually corresponds to how a human would describe the change. Moved blocks read as moved blocks. Refactors don't fragment.
The tradeoff is speed and a different failure mode. Patience is slower because the unique-line detection requires an extra pass and the recursive structure adds overhead. And on files with very few unique lines (a CSV, a JSON array of similar objects, a long lookup table), patience degenerates back to Myers without having added anything useful.
Histogram diff: faster patience
Histogram is a refinement of patience that drops the "exactly once" requirement and replaces it with a frequency histogram: rare lines are weighted more than common lines as anchor candidates. It was first implemented in JGit, then ported to libgit2 and mainline Git. The --histogram flag has been available since Git 1.7.7 (released October 2011).
Mainline Git still defaults to Myers, but several front ends, IDE integrations, and code-review tools default to histogram now. That's why two developers on the same repo can see different diffs without consciously changing a setting. The config key is diff.algorithm and the valid values are myers, minimal, patience, histogram.
(minimal is Myers with extra work spent trying to shorten the edit script further. It's slower and produces diffs that are sometimes shorter but usually no more readable. Most people who set it on regret it after the first 200-file pull request.)
Structural diff: leaving line-diff territory
All four algorithms above operate on a sequence of tokens. They make no use of the fact that the tokens might be lines of JSON, YAML, XML, source code, or arbitrary text. Indent JSON differently and Myers, patience, and histogram all flag every line as changed. Reorder the keys of an object and they all flag every line as moved.
Structural diff is the category of algorithms that parse the input first and diff the resulting tree. For JSON, that means tokenizing into an object/array/scalar tree and walking both sides. Common implementations:
- jsondiffpatch (JavaScript). Object diff with optional array-by-id matching. Output is a JSON document describing the changes.
- dyff (Go). Specifically targets YAML, designed for Kubernetes manifests. Human-readable output.
- json-diff (CLI, multiple implementations). Lightweight, suitable for CI scripts.
- jq with a comparison script. Not a diff tool per se but routinely used as one.
The output of a structural differ is fundamentally different from a line differ's. Two objects with the same keys in a different order produce zero differences. A nested change at spec.containers[0].image shows up as one change at one path, not as a block of moved braces. White-space variation is invisible.
The cost is that structural diff doesn't make sense for arbitrary text. You can't run it on a Markdown file or a log file or a Python source file (without first parsing Python). It's a category of tool that requires a parseable, structured format. For JSON, YAML, XML, HCL, and a handful of others, it's the right tool. For anything else, you're back to line diff.
JSON Patch (RFC 6902) vs JSON Merge Patch (RFC 7396)
When you want to express the output of a JSON structural diff, two IETF standards compete. They look superficially similar and produce wildly different documents.
JSON Patch (RFC 6902, published April 2013) describes a sequence of operations. A patch is a JSON array, each element an object with an op field of one of: add, remove, replace, move, copy, or test. Paths use JSON Pointer (RFC 6901). A small example:
[
{ "op": "replace", "path": "/spec/replicas", "value": 5 },
{ "op": "add", "path": "/metadata/labels/owner", "value": "platform-team" },
{ "op": "remove", "path": "/metadata/annotations/deprecated" }
]The patch applies deterministically; test operations let you guard against concurrent modifications. It's the right format for API edit endpoints. Kubernetes' kubectl patch --type json uses it directly.
JSON Merge Patch (RFC 7396, published October 2014) describes a target document instead. The patch is a JSON object shaped like the original; values present in the patch overwrite the original, null values delete keys, and missing keys leave the original untouched. The same change as above:
{
"spec": { "replicas": 5 },
"metadata": {
"labels": { "owner": "platform-team" },
"annotations": { "deprecated": null }
}
}Merge patch is dramatically simpler to write by hand, but it cannot express array modifications other than wholesale replacement, and it conflates "delete this key" with "set this key to null." For configuration files with sparse changes it's fine. For anything with arrays of objects, JSON Patch is the only one of the two that gives an unambiguous answer.
Both standards are in active use. Kubernetes' strategic merge patch (yet a third format) borrows from RFC 7396 and adds array-merge directives via custom annotations. The choice between formats is usually dictated by the consumer, not the producer.
Where each algorithm picks the wrong answer
A direct comparison:
| Algorithm | Best for | Falls apart on | Origin |
|---|---|---|---|
| Myers (1986) | Source code with few repeated lines | Many similar lines (CSVs, JSON arrays), moved blocks | Algorithmica 1986 |
| Patience (early 2000s) | Refactored source code, moved functions | Files with no unique lines | Cohen, originally for Codeville |
| Histogram | Large source files, the general case | Same as patience on truly repetitive input | JGit; Git --histogram since 1.7.7 (2011) |
| Structural | Structured data with semantic meaning | Free-form text, arbitrary file formats | Tool-specific; output per RFC 6902 or 7396 |
The other useful framing: line-based diff is right when the format is line-meaningful, and wrong when it isn't. JSON pretty-printed across many lines is technically a line-based file but it isn't a line-meaningful one. Two valid JSON documents can be byte-identical in meaning but disagree on hundreds of lines because one uses two-space indent and the other uses four.
For YAML the problem is worse. Anchors and aliases (<<: *defaults) produce dramatically different line counts for equivalent resolved content. Diffing a values.yaml file that uses anchors against the same file with anchors expanded gives a 200-line line-diff for a zero-change semantic comparison.
Choosing an algorithm, or letting the tool choose
For most development workflows the right defaults are: histogram for git diff if you're willing to override the default (git config --global diff.algorithm histogram), patience for code-review tools that haven't caught up, and structural for anything that's actually structured data.
The thing not to do is run a structural diff and a line diff on the same file and trust one to be canonical. They answer different questions. A structural diff of two Kubernetes manifests answers "what configuration changed." A line diff of the same two files answers "what bytes changed." The line diff includes formatting noise. The structural diff doesn't. Whether the formatting noise matters depends on whether the consumer of the file cares about formatting (a code reviewer might, a Kubernetes API server doesn't).
If you spend any part of your week pasting JSON or YAML into a diff tool and squinting at line-by-line color highlights to figure out what actually changed, you're using a line-based tool to answer a structural question. A semantic diff like Diffpad parses both sides into their object representation first, walks the trees, and reports changes by key path. The output is shorter, doesn't break when someone reorders keys, and doesn't care about indentation.