Myers diff

Deep dive

How it works

Parts:

• edit graph — grid, x over A (N items), y over B (M items); right = delete a[x], down = insert b[y], diagonal (free) where a[x] == b[y]
• diagonal k = x − y — a D-path ends on k ∈ {−D, −D+2, …, D}
• V[k] — furthest x on diagonal k with the current number of edits
• snake — maximal run of matching diagonal edges after an edit
• trace — V saved per round, for backtracking (O(D²) ints)

Steps:

1. Start with V[1] = 0. For D = 0, 1, 2, … and each k = −D, −D+2, …, D:
2. If k = −D or (k ≠ D and V[k−1] < V[k+1]) take x = V[k+1] (down: insert), else x = V[k−1] + 1 (right: delete); y = x − k.
3. Follow the snake: while a[x] == b[y], advance both.
4. Store V[k] = x. If (x, y) = (N, M), D is the shortest script length; stop.
5. After each round, save V[−D..D] in the trace.
6. Backtrack from (N, M) for d = D…1: find the predecessor diagonal in trace[d−1], emit the snake, then one Ins or Del.
7. Reverse: that is the script.

 A = ABCABBA, B = CBABAC (Myers' Fig. 1): D = 5, LCS = CABA
 round D=0   k: 0              V[0] = snake from (0,0)
 round D=1   k: -1 1           each k: best of V[k-1]+1 (right), V[k+1] (down), then slide
 round D=5   k: -5 -3 .. 5     some k reaches (7,6) = (N,M): done

Linear space: search forward from (0,0) and backward from (N,M) at once; where a forward and a reverse D/2-path overlap is the middle snake. Emit it and recurse on both halves. Space O(N+M), "roughly twice as slow" (Myers, VAX tests).

Code

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Edit { Eq(usize, usize), Del(usize), Ins(usize) } // indices into a / b

/// Shortest edit script (Myers 1986, greedy forward). Memory O(D^2): one V window per round.
pub fn diff<T: PartialEq>(a: &[T], b: &[T]) -> Vec<Edit> {
    let (n, m) = (a.len() as isize, b.len() as isize);
    let off = n + m + 1;
    let mut v = vec![0isize; 2 * off as usize + 1]; // v[k + off] = furthest x on diagonal k = x - y
    let mut trace: Vec<Vec<isize>> = Vec::new();    // trace[d] = V[-d..=d] after round d
    let mut dd = 0;
    'rounds: for d in 0..=(n + m) {
        for k in (-d..=d).step_by(2) {
            let mut x = if k == -d || (k != d && v[(k - 1 + off) as usize] < v[(k + 1 + off) as usize]) {
                v[(k + 1 + off) as usize]     // step down: insertion of b[y]
            } else {
                v[(k - 1 + off) as usize] + 1 // step right: deletion of a[x]
            };
            let mut y = x - k;
            while x < n && y < m && a[x as usize] == b[y as usize] { x += 1; y += 1; } // snake
            v[(k + off) as usize] = x;
            if x >= n && y >= m { dd = d; break 'rounds; }
        }
        trace.push(v[(off - d) as usize..=(off + d) as usize].to_vec());
    }
    let (mut x, mut y) = (n, m);
    let mut out = Vec::new();
    for d in (1..=dd).rev() {
        let (k, p) = (x - y, &trace[(d - 1) as usize]);
        let at = |kk: isize| p[(kk + d - 1) as usize];
        let pk = if k == -d || (k != d && at(k - 1) < at(k + 1)) { k + 1 } else { k - 1 };
        let (px, py) = (at(pk), at(pk) - pk);
        let sx = if pk == k + 1 { px } else { px + 1 }; // snake start after the edit
        while x > sx { out.push(Edit::Eq((x - 1) as usize, (y - 1) as usize)); x -= 1; y -= 1; }
        out.push(if pk == k + 1 { Edit::Ins(py as usize) } else { Edit::Del(px as usize) });
        (x, y) = (px, py);
    }
    while x > 0 { out.push(Edit::Eq((x - 1) as usize, (y - 1) as usize)); x -= 1; y -= 1; }
    out.reverse();
    out
}

/// Unified-style hunks with `ctx` lines of context.
pub fn unified(a: &[&str], b: &[&str], e: &[Edit], ctx: usize) -> String {
    let chg: Vec<usize> = (0..e.len()).filter(|&i| !matches!(e[i], Edit::Eq(..))).collect();
    let (mut out, mut i) = (String::new(), 0);
    while i < chg.len() {
        let mut j = i;
        while j + 1 < chg.len() && chg[j + 1] - chg[j] <= 2 * ctx + 1 { j += 1; } // merge close changes
        let (s, t) = (chg[i].saturating_sub(ctx), (chg[j] + ctx + 1).min(e.len()));
        let cnt = |r: &[Edit], a_side: bool| { // items of r that exist in A (or in B)
            r.iter().filter(|x| !matches!(x, Edit::Ins(_) if a_side) && !matches!(x, Edit::Del(_) if !a_side)).count()
        };
        out += &format!("@@ -{},{} +{},{} @@\n", cnt(&e[..s], true) + 1, cnt(&e[s..t], true),
                        cnt(&e[..s], false) + 1, cnt(&e[s..t], false));
        for x in &e[s..t] {
            match *x {
                Edit::Eq(p, _) => out += &format!(" {}\n", a[p]),
                Edit::Del(p) => out += &format!("-{}\n", a[p]),
                Edit::Ins(q) => out += &format!("+{}\n", b[q]),
            }
        }
        i = j + 1;
    }
    out
}

fn main() {
    let d = |a: &str, b: &str| diff(a.as_bytes(), b.as_bytes());
    let cost = |e: &[Edit]| e.iter().filter(|x| !matches!(x, Edit::Eq(..))).count();
    assert_eq!(cost(&d("ABCABBA", "CBABAC")), 5);         // Myers 1986, Fig. 1: D = 5, LCS = 4
    assert_eq!(cost(&d("same", "same")), 0);
    assert_eq!(cost(&d("abc", "xyz")), 6);                 // disjoint: N + M
    let (a, b) = ("ABCABBA", "CBABAC");
    let applied: String = d(a, b).iter().filter_map(|x| match *x {
        Edit::Eq(p, _) => Some(a.as_bytes()[p] as char),
        Edit::Ins(q) => Some(b.as_bytes()[q] as char),
        Edit::Del(_) => None,
    }).collect();
    assert_eq!(applied, b);                                // script applied to A gives B
    let (x, y) = (["a", "b", "c", "d", "e", "f", "g", "h", "i"], ["a", "b", "X", "d", "e", "f", "g", "h", "Y"]);
    print!("{}", unified(&x, &y, &diff(&x, &y), 1));
}

Compiled and run (asserts pass). Also checked against an O(NM) LCS table on 20,000 random short sequences: D = N + M − 2·LCS every time.

Complexity and constants

• Time O((N+M)·D): D rounds of up to D+1 diagonals, plus the snakes.
• Space of this code: round d keeps 2d+1 values of 8 bytes, about 8·D² bytes (computed): D = 1,287 is about 13 MB; D = 200,000 (unrelated 100,000-line files) over 300 GB, hence linear space or cut-offs.
• Measured on this Mac (Apple M4 Pro), release build, one thread, median of 7 in-process runs, two generated 10,000-line files with scattered insert / delete / replace edits (a replacement counts 2 in D):

Interning time not included. Cost is driven by D, then by one item comparison.

Efficiency

• Cost: D = 396 on 10,000 lines: 0.22-0.34 ms, about 3×10⁷-4.5×10⁷ lines/s (measured on this Mac (Apple M4 Pro), table above); memory about 8·D² bytes. Bound: item comparisons for similar inputs, memory for dissimilar ones. git diff --no-index end to end on the same files: about 12 ms per run (measured on this Mac, includes process start).
• Levers:
  • strip common prefix and suffix, discard lines present on one side only — shrinks N and M (GNU manual; git xdl_cleanup_records) — local edits
  • hash lines to integers once — 1.5-2.2× in the table (measured on this Mac) — every line diff
  • linear-space middle snake — O(N+M) memory, about 2× time (Myers 1986) — large or dissimilar inputs
  • cost cut-off — bounded time, non-minimal script (gnulib diffseq.h: O(N^1.5 log N)) — huge files, many changes
• Naive → standard → state of the art:
  • N×M LCS table · O(N·M) time and space
  • Myers greedy, saved V windows · O((N+M)·D) time, O(D²) space
  • preprocessing + middle snake + heuristics (git, GNU diff, imara-diff) · O(N) space, bounded worst case

Implementation notes

• i32 instead of isize in V and trace halves memory.
• GNU diff strips common prefix and suffix first (can rarely give a non-minimal result, --horizon-lines); --minimal turns its cut-off off, --speed-large-files adds a heuristic for scattered small changes.
• Git's xdiff stops at mxcost (about the square root of the diagonals, floor 256) and takes a "good enough" snake heuristic after 256 edits (xdiffi.c).

Pitfalls

• Assuming default output is minimal: git and GNU diff use heuristics; --minimal spends extra time on the smallest script.
• Zero-length hunk ranges print the preceding line number in real unified format; the code prints start + 1 (a sketch).
• Equal-length scripts differ in readability; blocks can slide past identical lines. Git's indent heuristic (default on) picks a nicer spot.
• CRLF and a missing final newline make equal lines unequal; normalise first.
• difflib is not Myers: it is Ratcliff/Obershelp-style and makes no minimality claim (Python docs).

Variants and alternatives

In production

git diff and git merge (xdiff), GNU diff (diffutils), Rust similar (built for the insta snapshot-testing library, per its README).

Implementations

Sources

• Eugene W. Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica 1(1-4):251-266, 1986. paper · author PDF
• Bram Cohen, Patience Diff Advantages, blog 2010. post
• GNU diffutils manual, diff Performance Tradeoffs. manual · gnulib diffseq.h
• git documentation, git diff --diff-algorithm. docs · xdiffi.c · xhistogram.c
• Python docs, difflib: The difflib algorithm. docs