Why Does GNU diff Take 150 Seconds on 10 GB? — What the Source Shows: It Reads Everything Before Comparing, While GNU grep Streams

Comparing two 10 GB text files (about 100 million lines each), GNU diff took 150.93 seconds and uvd, the CLI of UwDiff that I develop, took 21.23 seconds. They used 17.23 GiB and 0.41 GiB of memory.

GNU grep, on the other hand, runs at the speed of the storage, just like my uvf (the search command of UwView).

Both are GNU tools, so why does only diff slow down on large files? Instead of guessing, I read the source code of GNU diff and GNU grep.

The short answer: GNU diff reads both files into memory, then walks every line several times. GNU grep streams without splitting into lines, almost exactly like uvf

• GNU diff reads the old and new files completely into memory first, builds a hash table of every line, and runs the Myers algorithm over all lines at once. Comparison cannot start until reading has finished, and it walks large tables proportional to the line count several times.
• uvd compares while streaming both files 8 MB at a time. While lines are identical it only checks hashes and moves on; it builds tables only in a window around each difference and runs Myers only over short stretches.
• GNU grep searches each buffer without splitting it into lines, cuts out the line only after a match, and counts line numbers only when it matches. This is the same idea as uvf; both do very little work per byte, so storage speed decides how fast they go.

The gap comes less from how clever the algorithm is and more from the design: read everything, then start, versus advance while reading.

What I read

• GNU diffutils: src/io.c (reading and line hashing), src/analyze.c (the comparison flow) and gnulib’s lib/diffseq.h (the Myers algorithm itself)
• GNU grep: src/grep.c (reading and line handling), src/kwset.c (fixed-string search), src/kwsearch.c and src/dfasearch.c (regular expressions)
• Version: the development branch of the unofficial GitHub mirrors (gnu-mirror-unofficial/diffutils, grep). The files above are built the same way as GNU diff 3.12, which I used for the measurements.
• My own code for comparison: UwDiff’s TextDiffEngine, Myers and Hashing, and UwView’s RawGrep (the uvf search)

The GNU sources are GPL. This article only describes how they work; no code is copied.

First, the measurements: the gap widens as files grow

Same MacBook Air (Apple M4, 10 cores, 32 GB memory), external SSD, same test data, cache cleared before each single run (sudo purge). Text compared in line order, in the diff -u format.

uvd grows almost in proportion to size and its memory stays around 0.4 GiB. GNU diff’s memory grows with size, and its time jumps 3.7× from 5 GB to 10 GB.

All tables and the method are on the UwDiff benchmarks page.

What happens inside GNU diff

When you run diff old new, GNU diff goes through these steps.

1. Read both files completely (slurp in io.c). For a regular file it allocates memory for the whole file and reads to the end.
2. Trim the common start and end (find_identical_ends). In memory, it compares several bytes at a time and removes what is identical at the start and at the end. This is fast, but if the files differ from the first line, nothing can be trimmed.
3. Hash every line into one table shared by both files (find_and_hash_each_line). With a hash computed one byte at a time, every line goes into a single hash table, and identical lines get the same number (an equivalence class). An array pointing to the start of every line is built too.
4. Set aside lines the other file does not have (discard_confusing_lines in analyze.c). A line that exists on only one side must be an addition or a deletion, so it is left out of the main comparison. This also walks the arrays for all lines.
5. Compare all remaining lines in one Myers divide-and-conquer (compareseq in diffseq.h). It extends diagonals from both ends, finds where they meet in the middle, and recurses. If it gets too expensive, it stops at a point that is not optimal (unless --minimal is given). Its working arrays are also sized by the line count.
6. Shift change boundaries to read better (shift_boundaries), then build and print the script.

Each step starts only after the previous one has finished. While reading from storage nothing is compared, and while comparing nothing is read. Steps 2 to 6 all work on arrays proportional to the line count (about 100 million lines × 2 at 10 GB).

What the design tells us, and what it does not

From the source, we can say:

• Just reading two 10 GB files takes around 20 seconds on this external SSD. GNU diff does not start comparing until that is done, so however fast the comparison is, the total is “read time plus compare time”.
• It builds hash tables and arrays for every line of both files, so memory grows with the line count. The measured memory (3.15 GiB at 1 GB, 17.23 GiB at 10 GB) has that shape.
• At 100 million lines, the shared hash table is written all over the place.

What I did not measure is how long each step takes (no profiling). The 3.7× jump from 5 GB to 10 GB coincides with memory use approaching the machine’s 32 GB, but I am not claiming that as the cause.

What happens inside uvd

uvd (UwDiff’s text comparison) uses the same Myers algorithm as GNU diff, but applies it differently.

1. Each file is read 8 MB at a time by its own thread, split into lines, and each line gets a hash computed 16 bytes at a time.
2. The comparing thread simply advances while the hashes match, and drops lines it has finished with.
3. When a difference appears, it widens a window around it and, using lines that appear exactly once in both the old and the new window as anchors, decides where the files line up again.
4. Only the short stretch up to that point goes through Myers to find the minimal diff.
5. When one file ends, the rest becomes one block of additions or deletions.

Two reading threads and one comparing thread run at the same time, so the total is close to “read time plus a little”. Hash tables exist only in windows around differences, so their size depends on how much differs, not on how big the files are.

Where GNU diff is the better fit

Because uvd decides where to line up using anchors inside a window, its diff is not always minimal. On test data where lines were reordered in small blocks, uvd’s diff was 0.5% longer than GNU diff’s (both are correct: applying either to the old file reproduces the new file byte for byte).

If the files fit comfortably in memory, the changes are large, and you need the minimal diff (diff --minimal), GNU diff’s design is the right one. uvd gives up a little minimality in exchange for comparing while reading.

Why GNU grep stays fast: it is built almost like uvf

Reading GNU grep, its design turned out to look not like uvd but almost exactly like uvf (UwView’s search).

Both follow the same principles: do not split the buffer into lines, do not look at newlines until there is a match, and count line numbers afterwards. With so little work per byte, the CPU has headroom and storage speed decides the result.

On a 258 GB file (4.5 billion lines), GNU grep took 273.66 seconds. Just reading the file once with wc -l took 268.49 seconds, so that is +1.9% (the 258 GB article). uvf searches 50 GB in 50.82 seconds, 962 MB/s (the article on making uvf single-pass). These were measured on different days with different files, so I do not compare the seconds, but both reach about 0.96 GB/s, which is the read speed itself.

Same GNU, so why is only diff like this?

What the source shows is a difference in the shape of the problem.

• grep only needs to read one file once, front to back. It never has to remember earlier lines, so streaming is the natural design from the start, and it keeps up with today’s SSDs.
• diff looks for the minimal difference between two files. The Myers algorithm (published in 1986) assumes you can look anywhere in both sequences. When files fitting in memory was a given, reading everything and numbering every line made sense. GNU diff’s later improvements (trimming the common start and end, setting aside lines the other side lacks, stopping when it gets too expensive) all make in-memory array processing faster; none of them turns it into comparing while reading.

uvd assumes that “the two files you diff are usually very similar”, gives up a little minimality, and rebuilds diff in the same streaming shape as grep. The gap, 3.5× at 1 GB, widens to 7.1× at 10 GB because this design difference matters more as files grow.

Ideas uvd could borrow

There are also things to learn from GNU diff. They are not in uvd today; I am noting them as ideas to consider.

• Advance over identical leading bytes without splitting into lines: the equivalent of GNU diff’s common-prefix trimming. uvd still splits and hashes lines while they are identical, so when differences are only near the end there is work to save (though while storage speed is the limit, it may not help much).
• Set aside lines the other side lacks before Myers: this could shrink the stretch passed to Myers when a difference window is large.

Try it

# macOS (Homebrew)
brew install --cask amru195704/uwview/uwdiff

# Windows (Scoop)
scoop bucket add uwview https://github.com/amru195704/scoop-uwview
scoop install uwdiff

# Linux (Snap)
sudo snap install uwdiff

uvd old.log new.log -o changes.diff   # a diff -u style diff, produced while reading

How to install Scoop itself and manual installation are on the download page.

Read next

• UwDiff benchmarks (with conditions, losses included) — every table against GNU diff, macOS diff, qsv and DuckDB at 1 GB, 5 GB and 10 GB
• Why can’t diff and grep compare so many files? — why I built UwDiff, and how a prototype confirmed the “read time plus a little” hunch
• Five questions against 258 GB and 4.5 billion lines — how close GNU grep, ripgrep and BSD grep get to storage speed
• UwView, the sister tool — open a huge log and search it like grep

From the developer: apps, Kindle books and public projects are listed on GitHub: amru195704.