How to diff two huge files in a browser

The diff algorithm in every textbook needs a table with one cell per pair of lines, which is why so many online diff tools quietly give up in the low thousands. This is what goes wrong, how Myers’ O(ND) algorithm fixes it in linear space, how to compare two multi-gigabyte binary files in constant memory — and the bit-level reading that tells you what kind of edit you are looking at.

Why the obvious algorithm runs out of memory

A diff is a longest common subsequence problem. Given two sequences of lines, find the longest ordered set of lines they share; everything not in it was inserted or deleted. The textbook solution is dynamic programming: build a table dp[i][j] holding the LCS length of the suffixes starting at i and j, fill it from the bottom-right, then walk back to recover the alignment.

It is correct, it is easy to write, and it is O(n·m) in both time and space. That second one is the problem. Two 3,000-line files need nine million cells — 18 MB as 16-bit integers, which is fine. Two 30,000-line files need nine hundred million — 1.8 GB, which is not. The cost does not care whether the files are nearly identical or completely unrelated; it depends only on how big they are.

That is exactly backwards. The diffs people actually run are between two versions of the same thing, and they differ in a handful of places. An algorithm whose cost tracks the size of the input, rather than the size of the change, is doing enormously more work than the answer requires.

Myers: walk the edit graph, not the table

Eugene Myers’ 1986 paper reframes the problem. Draw a grid with sequence A along the top and B down the side. You start at the top-left and must reach the bottom-right. Moving right deletes a line from A; moving down inserts a line from B; and where A[x] === B[y] you may move diagonally for free — that is a matched line. The shortest path from corner to corner, counting only the non-free moves, is the minimum edit script. Its length is called D.

The insight is to search by increasing D. For D = 0, how far can you get with no edits at all? For D = 1, one edit? The frontier at each step is stored per diagonal k = x - y, and there are only 2D+1 diagonals reachable in D moves — so the whole frontier is one array of length O(D), not a table of size O(n·m).

// One step of the forward frontier. v[k] is the furthest x reached on
// diagonal k. Extending a diagonal is free, so after stepping we slide
// along every matching line we can — that slide is the "snake".
for (let k = -d; k <= d; k += 2) {
  // Come from whichever neighbour got further: down (k+1) or right (k-1).
  let x = (k === -d || (k !== d && v[k - 1] < v[k + 1]))
    ? v[k + 1]        // moved down from the diagonal above
    : v[k - 1] + 1;   // moved right from the diagonal below
  let y = x - k;
  while (x < n && y < m && A[x] === B[y]) { x++; y++; }  // the snake
  v[k] = x;
  if (x >= n && y >= m) return d;  // reached the far corner in d edits
}

Time is O((n+m)·D). For two files that differ in ten lines, D is about twenty and this finishes before you can measure it — regardless of whether the files are a thousand lines or a million. The cost has moved from the size of the input to the size of the change, which is where it belonged.

A practical note: compare integers, not strings. Hash each distinct line to a small integer once, up front, and the inner loop compares numbers instead of walking characters. This is also the natural place to apply the ignore options — two lines that normalise to the same text get the same integer and are therefore equal, at no extra cost in the loop.

The linear-space refinement

Finding D is O(D) space, but recovering the actual edit script naively means keeping every frontier, which is O(D²). Myers’ refinement removes that too. Run the search from both ends at once — a forward frontier from the top-left and a reverse frontier from the bottom-right. The first time they overlap, the point where they meet lies on some shortest path. Split the problem there and recurse on the two halves.

// Sketch. Each half is an independent, smaller diff; the recursion
// depth is logarithmic and only two frontier arrays are ever live.
function diff(A, aLo, aHi, B, bLo, bHi, out) {
  // Peel the common prefix and suffix first — cheap, and it is what makes
  // an append-only change cost almost nothing.
  while (aLo < aHi && bLo < bHi && A[aLo] === B[bLo]) { aLo++; bLo++; }
  while (aHi > aLo && bHi > bLo && A[aHi - 1] === B[bHi - 1]) { aHi--; bHi--; }

  if (aLo === aHi) { out.push({ type: 'ins', bLo, bHi }); return; }
  if (bLo === bHi) { out.push({ type: 'del', aLo, aHi }); return; }

  const { x, y } = middleSnake(A, aLo, aHi, B, bLo, bHi);
  diff(A, aLo, x, B, bLo, y, out);
  diff(A, x, aHi, B, y, bHi, out);
}

Two details matter in practice and are easy to get wrong.

First, drive it from an explicit stack, not the call stack. Two hundred thousand lines can nest deeper than the engine’s frame limit, and a stack overflow inside a Web Worker is not an error message — it is a tab that never finishes. Push the pieces of each window in reverse order (suffix, right half, left half, prefix) and they pop out in document order with no post-sort.

Second, if you reuse the two frontier arrays across every recursive call — and you should, allocating a fresh pair per call is what makes a naive linear-space implementation slower than the table it replaced — reset a wide enough band. The overlap test reads the opposite frontier at diagonal delta - k, where delta = n - m. For a lopsided window (one side more than three times the other) that diagonal falls outside the ±D range the loops walk. Leave it unreset and the test reads a live-looking value from a previous call, splits the window at a point no path goes through, and makes no progress — an infinite loop rather than a wrong answer. Clear max(D, |delta|) either side of centre.

Finally, give the search a work budget. D is small for two related files and enormous for two unrelated ones of the same size, where the algorithm would spend a very long time proving they have nothing in common. Past the budget, report that region as a wholesale replacement — which is the honest answer anyway.

From an edit script to a side-by-side view

Myers gives you a sequence of equal, delete and insert runs. A side-by-side view wants something slightly different: an edited line should sit opposite the line it replaced, not appear as an unrelated deletion and an insertion several rows apart.

The transformation is small. Buffer consecutive deletions and insertions instead of emitting them immediately; when the run ends, pair them up. The first k = min(deletions, insertions) form changed rows, left against right. Whatever is left over on the longer side becomes plain deletions or additions, with the opposite cell rendered as a muted blank so the eye tracks the gap rather than reading the next line as if it were opposite.

The same row list drives the unified view and the exported patch. Unified is one column with - and + markers, where a changed row is simply a deletion followed by an insertion — which is exactly how the format encodes it. For a real .patch, grow each changed row into a window of three context lines, merge the windows that touch (otherwise two edits four lines apart emit two hunks with duplicated context between them), and write a @@ -start,count +start,count @@ header per merged group.

Word-level highlighting

A whole line painted red says something changed on it. Marking the words that moved says what. And it needs no new algorithm — it is the same diff on a smaller alphabet.

// Tokenise so that punctuation and whitespace are their own tokens: they
// are real differences, but they must not glue two words into one.
const tokenize = (line) => line.match(/[\p{L}\p{N}_]+|\s+|[^\p{L}\p{N}_\s]/gu) ?? [];

// Then run the same Myers diff over the token ids and merge adjacent
// segments that share a changed/unchanged flag.

Two guards keep it cheap. Only refine rows already classified as changed — an equal row has nothing to mark — and skip refinement past a few hundred tokens, because a single minified line of 100 KB costs far more than the row is worth. Treat those as wholly changed and move on.

Ignoring what you meant to ignore

Most of the noise in a real diff is not a change anyone made on purpose: a re-indentation, a converted tab, a trailing space, a capitalisation pass. The rule that keeps these options honest is that they normalise the comparison key only. The rendered row always shows the real bytes of the file.

“Ignore whitespace” deserves one caution: collapse runs of spaces and tabs to a single space and trim the ends — do not strip whitespace entirely. Stripping it makes a b equal ab, which is a different and wrong claim.

“Ignore blank lines” is the awkward one, because a blank line still has to be displayed. Hold blank lines out of the sequences before diffing, remembering their original indices, and re-insert them as context rows afterwards, zipping the two sides’ pending blanks together. Added spacing then stops being reported as an edit while every real line of both files stays on screen.

Binary: a comparison that never buffers

None of the above applies to two files that are not text. There are no lines, an LCS of bytes is meaningless at scale, and the interesting question is different: which bytes differ, where, and by how much?

That question has a much better answer, because it can be computed honestly in constant memory. Read both files in lockstep, a block at a time; fold each pair of blocks into counters; throw the blocks away.

for (let off = 0; off < common; off += BLOCK) {
  const end = Math.min(common, off + BLOCK);
  // Both reads issued together so the two files stream in parallel.
  const [ab, bb] = await Promise.all([
    fileA.slice(off, end).arrayBuffer(),
    fileB.slice(off, end).arrayBuffer(),
  ]);
  fold(state, new Uint8Array(ab), new Uint8Array(bb), off);
  // …and that is it. Both blocks are unreachable after this line.
}

What the fold keeps is fixed in size no matter how big the files are: counts of differing bytes and bits, the first and last differing offset, a run list (maximal spans of consecutive differing bytes, which is what next/previous-difference navigation walks), and a density map of a fixed 1,024 buckets so you can see at a glance whether the changes cluster or are scattered. Peak memory is two blocks. Two 20 GB disk images compare on a laptop.

The property to test for is block invariance: the numbers must be identical whether you fold the files in one piece or a byte at a time. The trap is a run that straddles a block boundary — carry the open run across the fold, or a single differing region gets reported as two. That test is the whole basis of the constant-memory claim; if the block size can change the answer, the claim is false.

Displaying it uses the same trick as the rest of a large-file viewer: the hex view is windowed. Size a spacer element to the full row count, and on each scroll slice only the rows on screen out of both files. Nothing but the visible rows is ever in the DOM or in memory.

The bit-plane histogram

Here is where a byte comparison can say something a hex dump cannot. A byte can differ in eight ways at once, and which of the eight moved is information. So count the Hamming distance — differing bits, not bytes — and break it down by bit position.

const x = a[i] ^ b[i];
if (x !== 0) {
  diffBytes++;
  diffBits += POPCOUNT[x];
  // Which planes moved. Runs only on differing bytes, so it is nearly free.
  for (let bit = 0; bit < 8; bit++) if (x & (1 << bit)) bitCounts[bit]++;
}

The shape of that histogram identifies the kind of edit:

• One flip per changed byte, all in bit 0. Least-significant-bit steganography: data hidden in the quietest bit of many samples, where it shifts a pixel or an audio sample by an amount nobody can perceive. Nothing else looks like this.
• One flip per changed byte, all in one higher plane. A single bit plane was rewritten.
• Bits spread across all eight planes. Whole values were rewritten — a real change to the data in that region.

The file size carries a second, stronger signal, and it costs nothing to read. If two files differ yet are byte-for-byte the same length, almost nothing benign explains it: re-saving a file picks its own size and essentially never lands on the original exactly. An identical size plus a scatter of changed bytes means something was rewritten in place, inside the structure the file already had.

OmniViewer’s own /png/secret is a clean demonstration. It hides a message in a PNG by choosing between equally short back-references in the DEFLATE stream — so the file size is identical, every decoded pixel is identical, and roughly 0.4% of the bytes differ. Drop the before and after into /diff/bin and the size line and the density map tell you what happened before you have read a single byte of hex.

Neither half is bounded any more

It is worth being precise about how each half of a diff tool scales, because the two halves are genuinely different problems with, as it turns out, the same answer.

The byte comparison streams, folds and discards; its memory does not depend on the input at all. 6.4 GB a side is measured, on a flat 35–49 MB heap.

The line comparison used to be bounded, and the reasoning looked sound: diffing by lines means decoding both files into strings and holding them, plus one row object per line of the result. Myers removes the quadratic space, but it does not make two multi-gigabyte files fit in memory. So the old engine read a 16 MB prefix of each side and said when it truncated.

The flaw in that argument is the word holding. You do not need the lines — you need to know which lines match, and a hash is enough for that. So each side is now indexed once, in parallel across a worker per chunk, into content-defined blocks of about 64 lines: a block ends at a line whose rolling hash over the previous eight lines has six low bits clear. Because that rule reads only content, inserting a line perturbs one block and the next boundary re-syncs the two files — rsync’s anchor trick, moved up from bytes to lines. What survives the pass is 24 bytes per block. Then Myers runs over the blocks, and only the stretches whose hashes disagree are read back and diffed exactly.

The result is that the cost tracks how different the files are rather than how big they are. Measured in headless Chromium against the shipped build, two 1.39 GB JSON exports with 70.8 million lines a side and two edits between them: both differences found in 6.3 seconds, at 454 MB/s across the pair — faster than one file streams, because the index pass runs a worker per chunk on both sides at once. The screen matches: the grid is windowed like the hex view, so the scrollbar spans all 70 million aligned rows while fifty-one of them are in the DOM and each row’s text is fetched as it is painted.

Memory is the number such claims usually fudge, so plainly: peak is about 240 MB for a 3.4 GB pair, and it is not flat. It scales with the index — 24 bytes per sixty-odd lines, plus the scratch space the alignment needs and then frees — never with the files, which are not resident at any point.

One thing is still refused, on purpose. If more than 40% of the blocks go unmatched and there is more than 64 MB of unmatched content, the two files are not versions of each other, and the line screen says so instead of grinding out millions of change rows — it points at the byte comparison, which has no such limit. A small pair that shares no line is still diffed exactly, because it can be: the refusal is about cost, not about difference.

That shape — window what you view, stream what you scan, hold only an index — is the same one every format on OmniViewer uses. The diff route just applies it to two files at once.

OmniViewer opens every file format in your browser — JSON, CSV, PDF, PNG, ZIP and more — powered by the same windowed engine as fastjsonviewer.com and hugecsv.com. The diff route is the one that takes two of them at once.