TopolearnKnowing what makes a search slow lets you search gigabytes in seconds instead of minutes.
GNU grep is fast because it avoids doing per-character regex work on most of the input:
- It extracts a required literal from the pattern (for
ERROR [0-9]+that'sERROR) and searches for it with a Boyer-Moore-style algorithm that can skip ahead several bytes at a time. Only candidate lines are checked by the full matcher. - The full matcher is a DFA built lazily from the regex: each input byte costs one table lookup, with no backtracking, so time is linear in the input size.
- It reads big blocks and doesn't split the input into lines before matching; it finds line boundaries only around matches.
Things that defeat this:
- Backreferences like
\(a*\)\1can't be expressed as a DFA, so grep falls back to a backtracking matcher which can be exponential. -Puses PCRE2 (with JIT), fast for typical patterns but backtracking, so pathological patterns can be very slow.- Multibyte locales can force slower paths for some constructs;
LC_ALL=Coften speeds up large ASCII searches. -iwith some locales, and patterns with no usable literal, also reduce the skipping.
For many fixed strings use -F -f patterns.txt: grep builds an Aho-Corasick-style matcher that searches for all of them in one pass. Avoid loops that run grep once per pattern over the same file.
Example
# 2 million lines of test data
seq 1 2000000 | sed 's/^/line /' > big.txt
time grep -c 'line 1999999' big.txt # literal: skips most bytes
time LC_ALL=C grep -c 'line 1999999' big.txt
# many fixed strings in one pass instead of a loop of greps
printf 'line 17\nline 42\nline 99\n' > wanted.txt
grep -cxF -f wanted.txt big.txt # 3
# backreference: no DFA possible, much slower on big inputs
time grep -cE '(1)\1' big.txtRemember
- grep searches for a required literal first, then confirms with a DFA
- Backreferences and -P fall back to backtracking
- Use -F -f file for many fixed strings in one pass
Watch out for
- Looping over a list of terms and running grep once per term on the same large file.