How git diff Works, Inside the Myers Algorithm

The first version of the Toolium Diff Checker used a naive line-by-line comparison: walk down both files in parallel, mark lines that differ. This produced obviously-wrong output for any case where a line was added or removed in the middle of a file - after the insertion, everything below it looked like it had changed even though nothing had. A user reported it as broken, and they were right. The fix was to reframe the problem as a longest common subsequence, which is the idea underneath every serious diff tool. This post explains why a naive diff fails, what git's Myers algorithm does instead, and which parts of that the Toolium tool actually implements.

The naive approach and why it breaks

Consider these two files:

File A:           File B:
line 1            line 1
line 2            inserted line
line 3            line 2
                  line 3

A naive parallel-walk diff says: line 1 matches line 1. Line 2 (A) does not match "inserted line" (B); mark as changed. Line 3 (A) does not match "line 2" (B); mark as changed. We have run out of A; mark "line 3" as added.

The result claims that two lines changed and one was added. The actual change was a single insertion. The naive diff is technically valid (the operations would transform A into B) but minimally informative.

The longest common subsequence problem

The Myers algorithm reframes diffing as a longest common subsequence (LCS) problem. Given two sequences, find the longest subsequence that appears in both, in the same order, possibly with gaps. The LCS for the example above is "line 1, line 2, line 3" - all three lines from A appear in B in the same order.

Once you have the LCS, the diff falls out: lines in the LCS are unchanged; lines in A but not in the LCS are deletions; lines in B but not in the LCS are insertions. For the example, the LCS spans all of A and three of the four B lines, so the only operation is an insertion of "inserted line" between lines 1 and 2.

Myers' algorithm (published in 1986) is the clever version: it walks an edit graph and runs in O(ND) time, where D is the size of the difference, so near-identical files are close to linear. The Toolium tool does not implement Myers. It fills the straightforward LCS table instead, which is O(N*M) in both time and space after identical prefixes and suffixes are trimmed off. That is slower in theory and perfectly fine for the inputs a browser tab sees. For huge inputs it gets slow, which is why the Toolium tool caps the work at four million cells, roughly a 2,000-by-2,000-line changed region, and refuses beyond that rather than hanging.

Why git diff produces the output it does

The Myers algorithm answers "what is the minimum set of operations to transform A into B." When you see a git diff with "+" lines (additions) and "-" lines (deletions), each line is part of the answer to that LCS question.

The "unified" format that git defaults to is just a presentation choice: instead of showing the LCS and marking insertions and deletions around it, git interleaves the changes inline with three lines of context above and below. This is more readable than the old "side by side" format for most code review use cases, which is why every modern diff tool has adopted it.

Word-level diff inside changed lines

For lines that are nearly identical between A and B - say, a single word changed - the line-level diff just shows them as one deletion and one addition, which makes it hard to spot the actual change. Better diff tools (and the Toolium Diff Checker) detect "near-matches" between deleted and added lines and run a word-level diff inside them, highlighting just the changed words.

The algorithm: after the line-level diff produces deletion/insertion pairs, look at each pair. If the two lines are similar enough by some metric (Levenshtein distance under a threshold, say), treat them as a "modification" and run the same LCS diff over the words inside them. The output then highlights only the changed words inside the otherwise-identical line, which is much easier to read.

This is the difference between "here are 100 lines that look the same except they are slightly different" and "here are the 50 specific words that changed."

Whitespace as a first-class problem

Whitespace is the most common cause of misleading diffs. A file converted from tabs to spaces has every line different, even though no content changed. A file with CRLF line endings compared to LF line endings has every line different. The Toolium tool has a "Ignore whitespace" toggle that normalizes leading/trailing whitespace before comparing, which usually removes false positives without hiding real changes.

Pro tip from years of code reviews: if a diff looks much larger than expected and the lines all look the same, it is almost always a whitespace or line-ending issue. The git config equivalent is git diff --ignore-all-space, which has saved me many minutes of squinting at suspicious diffs.

What the Toolium tool does

The Diff Checker takes two text inputs (left and right), runs the LCS diff described above, and shows a unified diff with color-coded additions (green), deletions (red), and unchanged context. Near-matches get word-level highlighting on top. Whitespace handling is toggleable. The output supports keyboard navigation - press up/down arrow to jump between changes.

For very large diffs, the algorithm slows down quadratically. The current cap before the tool warns is about 10,000 lines per side; beyond that, the diff might take a few seconds to compute and the rendering of so many lines can make the page sluggish.

When to use a diff tool vs git

git diff is more powerful for files under version control: it tracks renames, can show diffs across many commits, supports custom diff drivers for specific file types. The Toolium diff is for the case where you do not have files under version control: comparing two text blobs you pasted from different sources, two API responses, two configuration files from different servers, two versions of a document a coworker sent you.

For code review on GitHub or GitLab, use those platforms' built-in diff viewers. For ad-hoc comparison of text that does not have a git history, use a tool like this one.

Privacy

The comparison runs entirely in your browser. Both inputs stay on your machine; no upload. Sensitive code, configuration files with API keys, contract drafts - all safe to compare here.