A diff tool should limit work, not lines

Every online diff tool has a size limit, and almost all of them count lines. That guard is aimed at the wrong thing. A 20,000 line log diffs in 55 milliseconds. A 5,000 line file compared against the same 5,000 lines in a different order takes the best part of a second, and 10,000 of them takes three.

A line cap set anywhere useful refuses the first case and permits the second. It is measuring the input rather than the job.

Where the time actually goes

Myers' algorithm runs in roughly O((N + M) x D), where N and M are the numbers of lines and D is the size of the smallest edit script between them. D is the part nobody puts in a limit, and D is the part that varies by three orders of magnitude between two files of identical size.

Two versions of a config file with ten changed lines have a tiny D. The same file with its lines shuffled has a D close to N, because almost every line has to move. Both are 5,000 lines. One is instant.

Measured on node 24.15.0, 9 September 2026, three runs each on a machine that was busy with other work, which is why these are ranges rather than single numbers.

Look at rows two and four. The 20,000 line comparison is four times the input and roughly a twentieth of the time. Any cap that lets the fourth row through lets far worse through, and any cap that stops it stops the second row too.

Budget the work instead

D is not known in advance, but it is discovered as the search runs: the algorithm walks outward one edit distance at a time. So the guard can sit inside the loop and count what has actually been spent, which is (N + M) x D / 2 cells of the edit graph. Past a fixed budget, stop and say so.

With the budget at 32 million, the shuffled 5,000 line case stops about 60 milliseconds in and every realistic row in that table finishes untouched. The refusal is specific rather than generic, because by the time it fires the tool knows exactly what happened: the two texts share thousands of lines in a very different order, and sorting both before comparing will answer the question the person was actually asking.

A line cap is still worth having underneath, at 50,000 a side, because the parts of the work that are genuinely linear still have to be paid for. It is a floor, not the guard.

Two cheap wins before the algorithm runs

Peel the common prefix and suffix first, at every level of the recursion. Most real comparisons are two versions of the same document that agree at both ends, and the peeled part costs nothing to match.

Then drop the lines that appear on only one side, before matching. No common subsequence can contain a line the other text does not have, so they can be set aside and put back afterwards. On a file with a large inserted block this removes the block from the search entirely.

filetity is built by Adarsh Mishra. The timings above came off one busy laptop and are ranges for that reason; if you measure something different, that is useful rather than contradictory: support@filetity.com.