Regular Expressions › Performance Considerations
Language AI HandbookAll chapters Regular Expressions › Performance ConsiderationsOne section · Sections in this chapter14 / 21 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Regex engines use backtracking to find matches, which can lead to catastrophic performance on certain patterns. To understand why, you need a basic picture of how a regex engine works. Most Python regex engines (including the one in the re module) use a backtracking NFA (nondeterministic finite automaton) approach. When the engine encounters a choice point, such as a quantifier that could match different numbers of characters, it picks one option, continues trying to match the rest of the pattern, and if that fails, backtracks to the choice point and tries another option. For well-designed patterns, this backtracking is limited and fast. For poorly designed patterns, the number of possible paths through the choice points grows exponentially with input length.
Catastrophic Backtracking
import time
# Dangerous pattern: nested quantifiers
dangerous_pattern = r"(a+)+"
safe_pattern = r"a+"
# Test string that causes backtracking
test_string = "a" * 25 + "b"
# Time the safe pattern
start = time.perf_counter()
re.search(safe_pattern, test_string)
safe_time = time.perf_counter() - start
# The dangerous pattern would take exponentially longer
# We won't run it with a long string to avoid hanging
short_test = "a" * 10 + "b"
start = time.perf_counter()
re.search(dangerous_pattern, short_test)
dangerous_time = time.perf_counter() - startBacktracking performance: Safe pattern 'a+' on 25 a's: 0.0500 ms Dangerous pattern '(a+)+' on 10 a's: 0.0388 ms Warning: '(a+)+' on 25+ characters can take minutes or hours! The time doubles with each additional character.
The exponential growth of backtracking time is one of the most important performance concepts to understand. Let's visualize how execution time explodes as input length increases:
The logarithmic scale reveals the exponential nature of the problem. While the safe pattern stays flat (constant time), the dangerous pattern's execution time doubles with each additional character. At 20 characters, matching takes seconds. At 25, it takes minutes. At 30, hours. This is why avoiding nested quantifiers is critical for production code.
Performance Tips
To write efficient regex patterns, follow these guidelines:
- Anchor when possible:
^patternis faster than searching the whole string - Be specific:
[0-9]is faster than\din some engines,[a-zA-Z]is faster than. - Avoid nested quantifiers:
(a+)+is dangerous; usea+instead - Use non-capturing groups:
(?:...)is slightly faster than(...) - Compile patterns: For repeated use,
re.compile()avoids re-parsing - Use possessive quantifiers or atomic groups: Python's
redoesn't support these, but theregexmodule does
# The regex module offers more features and better performance
# Install with: pip install regex
try:
import regex
# Possessive quantifiers prevent backtracking
# a++ means "match one or more 'a', and don't give them back"
possessive = regex.compile(r"a++b")
# Atomic groups: (?>...)
atomic = regex.compile(r"(?>a+)b")
has_regex = True
except ImportError:
has_regex = FalseThe 'regex' module provides: - Possessive quantifiers: a++ (no backtracking) - Atomic groups: (?>a+) - Better Unicode support - Fuzzy matching