The regex module is excellent and fast. However, it supports features (like back-references) that cannot be implemented using linear-time algorithms.
I've only glanced at the code, but it doesn't appear to be using a Thompson-style implementation.
My question, then, is: if a given expression doesn't use back-references, fuzzy matching, etc, is performance guaranteed to be linear in the length of the input string for all possible inputs? Or are there some inputs that cause exponential-time behavior?