The Regex That Hangs: Catastrophic Backtracking, Measured Across Five Engines
Twenty-eight a's and a b. Python's re module needs 16.5 seconds to say no. grep -P gives up and errors out. ripgrep answers in about two milliseconds. Same pattern, same input, three fates — and the fix is one character.
Written November 8, 2026 · Tested with Python 3.12.3 · 15 min read
- The cliff, in one table
- grep -P never hangs. It errors out.
- The one-character fix
- It is not just the textbook case
What this tutorial measures
The pattern is (a+)+$ and the input is 'a' repeated n times, then a 'b'. The $ can never match in front of that 'b', so the answer is always no — the only question is what each engine pays to find that out. The pattern is the canonical textbook case: a group that repeats, inside a repetition. A run of n a's can be split into groups in 2^(n-1) ways, and a backtracking engine that has to try every split before conceding does exponential work. At n=28 that is 2^27, about 134 million splits.
Five engines ran the same pattern against the same files on one box: Python 3.12.3 re, GNU grep 3.11 with -P (PCRE2 10.42), GNU grep with -E, ripgrep 14.1.0, and a small Rust program built on the regex crate 1.13.1. Each cell is the median of three runs with a 20 second timeout, timed from the outside, so the numbers include process startup. The two runs agree within a few percent on every cell that matters.
The cliff, in one table
Non-match (a+)+$ on 'a'×n + 'b', milliseconds, median of 3:
| n | grep -P | grep -E | ripgrep | Python re | Rust regex |
|---|---|---|---|---|---|
| 12 | 2.4 | 2.3 | 2.3 | 20.2 | 1.5 |
| 16 | 2.8 | 2.4 | 2.5 | 24.1 | 1.3 |
| 20 | 7.8 | 2.3 | 2.3 | 86.3 | 1.3 |
| 22 | 21.9 | 2.1 | 2.1 | 275.8 | 1.4 |
| 24 | 13.7 | 2.4 | 2.1 | 1,076.3 | 1.6 |
| 26 | 14.4 | 2.4 | 2.5 | 4,183.1 | 1.2 |
| 28 | 14.3 | 2.4 | 2.4 | 16,543.6 | 1.5 |
Python re roughly quadruples with every two added a's: 86.3 ms at n=20, 275.8 at n=22, 1,076.3 at n=24, 4,183.1 at n=26, 16,543.6 at n=28. The ratios per step are 3.20, 3.90, 3.89, and 3.95 — the doubling per added character, settling toward 4x per two characters as the exponential term swamps the fixed startup cost. A single smoke run at n=29 took 33,329.8 ms, so the doubling continues past the table: 16.5 seconds at n=28, 33.3 at n=29. At n=30 the same curve predicts over a minute, and at n=40 it predicts hours. The Nov 7 run measured the same shape: 84.2 ms at n=20 rising to 16,645.9 ms at n=28, with a 34,212.3 ms smoke run at n=29.
Three engines do not move at all. Ripgrep stays between 2.1 and 2.5 ms, the Rust regex crate between 1.2 and 1.6 ms, and grep -E between 2.1 and 2.4 ms, from n=12 to n=28. The input grows and nothing changes, because these engines do not backtrack: the Rust regex crate docs state that all searches in the crate have worst-case O(m·n) time, where m is proportional to the size of the regex and n to the size of the string, and that the crate lacks look-around and backreferences precisely because they cannot be implemented efficiently. Ripgrep is built on the same crate, so its flat column is the same guarantee wearing a command-line interface.
grep -P never hangs. It errors out.
grep -P is the interesting middle case. It is a backtracking engine — PCRE2 — but it refuses to hang. Clean no-match answers (exit code 1, no error) through n=22, then from n=24 on it exits with code 2 and prints exceeded PCRE's backtracking limit to stderr, with wall time plateaued at about 14 ms:
n=20 rc=1 err=
n=22 rc=1 err=
n=24 rc=2 err=grep: in_24.txt: exceeded PCRE's backtracking limit
n=26 rc=2 err=grep: in_26.txt: exceeded PCRE's backtracking limit
n=28 rc=2 err=grep: in_28.txt: exceeded PCRE's backtracking limit
The threshold is the same on both runs: rc=1 through n=22, rc=2 from n=24. The mechanism is PCRE2's match limit. The pcre2api docs describe match_limit as a means of preventing PCRE2 from using up too many computing resources on patterns that are not going to match but have a very large number of possibilities in their search trees, and name nested unlimited repeats as the classic example. When the internal counter reaches the limit, pcre2_match() returns PCRE2_ERROR_MATCHLIMIT. The default limit is 10,000,000 steps, which is why the plateau sits near 14 ms rather than at some universal value: a build with a raised limit burns more CPU before erroring, and the plateau moves with it.
Two details in the table are worth reading as measured, not smoothed. At n=22, grep -P takes 21.9 ms, above the roughly 14 ms plateau — the transition zone where the limit is nearly tripped and the engine does almost the full 10 million steps without quite reaching them. At n=20 it takes 7.8 ms, already climbing. The plateau is not a speed; it is the cost of 10 million wasted steps.
The exit code matters more than the timing. Exit code 2 is an error, not a no-match. A script that tests grep -q as a boolean — 0 means found, anything else means not found — misreads a limit trip as "no match" and carries on with a wrong answer. The same failure mode exists wherever PCRE2 surfaces: PHP's preg_match returns false on a match-limit trip, which is also not the same as "no match". If a pattern can trip the limit, check the exit code or the error, not just the boolean.
The one-character fix
Add one + to make the inner quantifier possessive: (a++)+$. A possessive quantifier matches as much as possible and never gives anything back, so the engine cannot re-split the run of a's. The Python re docs state it plainly: possessive quantifiers "do not allow back-tracking when the expression following it fails to match", and they were added in Python 3.11. The fix, measured at the same n values:
| n | grep -P possessive | Python possessive | Python before → after |
|---|---|---|---|
| 24 | 2.4 | 20.9 | 1,076.3 → 20.9 (51x) |
| 26 | 2.3 | 20.6 | 4,183.1 → 20.6 (203x) |
| 28 | 2.5 | 20.4 | 16,543.6 → 20.4 (811x) |
At n=28, Python drops from 16,543.6 ms to 20.4 ms, an 811-fold improvement, and grep -P goes from an rc=2 error at 14.3 ms to a clean rc=1 no-match at 2.5 ms. The Nov 7 run measured the same fix at 849x (16,645.9 → 19.6 ms); the ratio moves a little run to run because the denominator is dominated by interpreter startup, but the cliff is gone in both runs either way.
One caution, from the Python docs themselves: possessive quantifiers change what a pattern can match, not just how fast it matches. a*+a fails on 'aaaa' where a*a matches, because the possessive a*+ takes all four a's and cannot give one back for the final a. Here the fix is safe — the failing input still fails, and the matching input still matches — because the inner repetition never needs to give anything back for the $ to hold. Use a possessive quantifier only where the inner repetition cannot need to give back; where it can, rewrite the pattern with a character class instead.
It is not just the textbook case
(a+)+$ is a pattern nobody writes in production, so the claim needs a second example shaped like something a real program does. The probe ran one: a naive words validator, ^(\w+\s?)*$, against words separated by spaces with a '!' at the end so the match fails. The shape is the one a hand-rolled tokenizer or input validator takes — a word, an optional space, repeated — and it has the same nested-quantifier structure, because \w+ can split a word at any point and \s? can take the space or leave it.
| Words (k) | Input length | Python re | grep -P | ripgrep |
|---|---|---|---|---|
| 8 | 25 | 19.7 | 2.4, rc=1 | 6.9 |
| 12 | 37 | 20.3 | 2.4, rc=1 | 6.9 |
| 16 | 49 | 33.3 | 3.7, rc=1 | 6.7 |
| 20 | 61 | 243.6 | 16.0, rc=2 | 7.5 |
| 24 | 73 | 3,676.3 | 14.8, rc=2 | 6.7 |
Same three fates, on a pattern shaped like real code. Python climbs from 19.7 ms at 8 words to 3,676.3 ms at 24 words — 15 times slower across the last four words alone — while ripgrep stays flat near 7 ms. grep -P answers cleanly through 16 words, then trips the same limit from 20 words on and plateaus near 15 ms. The possessive fix, ^(\w++\s?)*$, takes Python at 24 words from 3,676.3 ms to 19.9 ms, a 185-fold improvement, and grep -P back to a clean rc=1 at 2.3 ms. A single-run check confirms the verdicts: the un-fixed pattern reports match=False in 3,565.1 ms of engine time, the possessive one match=False in 0.1 ms.
Ripgrep's floor is higher here than in the canonical table — about 7 ms against about 2.3 ms — while staying flat across all five rows. That is reported as measured; the flatness is the claim, and the floor difference is not explained by this probe.
The control: matching input is fast everywhere
The cliff is a non-match phenomenon. On matching input — 'a'×28 with no trailing 'b' — every engine answers at its startup floor:
| Engine | (a+)+$ on matching 'a'×28 |
|---|---|
| grep -P | 2.4 ms |
| grep -E | 2.2 ms |
| ripgrep | 2.3 ms |
| Python re | 19.9 ms |
| Rust regex | 1.4 ms |
Python's 19.9 ms on a match that succeeds instantly is the interpreter startup floor, and it is the same floor under every Python cell in the tables above: the matching-input control and the n=12 non-match cell both read about 20 ms. The exponential part sits on top of that floor and is unaffected by it — 16.5 seconds against a 0.02 second floor. The same holds for the other engines: their 1.5 to 2.5 ms columns are mostly process startup, which is why the flat engines read as flat rather than as zero.
What this does not cover
The Python medians include about 20 ms of interpreter startup, verified by the matching-input control. The exponential claim does not depend on it, but do not quote 16,543.6 ms as pure matching time; about 20 ms of it is startup.
The roughly 14 ms grep -P plateau is this box's PCRE2 default match limit of 10,000,000 steps, not a universal constant. A build with a raised limit burns more CPU before erroring, and the threshold n moves with it. The n=22 cell at 21.9 ms sits above the plateau because the engine nearly trips the limit without reaching it; the table is reported as measured, not smoothed into a curve.
The canonical pattern is the textbook case, and the guide says so. The generality claim rests on the second example — a words-shaped pattern with the same nested structure — not on the canonical pattern alone. A quoted-string pattern, an email validator, or any other real-world shape was not measured here; each would need its own run before claiming the same numbers for it.
The n=29 figure, 33,329.8 ms, is a single smoke run, not a median of three. The n=28 figure is the median of three in both runs. Nothing past n=29 was executed.
FAQ
Why does Python take 16 seconds on 29 characters?
Because the engine tries every way to split 28 a's into groups before conceding, and there are 2^27 of those, about 134 million. Each added a' roughly doubles the work, so the time quadruples per two added characters. The input is tiny; the search tree is enormous.
Why is grep -P fast when it also backtracks?
It is not fast at the match — it gives up. PCRE2 counts matching steps and stops at 10,000,000 by default, returning an error instead of an answer. The roughly 14 ms plateau is the cost of those 10 million wasted steps, and the exit code 2 tells you no answer was produced.
Why are ripgrep and Rust regex flat?
They do not backtrack. The Rust regex crate guarantees worst-case O(m·n) time and gives up look-around and backreferences to keep that guarantee. Ripgrep is built on the same crate. A flat column across n is what a linear-time guarantee looks like in practice.
Does the possessive fix change what the pattern matches?
It can, in general. A possessive quantifier never gives back, so a pattern that needs the inner repetition to shrink in order to match will stop matching — the Python docs show a*+a failing on 'aaaa' where a*a matches. Here it is safe because the inner repetition never needs to give anything back for the $ to hold, and the matching-input control confirms the match still succeeds. Where the inner repetition might need to give back, rewrite with a character class instead of forcing a possessive quantifier.
Is grep -E always safe?
For this pattern, yes: flat at about 2.3 ms across the whole table. That is a measurement of this pattern on this input, not a guarantee about every extended regex. GNU grep's -E path does not backtrack the way PCRE2 does, but a pattern with backreferences or other constructs outside the linear fragment is a different measurement.
How do I know if my own pattern is vulnerable?
Feed it a failing input that grows by one character at a time and time it. If the time roughly doubles per added character, the pattern has a nested quantifier with overlapping splits, and the fix is a possessive quantifier, an atomic group, or a character class that removes the ambiguity. The test input must fail: on matching input every engine is fast, and a passing test hides the cliff entirely.
Related guides on this site
- mv Across Filesystems, Measured: One Rename or a Full Copy
- grep -F vs -E vs -P, Measured: Same Pattern, Three Engines, One Silent Trap
- Searching, Reading, and Rewriting Text: Twelve Measured Guides
- Measured Comparisons: 9 Guides From November 8, 2026
Sources
- Python, re — Regular expression operations — possessive quantifiers
*+,++,?+do not allow back-tracking when the following expression fails to match, added in version 3.11; thea*+aexample showing a possessive quantifier can change whether a pattern matches. - Rust, regex crate — all regex searches in the crate have worst-case O(m·n) time complexity; the crate lacks look-around and backreferences because they cannot be implemented efficiently.
- PCRE2, pcre2api —
match_limitprevents PCRE2 from using up too many resources on patterns with a very large number of possibilities in their search trees, naming nested unlimited repeats as the classic example; reaching the limit returnsPCRE2_ERROR_MATCHLIMIT; the default limit is 10,000,000. - Ancisoft, Slow Regular Expression Search in Python — the nearest existing measurement: a Python-only timing table for
(\w+)+.growing from about 0.001 seconds at n=10 to about 15 minutes at n=30; no grep -P, ripgrep, Rust, or possessive-fix comparison. - DevKitLab, Why Is My Regex So Slow? — the theory behind the cliff: 2^(n-1) splits for n characters, and the note that ripgrep and Go's regexp run linear-time automata while backtracking engines hang.
- Veldica, Deterministic Python Prose Tokenizer Library — the only other Veldica page that discusses regex in production code, on hand-written edge cases; the regex-adjacent page this guide follows up.
- Veldica, Pulling One Field Out of a Million JSON Lines: jq vs Python vs grep, Measured — the follow-up guide: the same grep -P engine extracting one JSON field, 4.28x faster than jq and 5.11x faster than Python on a million flat lines, and the nested-key trap that silently adds 1,000 lines per 100,000.
- The same failing input has three fates: Python re hangs exponentially, grep -P errors out at PCRE2's match limit, and the linear engines answer in about 2 ms flat.
- Python re on (a+)+$ goes from 86.3 ms at n=20 to 16,543.6 ms at n=28, roughly quadrupling per two added characters, and a single run at n=29 takes 33.3 seconds.
- grep -P's answer changes at n=24: clean rc=1 through n=22, then rc=2 with exceeded PCRE's backtracking limit and wall time plateaued near 14 ms. The threshold is the PCRE2 default match limit of 10,000,000 steps.
- One character fixes both backtracking engines: (a++)+$ takes Python at n=28 from 16,543.6 ms to 20.4 ms, 811x faster, and grep -P back to a clean rc=1.
- The cliff is a non-match phenomenon. On matching input every engine is fast, and Python's 19.9 ms there is interpreter startup, not matching.
Keep Exploring
Paste a [Service] section and get a plain-language verdict on every sandboxing setting it finds.
Paste sshd -G output and get a hardening verdict on the values your server actually runs.
Paste a server block and get WebSocket, TLS, HSTS, and proxy-header verdicts.
Paste a systemd timer expression and get the specific reason it fails, the normalized form, and the past-date traps the built-in check hides.
The full sysadmin hub \u2014 systemd, cgroups, file tools, and measured Linux comparisons.