Myers, Patience, Histogram: The Diff for Note History

Reference: git's diff algorithms — the myers, minimal, patience, and histogram engines in git (C / xdiff), rooted in Myers (1986) and Hunt–McIlroy (1976).

When you keep notes as plain text under version control, a diff is how you read your own past. Git ships four line-diff algorithms and two rendering levers on top. None is universally "most readable." Which combination you pick decides whether a revision looks like a clean insert or a scrambled hunk.

That last sentence is the whole post, so here is the honest version up front. The diff algorithm — Myers, minimal, patience, or histogram — is only one of the things that shapes a hunk. Git's indent heuristic — added in 2.11 and on by default since 2.14 — already slides most hunks to the readable line. Word-diff renders changes inside a line instead of replacing the whole line. And the deepest factor is the one no flag controls: whether your note text gives the matcher unique lines to anchor on. This post takes all four algorithms, runs them on real note-shaped text, shows where they diverge and where they agree, and lands on a config you can set once.

Why does git diff sometimes make note edits unreadable?

A diff engine does not know what a paragraph is. It sees a list of lines and keeps the longest run it can, marking the rest added or deleted. When a note repeats identical lines — blank lines, identical ## headings, list scaffolds — the matcher can latch onto the wrong copy and produce a hunk that straddles a logical boundary.

The original Unix diff set the goal that every later algorithm inherited. Hunt and McIlroy, at Bell Labs in 1976, described their program as reporting differences "expressed as a minimal list of line changes to bring either file into agreement with the other."¹ Minimal is the operative word. A shortest edit script is not the same thing as the edit a human would describe, and for repetitive prose the gap between the two is exactly where hunks become hard to read.

Here is that gap, reproduced. A daily journal where every entry starts with an identical ## Log heading, and you insert one new entry in the middle:

@@ -6,2 +6,6 @@ Woke early, wrote 500 words.
 
+Called the dentist.
+
+## Log
+
 Reviewed the pull request.

You inserted a whole ## Log entry. The diff instead shows new text appended to the previous entry plus a trailing ## Log — a straddle. Every git algorithm produces this same output here, and the reason why is the key to the rest of the post.

What are the four algorithms git ships?

Git exposes four line-diff variants through --diff-algorithm= (or the diff.algorithm config): myers, minimal, patience, and histogram. The documentation describes myers as "The basic greedy diff algorithm. Currently, this is the default."² It tells minimal to "Spend extra time to make sure the smallest possible diff is produced,"² and calls histogram an extension of patience to "support low-occurrence common elements."²

They all solve the same problem — find a good common subsequence of lines — and differ only in how they choose the lines to keep. Myers walks an edit graph greedily. Patience throws away every ambiguous line and anchors on lines that are unique. Histogram is patience made practical. Minimal is myers told to spend more time proving its answer is the shortest. The pipeline below is the same for all four; only the middle box changes.

flowchart TD
  A[Old note vs<br/>new note] --> B[Split into lines]
  B --> C{Diff algorithm}
  C -->|Myers| D[Greedy<br/>shortest edit]
  C -->|Patience| E[Anchor on<br/>unique lines]
  C -->|Histogram| F[Unique + rare<br/>lines first]
  D --> G[Edit script<br/>plus/minus lines]
  E --> G
  F --> G
  G --> H[Indent heuristic<br/>slides boundaries]
  H --> I{Word-diff on?}
  I -->|Yes| J[Token-level<br/>changes]
  I -->|No| K[Line-level<br/>hunks]
  J --> L[Readable history]
  K --> L

Figure: git's diff path. Both note versions are split into lines; one of four algorithms produces an edit script of added and removed lines; git's indent heuristic then slides hunk boundaries to the most readable line; and, if word-diff is enabled, changes are re-rendered token-by-token inside each line before the final hunks are shown.

What does Myers actually optimize?

Myers optimizes for the shortest edit script — the fewest added-and-deleted lines that turn the old note into the new one. The 1986 paper models the two files as a graph and finds a shortest path through it. Its abstract states the algorithm "performs well when differences are small (sequences are similar) and is consequently fast in typical applications."³

The paper's headline result is a complexity bound: "a simple O(ND) time and space algorithm is developed where N is the sum of the lengths of A and B and D is the size of the minimum edit script for A and B."³ Because D is small when two note versions are similar — most edits touch a few lines — the algorithm is fast on exactly the input git sees most. A refinement gives "O(N + D2) expected-time performance under a basic stochastic model."³ For a note file, D is tiny, so Myers is effectively linear.

The trade-off hides in the word minimal. Consider two near-identical structures separated by identical lines. A greedy shortest-script matcher can pair the closing line of one block with the opening of the next, because that pairing happens to be one edit shorter. The script is minimal; the rendering is a straddle. This is not a bug — it is Myers doing precisely what it promises. It just optimizes a number that is not "legibility."

How do patience and histogram change the result?

Patience and histogram keep Myers' goal but change the anchors. Instead of greedily matching any line, patience finds the lines that are unique, aligns those, and recurses into the gaps. Bram Cohen, who designed it, described the core step plainly: "Find all lines which occur exactly once on both sides, then do longest common subsequence on those lines, matching them up."⁴

The payoff is that patience refuses bad matches. Cohen's own summary: "if you've completely rewritten a section of code it shouldn't match up the blank lines in each version."⁴ For notes, that means a rewritten paragraph is shown as one replaced block, not as a mosaic of coincidentally-shared blank lines and punctuation. Histogram is the same idea tuned for speed and for lines that appear a few times rather than exactly once — git's docs call it an extension to "support low-occurrence common elements."² It was ported into git from JGit; the source file xdiff/xhistogram.c still carries its origin, "Copyright (C) 2010, Google Inc. and other copyright owners as documented in JGit's IP log."⁵

But here is the honest limit, and it is the reason the journal example above straddled under every algorithm. Patience anchors only on lines that occur exactly once on both sides. An identical ## Log heading repeated ten times is unique nowhere, so patience has nothing to grab and falls back to the same greedy-shaped result. Unique anchors are a property of your text, not of the flag you pass.

The lever nobody credits: git's indent heuristic

Before you reach for a different algorithm, know that modern git already fixed most of the classic "straddle." Git 2.11 (2016) added an indent heuristic — a post-pass that slides a hunk's boundaries to the most readable line — and git 2.14 (2017) turned it on by default. It runs whichever of the four algorithms you choose.

The 2.11 release notes describe the motivation directly: output "can be made easier to read by intelligently selecting which lines are common and which lines are added/deleted when the lines before and after the changed section are the same."⁶ A year later the experiment concluded. The 2.14 notes: "The 'indent' heuristics is now the default in 'diff'. The diff.indentHeuristic configuration variable can be set to 'false' for those who do not want it."⁷ The config docs describe it as "the default heuristics that shift diff hunk boundaries to make patches easier to read."⁸

This is why, if you test the famous "insert a function between two functions" example on git 2.14+, plain default Myers already produces the clean, block-aligned diff that people used to switch to patience for. The heuristic does the boundary work; the algorithm chooses which lines match. When you evaluate diff readability in 2026, you are almost always looking at Myers-plus-indent-heuristic, not raw Myers.

The bigger prose win: word-diff

For prose, the single largest legibility gain is not the line algorithm at all — it is word-diff, which renders changes inside a line instead of replacing the whole line. Reflowed sentences and small wording edits are where line diffs read worst, and --word-diff (or --color-words) turns a whole-line swap into a precise token-level highlight.

Take a one-sentence note edit. The default line diff shows the entire sentence removed and re-added, leaving you to spot the three words that actually changed:

-The meeting is scheduled for Tuesday at 3pm in the small conference room.
+The meeting is scheduled for Wednesday at 4pm in the large conference room.

The same edit under git diff --word-diff isolates exactly what moved:

The meeting is scheduled for [-Tuesday-]{+Wednesday+} at [-3pm-]{+4pm+} in the [-small-]{+large+} conference room.

Word-diff is orthogonal to the algorithm — it operates on the line-level hunks after they are computed, so it composes with any of the four. It is also the lever that most directly serves note history, where edits are wording changes far more often than structural moves. Pair it with hard-wrapping your notes so each sentence is its own line, and even the line algorithm gets unique anchors to work with — the input-formatting lever covered in hard-wrap your notes so diffs are readable.

Is any algorithm faster, at note scale?

At the size of a note vault, no — speed is not a reason to choose. On a generated markdown corpus of about 32,000 lines (723 KB) with a scattering of edits and inserted sections, all four algorithms finished a full git diff in roughly the same time. Best-of-five wall-clock, git 2.43.0:

Those numbers include process startup, so the real algorithm time is smaller still — the spread is noise at this scale. Histogram was marginally slower here, not faster, which is the opposite of the folklore that histogram is the fast choice. For files that are megabytes of source with large diffs the picture can shift, but a note history is not that workload. Choose for readability; the clock will not notice.

So which one produces the more readable diff?

None of them, universally — and proving that is more useful than crowning a winner. Readability is the product of four things that compose: the algorithm's anchoring, git's indent heuristic, whether word-diff is on, and whether your text has unique lines to align. Change any one and a "confusing" diff can become a clean one without touching the others.

The claim survives its own test. Brute-forcing thousands of small edits over deliberately repetitive inputs, Myers and histogram do diverge — but Myers frequently produces the shorter diff. Given the change c c c a → c c a c c a, Myers adds two lines while histogram rewrites three. Neither is wrong; they optimize different things. And when the text is genuinely repetitive with no unique line, as in the identical-## Log journal, all four straddle together. The algorithm is a real lever, but it is one lever among four, and it is not the strongest one for prose.

That is the practical takeaway for owning a note history. A legible past is not a single setting you flip. It is a small stack: histogram or patience for structured text, the indent heuristic you already have, word-diff for wording edits, and the writing habit of unique headings and one sentence per line. Plain-text notes make all of this available to you — the history is a file, and the tools that read it are yours to configure.

What to set

Make histogram your default and reach for word-diff when you review prose — that is the whole toolkit. Set the algorithm once so every diff uses unique-anchor matching, keep the indent heuristic you already have, and add word-diff per command when you read wording changes. Two lines of config get you there:

git config --global diff.algorithm histogram
git config --global diff.wsErrorHighlight all

Then read wording changes with:

git diff --word-diff

Setting diff.algorithm to histogram gives you unique-anchor behavior everywhere without a per-command flag, and it costs nothing measurable at note scale. The indent heuristic is already on. Word-diff stays a per-invocation choice because you want it for prose review and not for every machine-readable patch. That is the entire toolkit — one default, one habit.

Frequently Asked Questions

Which git diff algorithm is best for prose or markdown? There is no universal best. For structured or repetitive text, patience or histogram anchor on unique lines and tend to align hunks to logical boundaries. For wording edits — the common case in notes — --word-diff helps more than any line algorithm. Git's default myers plus its indent heuristic already handles most everyday edits cleanly.

Why does git diff shuffle my lines or show the wrong lines as changed? Because your text gives the matcher no unique anchor. When identical lines repeat — blank lines, identical ## headings, repeated list scaffolds — the algorithm can pair the wrong copies and produce a hunk that straddles a logical boundary. Unique, content-bearing lines fix this more reliably than switching algorithms does.

What is the difference between patience and histogram diff? Patience matches only lines that occur exactly once on both sides, then runs longest-common-subsequence over those anchors. Histogram extends the same idea to lines that appear a few times, not just once, and is the faster, more practical variant. Git's docs describe histogram as extending patience to "support low-occurrence common elements."

How do I make git diff show word-level changes? Run git diff --word-diff, which renders changes as [-removed-]{+added+} inside each line, or git diff --color-words for a color-only version. It operates on the line-level hunks after they are computed, so it works with any diff algorithm and is the biggest single legibility gain for prose edits.

Is histogram diff faster than myers? Not at note scale. On a 32,000-line markdown corpus, all four algorithms finished within about three milliseconds of each other, and histogram was marginally slower than myers, not faster. Choose an algorithm for how it renders changes, not for speed — the timing difference is noise for note-sized files.

How do I set git to always use histogram? Run git config --global diff.algorithm histogram. That applies unique-anchor behavior to every diff without a per-command flag. To revert to the default, use git config --global diff.algorithm default, or pass --diff-algorithm=default on a single command.

Does the diff algorithm change what gets committed? No. A diff is a view computed on demand from two versions; it is not stored. Git records the file content, not the patch between versions. Changing diff.algorithm, the indent heuristic, or word-diff changes only how a change is displayed — the committed bytes and your history are identical either way.

What is the indent heuristic in git? It is a default-on post-pass, added in git 2.11 and made default in 2.14, that slides a hunk's boundaries to the most readable line when the lines around a change are identical. It runs no matter which of the four algorithms you pick, and it is the reason modern default git already avoids most of the "straddle" that once motivated switching to patience.

A diff is how a plain-text note history speaks to you, and you get to choose the voice — histogram for structure, word-diff for wording, unique lines so the tools have something to hold onto.

Your notes are files, and their history is yours to make legible. mnmnote.com