Myers diff algorithm

How git diff knows exactly which lines you changed

A diff tool compares an old file and a new file and lists the fewest lines to delete and insert to turn one into the other. Eugene Myers's 1986 algorithm finds such a shortest list quickly.

The key is the longest common subsequence: the longest list of lines found in both files in the same order, not always adjacent. Those lines are kept; every other old line is deleted and every other new line inserted.

Example: old lines A B C A B B A and new lines C B A B A C share C A B A in order, four lines. So the shortest diff deletes 3 lines and inserts 2.

Myers diff algorithm

The red and green lines in a git diff

Git uses Myers's algorithm as its default for git diff. The red lines starting with − are deletions, and the green lines starting with + are insertions.

If you change one word in a line, git shows the whole old line in red and the new line in green. Diff works on whole lines, so an edited line counts as one deletion plus one insertion.

Myers diff algorithm

It tries zero edits, then one, then two, and stops at the first fit

Put old lines down a grid's side and new lines along its top. A step right inserts a line and a step down deletes one, each costing 1; where lines match, a diagonal step is free. The shortest diff is the cheapest path across.

Myers searches by cost: first every point reachable with 0 edits, then 1, then 2. At each cost it slides as far as possible along free diagonals. The first time a path reaches the corner, it has the fewest edits.

Because it stops at the first cost that works, the time is about O((N+M)·D). For two big files with a small change, D is tiny, so it is fast. Comparing every line with every other line would cost N·M.