Diff Algorithms Explained: Myers, Patience, and Histogram

The Problem Behind Every Diff

Every diff tool solves the same mathematical problem: finding the Longest Common Subsequence (LCS) between two sequences of lines. The LCS is the longest set of lines that appear in both texts in the same order — though not necessarily contiguously.

Once you know the LCS, everything else is a deletion (lines in the original but not in the LCS) or an addition (lines in the new text but not in the LCS).

The challenge? The LCS problem is computationally expensive. A naive approach has exponential time complexity. Different algorithms trade accuracy, speed, and readability in different ways.

Myers Diff Algorithm

The Myers algorithm is the default in Git and most command-line diff tools. Published by Eugene Myers in 1986, it finds the shortest edit script — the smallest set of insertions and deletions that transforms the original text into the new text.

How It Works

Myers treats the comparison as a graph search. Each point represents a position in both texts. The algorithm searches diagonally (matching lines) and horizontally or vertically (edits) to find the shortest path from start to finish.

Key properties:

• O(ND) time complexity — where N is the total text length and D is the number of differences
• O(N²) worst case — when texts are completely different
• Linear in matching regions — when texts share long common sections, it runs nearly in O(N)

Strengths

• Produces the minimal edit script — no redundant insertions or deletions
• Fast when differences are small relative to file size (the common case)
• Well-tested and battle-proven in Git

Weaknesses

• Can produce awkward output when moved blocks exist — it may break a moved function into scattered deletions and insertions
• Does not recognize renames or moves natively

- function validate(input) {
-   return input.length > 0;
- }
  // ... 50 lines of unchanged code ...
+ function validate(input) {
+   return input.trim().length > 0;
+ }

In this case, Myers correctly detects the change, but if the entire function were moved to a different location, it would show as a deletion at the old spot and an addition at the new one.

Patience Diff Algorithm

Patience diff was created by Bram Cohen (also the creator of BitTorrent) and adopted by Git as an alternative strategy (git diff --patience). It focuses on producing more readable output for code.

How It Works

1. Find all lines that appear exactly once in both texts — these are "unique" lines
2. Compute the LCS of these unique lines using a patience-sorting approach
3. Use the unique-line LCS as anchor points
4. Run Myers diff on the segments between anchors

Strengths

• Better at preserving the structure of moved code blocks
• Function signatures, class declarations, and closing braces act as natural anchors
• Output aligns with how developers mentally parse code

Weaknesses

• Slower than Myers when there are few unique lines (degenerate cases)
• Still does not detect moves explicitly — it just avoids splitting them

Example: When a developer moves an entire method from the top of a file to the bottom, patience diff keeps the method intact instead of showing it as scattered line-level changes.

Histogram Diff Algorithm

Histogram diff is the default in JGit (the Java implementation of Git) and is available in Git via git diff --histogram. It extends patience diff with a focus on low-occurrence lines rather than strictly unique lines.

How It Works

1. For each segment between anchors, find the longest matching subsequence using lines with the lowest occurrence count
2. If a line appears 2 times in both texts,Histogram still considers it — patience would skip it
3. Recurse on remaining segments until no more matches exist

Strengths

• More robust than patience diff — it handles files with repeated patterns (like boilerplate code) better
• Often produces the most readable output for real-world codebases
• Falls back gracefully — when no low-occurrence lines exist, it behaves like Myers

Weaknesses

• Slightly slower than patience due to the additional occurrence-counting pass
• Implementation complexity is higher

Performance Comparison

In practice, the differences are subtle for small files. They become noticeable on files with:

• Hundreds of lines changed
• Moved or reordered functions
• Repeated boilerplate patterns

Which Algorithm Should You Use?

• General text comparison: Myers — fast and minimal
• Code review with moved blocks: Patience — cleaner alignment of functions
• Large files with repeated patterns: Histogram — most robust output
• Performance-critical pipelines: Myers — predictable O(ND) behavior

Most online diff tools hide the algorithm choice and use Myers or a hybrid approach. The best tool is the one that gives you output you can read and trust.

Related Guides

• Text Comparison Guide
• Code Review Diff Tips
• Regex Performance Tips

Try It Yourself

Use our free Diff Checker to compare texts instantly. Paste two versions, see every addition and deletion highlighted, and choose the view that fits your workflow — no command line needed.