The Cost Is 6.5 Milliseconds per Pattern per Mebibyte

Whether this will bite you comes down to two numbers, how many patterns you have and how big the file is. I timed three pattern counts against three slice sizes of that file, twice each, on an Apple M5 running macOS 26.5.2 with BSD grep 2.6.0-FreeBSD:

Every cell is the mean of two runs, which were within a 5% spread at the smallest and a 0.5% spread at the largest. Multiply the pattern count by the mebibytes and then by 6.5 milliseconds, and you have the time. Eight of the nine sit within 5% of a flat rate over a span of 1600 in the product and 1440 in the time; only the smallest, at half a second, is further out, and that's start-up.

So the two figures to keep are that about 1500 pattern-mebibytes is ten seconds, and about 9000 is a minute. A 2 GiB file against 50 patterns is 102,400 of them, which is eleven minutes. My 1122 patterns against 330 GB were 353 million, which is 26 days, and from the two progress checks below I got 27 days and 29, independently of it.

If your own product is in the low hundreds, none of this matters and BSD grep is fine. The rest of this page is for everyone above that.

Every Line Against Every Pattern Is a Nested Loop Join

BSD grep reads a line, then evaluates the pattern set against it one pattern at a time: your lines on the outside, your patterns on the inside, which is a nested loop join. The comparison count is the Cartesian product of the two, and each of those comparisons has to scan the line it lands on, which is how a count of lines turns into a count of bytes and gives you the rate in the table above. All the slices I timed came out of one file, where the lines and the bytes rise together, so these runs don't separate the two; the per-comparison scan is the reason to expect bytes to be the factor that matters.

-f is only the usual way to hand grep a large set, not the trigger. Over the same 2 MiB, a hundred patterns as a hundred -e flags cost 1.20s where -f costs 1.21s, and folding them into one -E alternation is 1.6x faster at 0.75s, against the hundredth of a second GNU grep takes on that identical alternation. If you have a lot of patterns, how you spell them barely matters.

GNU grep compiles the pattern set into one automaton instead and makes a single pass, so adding patterns to it is nearly free. mawk loads them into a hash and looks up one substring per line, which arrives at the same place by a different route.

The same thing happens in DuckDB, where IN against a list of 1122 identifiers compiles to a hash join. Build one lookup structure and a row costs a single lookup however large the set is. Loop over the set instead and a row costs one comparison per entry, so the work is rows times entries, which is the multiplication in the table above.

The timings separate the two greps the same way. Over the same 128 MiB with a thousand patterns, BSD grep takes 13m56s where GNU grep takes 0.401s, 2084x faster, and ripgrep 0.171s, the 4887x on the image at the top. Their scaling separates them too: on that slice a hundred times the patterns costs BSD grep 96 times the time and GNU grep 3.2 times. mawk takes 0.045s whatever the pattern count.

Reach for ripgrep, Unless the Match Sits at a Known Position

Here are the three that will do this job at a usable speed, on the whole 330 GB with all 1122 patterns, decompressing with pigz and writing the same gzipped output through pigz -p 8, with the floor and the macOS default for scale:

The top bar is the floor, the time to decompress 330 GB and count the bytes, because everything under it has to do that too. All three matchers selected the same rows in the same order, so they differ only in how long they take: GNU grep's output and ripgrep's are byte-identical, and mawk's is those same bytes with one extra line at the top. Every rate here is this machine, this file, and this one month of data. Compare them with each other rather than with numbers from yours.

All three cost one brew install, so the choice is not about effort:

1. ripgrep, the one to reach for. brew install ripgrep, and it matches anywhere on the line the way grep does, so nothing about your patterns has to change. It carries an Aho-Corasick automaton, reads each input byte once however many patterns you hand it, and is 2.4x faster than GNU grep here. Pass -a: without it a stray byte sequence makes ripgrep decide the stream is binary and stop early, and a file that is quietly short is a worse outcome than a run that is slow.
2. mawk with a hash, if the match sits at a known position. Fastest of the three and the most restricted. The pipeline at the top loads the identifiers into the array p and tests substr($0,1,36) against it, so it matches field 1 exactly rather than the identifier anywhere on the line. That's stricter than grep and it was what I actually wanted; if your patterns can appear anywhere, this one doesn't apply to you. If they can't, you can say so by anchoring every pattern to ^uuid,. Anchoring is worth 1.06x to ripgrep and 2.31x to GNU grep, each against its own unanchored run, at this file's 12.6% match rate, and the GNU grep figure rises to 6.38x at a 1.5% match rate, because the sparser the matches, the bigger the gain; ripgrep stays between 1.06x and 1.08x throughout. mawk still finishes first, by 1.83x over anchored ripgrep and 2.04x over anchored GNU grep.
3. GNU grep, if you'd rather not learn another tool. brew install grep puts it at ggrep, the flags are the ones you're already typing, and your pipeline changes by one character. That costs you 2.4x against ripgrep, or 1.11x at this file's match rate if both are anchored. Where matches are sparser the anchored order flips: at a 1.5% match rate anchored GNU grep takes 2m54s against anchored ripgrep's 6m56s. Either way it finishes a job the default could not.

The greps drop your header row. A CSV header matches no pattern, so grep and rg throw it away, and that is the extra line mawk wrote: 83 bytes, twelve of them once gzipped. Both commands at the top put it back, by different means. mawk has a record number, so FNR==1|| prints line 1 whatever is on it. grep and ripgrep have no such notion, so the shell peels the line off the front of the stream instead: read takes exactly one line from the shared stdin and the filter picks up from line 2, with IFS= to keep the header's leading and trailing whitespace and -r to stop backslashes being read as escapes.

Three traps, all of them silent, and two are in ids.txt rather than in your data. One empty line in the pattern file matches every input line, so the filter quietly becomes cat: 7,794 matching lines in a 200 MiB sample became all 784,857. The tell runs the wrong way, because an empty pattern matches before any real work happens and the run gets faster, BSD grep going from 10.65s to 0.01s on a 2 MiB slice. A job that has been crawling and then suddenly finishes is the thing to be suspicious of. More empty lines change nothing, and neither does where they sit, so one stray newline at the end of ids.txt will do it.

CRLF line endings in the same file do the reverse. grep appends the carriage return to every pattern, so nothing matches and you get an empty file and exit status 1. That costs more than the real job, 14.30s against 10.65s on the same slice, because a line that matches lets grep stop trying patterns on it and a line that cannot match never does. ripgrep strips the carriage return and is unaffected. mawk is immune to the blank line, an empty string never equalling a 36-byte prefix, but not to the CRLF, where it writes your header and nothing else.

The third trap is in the data. All three matchers read a line at a time, so a newline inside a quoted field, which the CSV spec allows, splits one record across two lines and defeats them equally: the second line starts mid-record, and a byte offset lands on whatever happens to be there. This file has none, which is why substr($0,1,36) is safe on it. DuckDB's CSV reader counted 1,272,998,467 records where awk counted 1,272,998,467 lines, and two counts that match, one of them from a real parser, are how you know.

The Same Command Name Is a Different Program

This goes past grep, and it's the part that holds at any size: the name of a command tells you almost nothing about which program will run, and you can't reason about its speed until you know. sed, sort, date, find, tar, head -c and tr all differ between macOS and Linux, in flags and in performance, and inside an Alpine container most of them are busybox, which is a third implementation again. grep --version costs nothing and I should have run it first.

Fifteen Hours In, grep Had Written 2.7% of the Output

I started with pigz -dc | grep -F -f | pigz -p 8, which is what I'd typically use, and went to do something else. Four and a half hours later the output file was 11 MB and at fifteen hours 38 MB. I had no denominator for either until ripgrep finished the same filter in seven minutes: 0.8% and 2.7% of the finished output. The rows in that output sit 0.70% and 2.16% into the input, which is how far grep had actually reached, at 0.13 to 0.14 MB/s. From both checks I got about a month, so I killed it. Having something to compare against is what made stopping obvious rather than agonising.

Related

• Filtering a 330 GB Gzipped CSV, in full, the long version of this one: every matcher timed against the others, the awk field-splitting measurements, the correctness traps, and the benchmarks that misled me.
• Filtering a 330 GB CSV in DuckDB, for doing this more than once.
• Pitfalls Directing an AI Agent, for the analysis the extract was made for.
• FreeBSD made BSD grep the default in December 2020, replacing GNU grep for licensing reasons.