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.

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 says the bottleneck is in grep itself rather than in the regex library. The commit that made bsdgrep the FreeBSD default states that it's slower than gnugrep, and recommends ripgrep to anyone needing more speed.

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.

Worth being precise about what I checked here. --trace shows the regex being assembled; it does not print which matcher the engine settled on. The list above is the documented selection criteria applied to my pattern set, not 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. The escape isn't a faster literal matcher; it's not doing literal matching at all, which is what the mawk version does by hashing one field.

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: 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.

awk splits fields lazily, on first reference. Touching $1 forces it 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. One repeat was the difference between those two conclusions.

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. On macOS that starts at 16 KiB and grows to 64 KiB for large writes (PIPE_SIZE and BIG_PIPE_SIZE in XNU's bsd/sys/pipe.h); on Linux it is 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.

That's the documented part. Attributing the 1.34x to it is my inference, not something I instrumented. What I can say from the numbers is where it isn't: the 20 GiB run showed user 5m19s / real 5m05s, one core pinned on awk with pigz barely registering, so it wasn't contention for cores.

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

Mine averaged 267.2 bytes/line against 267 for the whole file, and predicted 1.234 billion lines:

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

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, where single-threaded gzip caps out around 30-50 MB/s and would otherwise be the bottleneck.

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.