Algorithm comparison
Git has more than one way of producing a diff. All of them are correct; what differs is which answer a human finds easiest to read. This page runs all of them at once so the difference is visible.
Myers, patience, and histogram on the same input. Patience usually produces a longer script — that is the point: minimal is not the same as readable.
Give it two texts
Before anything is compared the text becomes a list of numbers — one per line, word or character. That choice is what counts as being the same, so it changes the grid, the D, and the diff that comes out. A diff is not one thing: it is the answer to the question you asked.
Every route on one edit graph
Each algorithm’s answer drawn as a path on the same grid. Where the routes coincide they agree; where they split, they attribute the change differently.
- Myers
- Linear Myers
- Patience
- Histogram
The numbers
| Algorithm | Script length (D) | Hunk count | V cells stored | Guarantees minimal |
|---|---|---|---|---|
| Myers | 2 | 1 | 16 | Yes |
| Myers — linear space | 2 | 1 | 22 | Yes |
| Patience | 2 | 1 | — | Not guaranteed |
| Histogram | 2 | 1 | — | Not guaranteed |
- Script length (D)
- Lines deleted plus lines inserted. Smaller is tighter.
- Hunk count
- How many separate chunks you have to read. Fewer is usually kinder.
- Guarantees minimal
- Whether the algorithm guarantees the smallest possible D — not whether its D happens to be minimal on this input.
The linear-space variant stored more cells than greedy here. That is not a miscount: it trades O(D²) storage for O(N+M) plus a fixed recursion overhead, and on an input this small the overhead wins. The order reverses as D grows — open a larger preset in the edit graph to watch it.
On this input all four agree: same D, same number of hunks. That is the common case on small edits — the differences appear when a repeated line gives Myers somewhere else to anchor. Try the "Where patience wins" preset.
Only Myers guarantees a minimal D. Patience and histogram trade minimality for readability.
The output, side by side
One input, four ways of reading it.
Myers
D = 2 · 1 hunk
Myers — linear space
D = 2 · 1 hunk
Patience
D = 2 · 1 hunk
Histogram
D = 2 · 1 hunk