So where did end up for earlier verisons of Python?

Yes and no.

We use finite automata to recognise regex's. A automata is just a fancy name for a directed graph. The lines on the graph that connect one state to the next are labelled with the input character. If there is no line from the current state labelled with the next input character the regex didn't match the input. If there is a line, you move onto the next state and input character. If this eventually gets you to the end of the graph, you have a match. The re.compile() call compiles your pattern into the said graph. At least that is the theory. In practice Python's re module is derived from a the C PCRE library, which looks to work differently again. It compiles to a mini program - but it turns out that program is equivalent to a automata.

There are two distinct types of automata - Deterministic and Non-Deterministic. (Actually in theory there is also infinite and infinite, which refers to the number of states in the graph. For obvious reasons practical computers only deal with finite graphs.) The sole difference between a NFA (Non-deterministic finite automata) and a DFA (deterministic finite automata) is an NFA state is allowed to have several lines labelled with the same input character. Which is where the "non-deterministic" comes from - when confronted that input character an NFA has no deterministic way of knowing which line to choose. In practice a real computer must execute all of them, either in parallel or using backtracking (which is effectively what PCRE does).

That difference between NFA and DFA oddly doesn't effect the their power to recognise complex regular expressions overly. What it does effect is their performance characteristics. The space used by compiled graph on an NFA is of the same order as the size of the regular expression it is compiled from (ie the relationship between the size of the regular expression and the size of the compiled graph is linear). However, for some inputs it's execution time can be exponential to the number of characters in the input.

In contrast a DFA's execution time is always linear to the size of it's input. In practice the execution time is always faster than that implies because an NFA has to do substantially more bookkeeping. Studies I've seen say around 20 times faster. However, the space used by its compiled graph is in the worst case an exponential function of the size of the pattern it is executing. Worse, notice I used the term "execution time" when describing their relative speed. That is because in an interpreted language like Python always has to compile the regular expression at run time. That compiling can also take an exponential amount of time. So this is where the "no" in my "Yes and No" answer comes from. Both can take exponential amounts of time.

A backtracking recogniser like PCRE gets a lot of it's speed by delaying most of the work until the it recognises the input. This can save a lot of time (think a lot of '|' conditions that aren't executed.) That's were PCRE gets it's speed from in the "usual case". So if you are recognising a regular expression just once PCRE is usually faster than other methods, when you include compile time. But it is also the worst in execution time if it strikes a pathological input.

So now we get the "Yes" part of my "Yes and No" answer. When we are taking about protecting against a DOS, the nice thing about a DFA is it's predictable. Predictable in the sense that while the compile step incurs a large upfront cost, that cost is always the same in every run of the program - including testing runs. If it is a problem you change your regex during testing. So the user will never see a program fail because of some input the programmer hadn't tested for. PCRE is at the opposite end of the spectrum. You will never see an issue from the speed of PCRE compiles. Unless you are very, very good you won't generate a pathological input during testing. But your program can mysteriously fail (well, hang) during production.

That had never happened to me for 20 years. And now suddenly, it's happened every couple of months. Having programs fail on inputs I am not and never will be smart enough to generate test cases for is not good. Looking at this from the standpoint of a Software Engineer trying to build reliable things, I'll wear the upfront cost of DFA's every time. Hell, the upfront cost of DFA's needn't even be incurred at runtime even in languages like Python. All the re module need do it allow you to save the compiled form somewhere so you can reuse it at runtime. And guess what? If you eliminate the time it takes to compile a DFA, it's execution time is always linear based on the size of the input. That is how my "Yes" answer arises.