DFA vs NFA Engines
The pattern \d{4} runs about the same speed on every engine you try. Swap in (a+)+$ over a long run of letters and one engine answers in microseconds while another climbs past a full minute, same input, same regex.
- ▸The same regex finishes in microseconds on one engine and runs over a minute on another, on identical input.
- ▸One family can never hang but refuses whole features; the other offers everything and can hang forever.
- ▸There is no single fastest engine: the exploring family usually wins on ordinary patterns and collapses on hostile ones.
Hand the regex cat|dog to Google's re2 and to Python's re, and both return the same match on the same string. The answer is identical; the road to it is not. The first compiles the pattern into a state machine, an NFA or the DFA built from it, then runs the input through that machine once. The second keeps the pattern as a branching set of choices and, at match time, steps into one choice and returns to try the next when it fails. Every shipping engine sits in one of these two camps: one compiles the pattern to a machine and runs it, the other holds the pattern as choices and explores them as the characters arrive.