Myers Diff Does 1.6% of the Work on Real Files and 105% on Random Ones

#algorithms #git #javascript #programming

Every diff you have read is the answer to one question: what is the shortest sequence of deletions and insertions that turns the old file into the new one? Myers' 1986 algorithm answers it by treating the two files as the axes of a grid and finding the cheapest path across — where moving diagonally, on a line both files share, is free.

👉 Live, runs in your browser: https://dev48.in/solve/day81-myers-diff.html

The search

Rather than exploring the grid cell by cell, Myers asks: how far can I get using exactly D edits? For each D it keeps only the furthest-reaching point on each diagonal — one number per diagonal, not a whole row — and stops the first time one reaches the corner. Because D only increases, the first arrival is minimal by construction.

for (let D = 0; D <= MAX; D++) {
  trace.push(V.slice());                   // snapshot, for backtracking later
  for (let k = -D; k <= D; k += 2) {
    let x = (k === -D || (k !== D && V[k-1+MAX] < V[k+1+MAX]))
      ? V[k+1+MAX]                         // moved down (insertion)
      : V[k-1+MAX] + 1;                    // moved right (deletion)
    let y = x - k;
    while (x < N && y < M && a[x] === b[y]) { x++; y++; }   // free diagonal
    V[k+MAX] = x;
    if (x >= N && y >= M) return { distance: D, script: backtrack(...) };
  }
}

🔴 The speed claim is half a truth

Everyone quotes O((N+M)D) against O(NM) and stops. Measured over 800 generated pairs:

corpus	worst D	Myers work vs an O(NM) table
a 40-line file with 4 edits	8	1.6%
random strings, 4-symbol alphabet	14	105%

On random strings D grows with the input, O((N+M)D) degenerates, and Myers does more work than the table it replaced. My first draft of this page quoted only the flattering corpus; the in-page check caught it.

The speed is not a property of the algorithm. It is a property of the algorithm meeting the inputs it was designed for — and files people actually diff are nearly identical, which is why it wins in practice.

The only honest test of a diff

Not "does it look right". Does the script rebuild the target?

function apply(a, script) {
  const out = []; let i = 0;
  for (const e of script) {
    if (e.op === "keep") { if (a[i] !== e.line) throw new Error("keep does not match"); out.push(a[i++]); }
    else if (e.op === "del") { if (a[i] !== e.line) throw new Error("delete does not match"); i++; }
    else out.push(e.line);
  }
  if (i !== a.length) throw new Error("script consumed " + i + " of " + a.length);
  return out;
}

800 of 800 generated pairs rebuilt exactly, with D = N + M − 2L satisfied every time against an independently computed longest common subsequence.

🔴 The bug in the V array

const V = new Array(2 * MAX + 1).fill(0);   // wrong
const V = new Array(2 * MAX + 3).fill(0);   // right

The search reads V[k-1] and V[k+1], so both ends need a slot of headroom. With two empty inputs MAX is 0, the array is one slot, the read runs off the end, returns undefined, and the loop never terminates. Every non-degenerate case worked perfectly.

Shortest is not readable

Several edit scripts can be equally short and they are not equally good to read:

change	D	hunks
two lines changed, adjacent	4	1
two lines changed, far apart	4	2

Same minimal distance, one tidy block versus two separate places to look. Minimising D says nothing whatever about this — which is why real diff tools bolt heuristics on top rather than trusting minimality alone.

How it is checked

188 asserts by three routes the page does not use: breadth-first search over the edit graph by layers, a full-table LCS with the subsequence reconstructed and verified as a subsequence of both inputs, and an exhaustive proof that no script shorter than D exists for small inputs.

188 verifier asserts, 27 in-page checks, 0 failures.

DEV Community