Production Case Study: Inside git diff (Myers vs Patience vs Histogram Diff)

1. The Boilerplate Misalignment Problem in Pure Myers Diff

Suppose File $A$ and File $B$ differ because a developer rewrote the body of func_one() while adding func_two(). Inside those functions sit dozens of identical boilerplate lines (}, return err;, blank lines). Because pure Myers diff treats every line as an unweighted token and greedily slides along the first available diagonal snake, it readily matches the closing } of func_one() in File $A$ with the closing } of func_two() in File $B$, producing a tangled, unreadable diff hunk that splits across function boundaries.

2. Git's Three Production Diff Engines

1. git diff --myers (Default / xdl_do_diff): Hashes each line into an integer token ID, strips common prefix/suffix lines, and runs Bidirectional Myers $O(ND)$ with Hirschberg's linear-space midpoint split (find_snake). Fast when $D$ is small, but includes heuristic cutoffs (max_chain_length) when $D$ is huge so it doesn't stall in $\Theta(N^2)$ time on completely rewritten files.
2. git diff --patience (Bram Cohen):
   • Identify all lines that occur exactly once in File $A$ AND exactly once in File $B$.
   • Find the Longest Increasing Subsequence (LIS) of their line positions in $O(U \log U)$ time via Patience Sorting (hence the name!).
   • Use those matched unique lines as immovable structural anchors, and recursively diff the sub-slices between consecutive anchors (falling back to Myers when no unique common lines remain in a slice).
3. git diff --histogram (JGit / Git 1.7.7+): What if a slice has no lines with count $== 1$ (e.g., a file with two similar classes where every header appears twice)? Patience Diff immediately falls back to Myers. Histogram Diff generalizes Patience Diff: it builds a frequency histogram of all lines in $A$, scans for the common line with the lowest occurrence count (up to a threshold of 64 occurrences) that forms the longest contiguous matching block, splits both files around that anchor block, and recurses on the prefix and suffix!

3. Visual Trace: Myers Brace Misalignment vs. Patience/Histogram Anchor

4. Reference Implementation: Patience Diff Unique-Line LIS Anchor Finder

#include <algorithm>
#include <string_view>
#include <unordered_map>
#include <utility>
#include <vector>

struct AnchorMatch {
    int line_a;
    int line_b;
};

// Finds Patience Diff structural anchors: Longest Increasing Subsequence of unique common lines
std::vector<AnchorMatch> find_patience_anchors(const std::vector<std::string_view>& a,
                                               const std::vector<std::string_view>& b) {
    std::unordered_map<std::string_view, int> count_a, count_b, pos_b;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) count_a[a[i]]++;
    for (int j = 0; j < static_cast<int>(b.size()); ++j) {
        count_b[b[j]]++;
        pos_b[b[j]] = j;
    }

    // Collect pairs (i, j) for lines occurring exactly once in A and once in B
    std::vector<AnchorMatch> uniques;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        if (count_a[a[i]] == 1 && count_b[a[i]] == 1) {
            uniques.push_back({i, pos_b[a[i]]});
        }
    }
    if (uniques.empty()) return {};

    // Patience Sorting O(U log U) Longest Increasing Subsequence on line_b
    const int u = static_cast<int>(uniques.size());
    std::vector<int> tails, tail_idx, parent(u, -1);
    for (int k = 0; k < u; ++k) {
        int y = uniques[k].line_b;
        auto it = std::lower_bound(tails.begin(), tails.end(), y);
        int idx = static_cast<int>(it - tails.begin());
        if (it == tails.end()) {
            tails.push_back(y);
            tail_idx.push_back(k);
        } else {
            *it = y;
            tail_idx[idx] = k;
        }
        if (idx > 0) parent[k] = tail_idx[idx - 1];
    }

    std::vector<AnchorMatch> anchors;
    for (int cur = tail_idx.back(); cur != -1; cur = parent[cur]) {
        anchors.push_back(uniques[cur]);
    }
    std::reverse(anchors.begin(), anchors.end());
    return anchors;
}