Your Code Isn't Slow, Your Regex Is Having an Existential Crisis

• #regex
• #performance
• #debugging
• #python

Every developer eventually meets the regex that ate production. Mine looked harmless. It validated a username. It was twelve characters long. It took down an API for forty minutes on a Tuesday, which is the most boring day to have a crisis and therefore the most humiliating.

The pattern that looked innocent

import re

USERNAME = re.compile(r"^([a-zA-Z0-9]+)*$")

USERNAME.match("syed")          # fine
USERNAME.match("a" * 30 + "!")  # goodbye, CPU

Read it out loud: "one or more letters, repeated zero or more times." That is the regex equivalent of saying "I want food, possibly several foods." It means the same thing as [a-zA-Z0-9]*, but the engine doesn't know that. When the match fails (thanks to that sneaky ! at the end), the engine tries every possible way to split the string into groups before giving up. For 30 characters that is roughly a billion ways. Your server will try all of them. Politely. One at a time.

This is called catastrophic backtracking, and it is exponential. Add one character, double the time. Users don't need to be hackers to trigger it; they just need to paste a long string with a typo at the end. Which is to say: users.

How to spot one

Look for a quantifier inside a group that is itself quantified:

• (a+)+, (a*)*, (\w+\s?)* — nested repetition
• (a|aa)+ — alternatives that can match the same text
• .*.*=.* — several greedy wildcards fighting over the same characters

If two parts of your pattern can both claim the same characters, the engine will try every custody arrangement.

How to fix it

1. Flatten it. ^([a-zA-Z0-9]+)*$ is just ^[a-zA-Z0-9]*$. Done.
2. Make alternatives mutually exclusive. If branches can't overlap, there's nothing to backtrack into.
3. Use possessive quantifiers or atomic groups where your engine supports them (Python 3.11+ does: (?>...) and a++). They say "once I've matched this, don't you dare give it back."
4. Limit input length before matching. A username longer than 64 characters is not a username, it's a cry for help.
5. Use an engine that can't backtrack for untrusted input, like RE2 (the google-re2 package), which guarantees linear time.

import re

# atomic group: no backtracking into the repetition
USERNAME = re.compile(r"^(?>[a-zA-Z0-9]+)$")

def valid_username(s: str) -> bool:
    return len(s) <= 64 and bool(USERNAME.match(s))

The lesson

Regex is a tiny programming language with no debugger, no type checker and a very literal personality. Treat every pattern that touches user input like code that can loop forever, because it can. Write a test with a long, almost matching string. If that test takes more than a few milliseconds, your regex is having an existential crisis, and it's much cheaper to help it now than at 2 AM.