Performance Traps

Catastrophic backtracking, measured

^(a+)+$ against a string of a followed by one b is the textbook case. a+ can split the run in exponentially many ways, and the outer + retries every one of them before the anchor finally fails.

Python 3.13, re.search(r'^(a+)+$', 'a'*n + 'b'):

Node 24, /^(a+)+$/.test("a".repeat(n) + "b"):

Every extra character roughly doubles the work, so 40 characters is hours. A 30-character request body is enough to pin a CPU core, which is why this has a CVE class of its own, ReDoS.

How to fix it

import re
s = 'a' * 26 + 'b'
re.search(r'^(a+)+$', s)      # 1.47 s
re.search(r'^(?:a+)+$', s)    # 0.87 s, dropping the capture is not the fix
re.search(r'^a+$', s)         # 0.00 s, the quantifier is not nested
re.search(r'^(?>a+)+$', s)    # 0.00 s, atomic group, Python 3.11+

Dropping the capture group is not a fix. (?:a+)+ is still nested and still exponential.

What makes a pattern vulnerable

The signature is two quantifiers where the inner one can match the same text more than one way, followed by something that can fail.

This classic email validator ships in real code and is exponential. Python, input 'a'*n + '@':

^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}...$

The culprit is (([\-.]|[_]+)?([a-zA-Z0-9]+))*, an optional group wrapped in a star.

The linear-time engines

Go's regexp and Rust's regex crate use a finite automaton, so match time is O(n) in the input and independent of the pattern's shape.

r := regexp.MustCompile(`^(a+)+$`)
r.MatchString(strings.Repeat("a", 26) + "b")      //  49 µs
r.MatchString(strings.Repeat("a", 100000) + "b")  // 5.5 ms

100,000 characters in 5.5 ms against the pattern that takes Python 1.5 s on 26. The trade is that lookaround and backreferences are gone, because they cannot be expressed in a DFA. If a service matches user-supplied patterns or user-supplied input at scale, that trade is worth taking.

Everyday speed, in rough order of payoff

1. Hoist the compile out of the loop. A precompiled pattern is roughly 2× faster per call in Python than going through the module-level cache, and the cache is only 512 entries deep.
2. Anchor when you can. ^\d+$ fails at position 0. An unanchored \d+$ retries at every position in the string.
3. Prefer a negated class to a lazy dot. [^"]* never backtracks, .*? backtracks once per character.
4. Put the cheap, discriminating test first. if 'ERROR' in line and pat.match(line) skips the engine for most lines.
5. Use a literal search when the pattern is a literal. str.find, grep -F, strings.Contains. No engine involved.
6. Do not build one giant alternation of hundreds of literals. A set lookup or an Aho-Corasick matcher wins by orders of magnitude.

import re
PAT = re.compile(r'wor\w+')        # module level, compiled once
for line in f:
    if 'wor' in line and PAT.search(line):
        ...

Defensive checklist for user input

• Never compile a pattern supplied by a user without a hard timeout or a DFA engine. There is no safe way to do it with a backtracking engine.
• Cap input length before matching. Most ReDoS reports die at a 256-character limit.
• Prefer parsing to validating. int(), urlparse, ipaddress, datetime.strptime, and the platform date parser all fail fast and give you the value.
• Note which engines can time out. .NET takes a matchTimeout on Regex. Python re, Java, JavaScript, and Go have no timeout parameter, so the guard has to be input size or the engine choice.
• Test the failure case, not the success case. Pass a long almost-match, such as 40 valid characters and one invalid one at the end, and time it.
• Scan your own patterns for the shapes in the table above. Nested quantifiers and overlapping alternations are the only two things you are looking for.