Git Diff Algorithms Compared: Myers, Patience, Histogram

1. Why the chosen diff algorithm makes a difference at all

Mathematically, a diff between two file versions is never unique: there is almost always more than one valid way to turn one file into the other, and a diff algorithm has to pick one of them. That is exactly where the algorithms available in Git differ, they optimize for different criteria and, given identical input, can produce quite different but each technically correct diffs.

For a review, that is far from a purely academic detail: a diff that shows a moved function as a full deletion and reinsertion costs a reviewer noticeably more time and attention than a diff that clearly recognizes the same function as an unchanged, relocated block and only marks the lines that actually changed.

2. The Myers algorithm: Git's default and how it works

The Myers algorithm is Git's default and is based on finding the longest common subsequence of two line lists, LCS for short. It computes the shortest possible sequence of insert and delete operations that turns one file into the other, and it is provably optimal with respect to the number of diff lines produced.

That very optimization for minimal line count can lead to unexpected results, though: the algorithm has no notion of semantic meaning and can therefore interpret coincidentally matching but entirely unrelated lines as belonging together, for instance a closing curly brace that looks identical in many places throughout a file.

# Myers is the default, so it does not need to be specified explicitly
git diff --diff-algorithm=myers

3. Patience diff: unique common lines as anchors

Patience diff takes a different approach: it first looks specifically for lines that appear exactly once in each file version and uses those unique lines as fixed anchor points. Between two consecutive anchors, the diff is computed recursively again, which makes the algorithm rely far more on unique structural features of the code than the purely line-based Myers algorithm.

This approach pays off especially with moved code blocks: a unique function signature or a distinctive comment serves as a reliable anchor point, so the entire block in between is more likely to be recognized as a coherent move instead of being broken up into many small, confusing individual changes.

git diff --diff-algorithm=patience

4. Histogram diff: an evolution of patience with better performance

Histogram diff conceptually builds on the idea behind patience diff, but uses a frequency table, a so-called histogram, to find unique anchor lines instead of a more expensive longest-common-subsequence search at every step. That keeps the basic behavior very similar to patience diff, while the computation itself runs noticeably faster in practice.

Thanks to this combination of patience-like result quality and better performance, histogram has become the preferred alternative to the Myers default in many projects, even outside of Git: other tools such as JGit already use histogram by default, because it strikes a good balance between readability and computational cost for realistic code changes.

git diff --diff-algorithm=histogram

5. The minimal algorithm and when it makes sense

The minimal algorithm is essentially a variant of the Myers algorithm that spends extra computation to guarantee the absolutely shortest possible diff output, even in cases where regular Myers would already have accepted a near-optimal but not quite minimal solution for performance reasons.

In practice, minimal pays off mainly for very small but critical diffs, for instance automatically generated patches that get processed further by machine, where every superfluous diff line causes real extra work. For everyday review use, minimal rarely offers a noticeable difference over Myers.

git diff --diff-algorithm=minimal

6. Choosing a diff algorithm for a single invocation

For a one-off test, the algorithm can be set directly via the --diff-algorithm command line option on any single call to git diff, git show or git log -p, without touching the permanent configuration. That works well for quickly checking, on a confusing diff, whether a different algorithm produces a clearer picture.

Especially on large refactorings, where entire methods or classes have been moved around within a file, this quick comparison is almost always worth it: switching from Myers to histogram often makes the difference between an unreadable tangle of deletions and insertions and a clearly recognizable, relocated block.

# Quickly try a different algorithm on a confusing diff
git diff --diff-algorithm=histogram HEAD~1

7. Configuring the algorithm permanently

Instead of specifying the algorithm on every call, git config diff.algorithm can set a default for the entire repository, or globally for every repository of a user. Many teams now set histogram as the new default, since in practice it rarely produces worse results than Myers and is clearly superior on moved code.

This setting also affects tools that internally rely on git diff, including many graphical git clients and IDE integrations, as long as they honor the git configuration correctly and do not ship their own hard-coded diff algorithm.

# Set histogram as the permanent default for this repository
git config diff.algorithm histogram

# Or globally for every repository of the current user
git config --global diff.algorithm histogram

8. Indent heuristic as a complement to the algorithm

Regardless of the chosen algorithm, Git additionally applies a so-called indent heuristic by default, which prefers aligning diff boundaries with lines that have lower indentation, for instance the end of a block rather than the middle of a condition. In practice that often produces more intuitive diffs, because braces and block boundaries tend to stay together instead of splitting arbitrarily in the middle of the code.

The heuristic has been enabled by default for a number of Git versions and can be disabled selectively via diff.indentHeuristic if needed, though that rarely makes sense in practice. It works independently of the chosen diff algorithm as an additional post-processing step, so it combines with Myers just as well as with histogram or patience.

# Explicitly disable the indent heuristic, it is enabled by default
git config diff.indentHeuristic false

9. A practical example: a moved function and how the algorithms diverge

If a helper function inside a file is moved further down and a new function is written in its old place at the same time, Myers often interprets the result as a series of nested deletions and insertions scattered across the whole file, because the algorithm optimizes purely for minimal line count without any semantic understanding of related blocks.

Patience and histogram, on the other hand, usually recognize reliably based on unique lines like the function signature that this is a pure move, and display the moved function as unchanged while only the genuinely new function gets marked as an insertion. On code changes with many repeated, generic lines, such as short closing braces, Myers sometimes surprisingly produces more compact results than the other algorithms.

10. Summary

11. FAQ: Diff Algorithms