macOS grep Has No Multi-Pattern Automaton

The grep on macOS is not GNU grep:

$ grep --version
grep (BSD grep, GNU compatible) 2.6.0-FreeBSD

The two have completely different multi-pattern implementations.

GNU grep compiles the entire pattern set into one automaton and makes a single pass. Historically that was an algorithm close to Commentz-Walter, which is Aho-Corasick plus a Boyer-Moore skip table. That code was removed in January 2017 in favour of plain Aho-Corasick, because Commentz-Walter's O(mn) worst case was reachable in practice. Either way, adding patterns doesn't multiply the work.

So why did 1122 patterns cost 23 days? Because BSD grep has no such automaton. It reads a line, then evaluates the pattern set against it. With 1122 patterns and 1.23 billion lines that's a multiplication instead of a single pass, and 0.17 MB/s is roughly what it costs.

The FreeBSD wiki, on where bsdgrep's time goes:

the main bottleneck is not in the regex(3) implementation but in grep itself

The commit that made bsdgrep the FreeBSD default calls the slowdown against gnugrep

the price to pay for fewer bugs

before pointing anyone who needs speed at ripgrep.

I did not read the source, so the per-line mechanism is inference from documented behaviour rather than something I confirmed. The 0.17 MB/s is the measured part.

If you want GNU grep on a Mac, brew install grep installs it as ggrep.

Regardless of which grep you have, two things are worth ruling out:

• A dirty pattern file. An empty line matches every input line and disables all fast paths. CRLF endings silently append \r to every pattern. Check with grep -c '^$' ids.txt and file ids.txt.
• A short pattern. Any implementation that skips is bounded by the shortest pattern in the set, so one 3-character entry can dominate. Check with awk '{print length}' ids.txt | sort -n | head -5. All 1122 of mine were exactly 36.

What ripgrep Does Instead

ripgrep has neither problem, though the path from -F -f to a matcher has a layer I didn't expect. It doesn't hand the literals to a dedicated multi-pattern engine. It welds them into one enormous alternation and gives that to Rust's regex crate, which rg --trace will print back at you:

grep_regex::config: assembling HIR from 1122 fixed string literals
grep_regex::matcher: final regex: "(?:7faedcb6-90c3-4e9a-9c6f-e2fbf0b998e7)|(?:5fe23ef0-ef4b-...)|..."

The regex engine then decides for itself how to search for 1122 alternated literals, and one of the things it can reach for is aho-corasick, a Rust library by the same author. That crate offers several strategies, and going by its published selection rules, a set of this shape qualifies for none of the quick ones:

• A prefilter, which scans for one cheap byte and only wakes the automaton where that byte appears. It needs either three or fewer distinct first bytes across the whole set, or three bytes that appear in every pattern and are rare enough to be worth hunting for. Lowercase UUIDs start with any of 16 hex digits, and every byte they contain is a hex digit or a hyphen, so there is nothing rare to scan for.
• Teddy, a SIMD algorithm ported from Intel's Hyperscan that compares several patterns against a block of input at once. Per the crate's design notes it only works well below roughly 100 patterns. I had 1122.
• A full DFA, a deterministic finite automaton, where every input byte advances the machine by exactly one state via a single table lookup. It is the fastest of the automata but its transition table costs orders of magnitude more memory, so the crate only builds one when the pattern count is small.

That leaves the crate's default, a contiguous NFA: nondeterministic, so it may follow several failure transitions for a single input byte, but it packs all of them into one allocation and gets close to DFA speed for a fraction of the memory.

--trace shows the regex being assembled. It does not print which matcher the engine settled on, so the list above is the published selection criteria applied to my pattern set rather than a decision I watched get made.

Could the pattern set be reshaped to reach a fast path? Not usefully. Splitting 1122 patterns into twelve batches of under 100 would let Teddy engage, but that's twelve passes over 330 GB against one. The prefilter can't be helped at all, because the bytes that make UUIDs UUIDs are exactly the bytes that saturate an analytics export. A faster literal matcher wouldn't help either. The mawk version sidesteps the problem by hashing field 1 rather than scanning for literals.

So ripgrep was working without any of the accelerations, and still came in around 7 minutes. Aho-Corasick reads each byte of the input once and only once, however many patterns it is carrying. The literature calls the text being searched the haystack and each pattern a needle; the linked sources use those terms throughout.

macOS awk Costs 2.8 µs per Record

macOS ships the BWK "one true awk". I benchmarked the sample, cached, with wc -l on the end:

That 2.8 µs is flat per-record overhead, and you pay it before your program does anything: find the newline, copy the bytes into $0, evaluate, step the loop. Over 1.234 billion lines it was the entire runtime, and no change I made inside the program moved it.

Two things that made no difference under BSD awk: field splitting (-F, and substr differed by 0.5%) and locale (LC_ALL=C versus unset differed by 0.8%). Both are real costs, but they're invisible next to 2.8 µs.

Field Splitting Costs 113 ns per Line

The BSD awk table above suggests field splitting costs nothing. It doesn't generalize. Under mawk, on the full file:

140 seconds over 1.234 billion lines, about 113 ns per line.

Why would naming a field cost anything, when the record is already in memory? Because awk splits fields lazily, on first reference. The moment you touch $1, awk has to scan the entire record, including that ~250-character quoted user agent, and allocate all eight field strings, only to read the first one. substr($0,1,36) reads 36 bytes and stops. Referencing only $0 means the record is never tokenized at all.

Field splitting was 4% of BSD awk's runtime and 64% of mawk's.

Quoted Fields Break awk -F,

awk -F, doesn't understand quoting. One comma inside "Mozilla/5.0 (KHTML, like Gecko)" shifts every subsequent field index on that row, and different user agents shift by different amounts. You get wrong data, not an error.

Fields before the first quoted column are safe. $NF is safe if nothing after the last quoted column contains commas. Everything in between isn't.

Detect it in one pass:

awk -F, 'NF!=31{n++} END{print n+0}' file.csv

Zero means -F, is correct for the entire file, and you're done. If it isn't zero, here are the options in increasing order of correctness and cost:

Count from the right, when only one column can contain commas:

awk -F, '{print $NF, $(NF-3)}'

gawk 5.3 or newer handles this natively with --csv (or -k), which takes RFC 4180 as its spec: quoted commas, doubled quotes, and newlines inside quoted fields. It overrides FS, FPAT, FIELDWIDTHS and RS entirely, and warns if you assign to any of them:

gawk --csv '{print $18,$1,$29}'

Kernighan added the same flag to the one true awk in 2023 and gawk followed to match, so the awk already on your Mac may support it. Check with awk --version.

gawk with FPAT, if you're on gawk older than 5.3. This gives true field positions, but quoted fields arrive with their quotes intact, embedded newlines still defeat it, and it's several times slower than plain splitting:

gawk -v FPAT='([^,]*)|("([^"]|"")*")' '{print $18,$1,$29}'

A real parser, the fallback when neither awk is new enough. Expect 0.5-1M lines/sec:

python3 -c '
import csv, sys
r = csv.reader(sys.stdin); w = csv.writer(sys.stdout)
h = next(r); idx = [h.index(c) for c in ("center_id","user_id","viewing_type")]
w.writerow([h[j] for j in idx])
for row in r: w.writerow([row[j] for j in idx])
'

Looking columns up by header name also means the code survives a schema change.

The Filter Eats the Header Row

The filter discards the header along with every other non-matching line. Peel it off the front of the stream and print it before the filter runs:

pigz -dc big.csv.gz | { IFS= read -r h; printf '%s\n' "$h"; grep -F -f pats.txt; } | pigz > out.gz

read consumes exactly one line from the shared stdin, then the filter picks up from line 2. IFS= keeps leading and trailing whitespace in the header intact, and -r stops backslashes being interpreted as escapes.

The FNR==1|| in the mawk pipeline earlier does the same job inside awk. This form is for when the filter is grep or ripgrep and has no notion of a record number.

Run Every Benchmark Twice

My first mawk timing was 0.483s wall / 0.088s user. The repeat was 0.071s / 0.058s. The first number was process startup and cold cache. The tell was that every other command's CPU time tracked its wall time closely and mawk's didn't.

Had I stopped at the first run, 0.483s would have put mawk behind ripgrep's 0.272s, and I'd have built the pipeline around an rg prefilter. At 0.071s mawk is faster than pigz can feed it and the prefilter is pure overhead.

Cached Samples Over-Predict by ~1.5x

Same awk, same expression, three contexts:

A read from a pipe is bounded by the kernel's pipe buffer, and on macOS that buffer is not one size. XNU picks from a ladder of 512, 1024, 2048, 4096, 8192, 16384 and 65536 bytes. A fresh pipe starts at the bottom rung, 512 bytes, and each write that won't fit in the free space bumps it to the smallest rung that will hold the backlog plus the incoming write, capped at 65536 and at a 16 MB system-wide budget. That's choose_pipespace in bsd/kern/sys_pipe.c; the constants live in bsd/sys/pipe.h. pigz writes in large blocks, so this pipe would have reached the top rung on the first write or two. Linux is a flat 64 KiB, per pipe(7).

A read from a file already in page cache has no such bound and never blocks waiting on another process. The buffer sizes are documented; attributing the 1.34x to them is my inference and I didn't instrument it. They do rule out one alternative: the 20 GiB run showed user 5m19s / real 5m05s, one core pinned on awk with pigz barely registering, so cores weren't being contended for.

Rule of thumb: multiply a cached-sample estimate by ~1.5, and run a short in-pipeline version before committing to a multi-hour job.

time pigz -dc big.csv.gz | head -c $((20*1024**3)) | your-filter-here | pigz -p 8 > /dev/null

Check the Sample Is Representative, for the Property You Care About

My sample was the leading 200 MiB, taken with head -c. For line length it was excellent:

wc -l < /tmp/sample.bin    # divide the byte count by this

267.2 bytes/line projects 1.234 billion lines for the whole file, against the 1.2 billion I'd estimated separately.

For match rate the same sample was worthless. 7794 of its 784,857 lines matched, or 0.99%. The finished output has 159,814,097 lines against ~1.234 billion in, which is 13%. The sample was low by a factor of thirteen.

The reason is that the file is ordered by field 1, so a slice off the front covers only the centre IDs that sort earliest. Confirm it on your own data before trusting a leading slice for anything density-related:

pigz -dc big.csv.gz | head -c $((200*1024*1024)) | cut -d, -f1 | sort -u | wc -l

A handful of distinct values means the file is sorted, and the head of it covers a narrow slice. Sample size wasn't the problem here; a 2 GiB slice off the same end would have been wrong by the same factor.

gzip -l Lies About Anything Over 4 GiB

Checking the finished output:

$ gunzip -l lc-camera_stream_views_july_2026.csv.gz
  compressed uncompressed  ratio uncompressed_name
  1390818770   1279017005  -8.8% lc-camera_stream_views_july_2026.csv

A negative ratio says compressing made the file bigger, which gzip does not do to CSV. The format stores the uncompressed size in a four-byte trailer field, so anything at or above 4 GiB is recorded modulo 2^32, and gzip -l reports that wrapped value back without comment.

The real size was 44,228,689,965 bytes, which is the reported 1,279,017,005 plus ten full wraps. That works out to 31.8:1, in line with the source file's 30:1 rather than the impossible -8.8%.

The only reliable answer is to decompress and count:

pigz -dc big.csv.gz | wc -c

At 2.33 GB/s that costs about a minute for 44 GB, and it is the same command that gives you the decompression floor.

The Decompression Floor: 2.33 GB/s

pigz -dc measured 2.33 GB/s on this file:

time pigz -dc analytics.csv.gz | wc -c
# 329691473398
# real 2m21.693s

pigz can't parallelize decompression of a single gzip stream. It was fast here because a 30:1 compression ratio decoded mostly as long back-references. -p 8 still matters on the compression side. The filter emitted 44.2 GB over the 3m40s run, so the output stage was fed at roughly 200 MB/s, well past the 30-50 MB/s a single-threaded gzip manages.

At 2.33 GB/s, ripgrep at 771 MB/s was never decompression-bound: its full-run rate of 785 MB/s matched its sample rate almost exactly. mawk at 2954 MB/s was faster than the decompressor, which made it the only tool here that was floor-bound. The 3m40s against a 2m22s floor was pipe and syscall overhead, not matching.