2.75 seconds or 2 microseconds: the same regex, two engines

Here is a regular expression: (a+)+$. Here is an input: a string of 28 a characters followed by one !, which the pattern cannot match.

Ask Dart's built-in RegExp whether the pattern matches that input, and on my laptop it takes 2.75 seconds to return false. Ask Google's RE2 engine the same question about the same bytes, and it returns false in about 2 microseconds. Same pattern, same string, same answer. The only thing that changed is which engine did the matching, and it made the answer arrive roughly a million times sooner.

Both numbers are real. I ran the benchmark on Apple Silicon with Dart 3.11, and both engines saw byte-for-byte identical input. The gap is not something you can close by writing a cleverer pattern. Here is where it comes from, and when it is worth paying RE2's cost to avoid it.

The measurement

The pattern is (a+)+$. The input is n copies of the letter a followed by one !, so the match always fails (the string does not end the way the pattern demands). I fed the identical pattern and input to both engines and timed the match. Times are in microseconds; I write us for microseconds and ms for milliseconds.

n	Dart RegExp (us)	re2 (us)
16	4,712	2 to 3
18	10,490	2 to 3
20	15,671	2 to 3
22	49,416	2 to 3
24	169,381	2 to 3
26	679,067	2 to 3
28	2,746,957 (2.75 s)	2 to 3

re2 sits flat at 2 to 3 us the whole way down the column. Dart's RegExp roughly quadruples every time n goes up by two. By n=28 it is spending 2.75 seconds to answer a yes/no question about a 29-character string.

This is the shape of a ReDoS (regular expression denial of service) bug. A pattern that looks ordinary meets an input that is a little bit adversarial, and one match call ties up the isolate for seconds. This is not hypothetical: in dart-lang/sdk#61284 an ordinary URL pattern froze a running app on iOS. Nobody wrote that pattern to be malicious. It just had the wrong shape and met the wrong input.

Why one explodes and the other does not

Both engines answer the same question. They go about it in completely different ways, and that difference is the entire 2.75-seconds-versus-2-microseconds gap.

A backtracking engine treats matching as a search

For (a+)+ to match a run of a's, the engine has to decide how to divide that run between the inner a+ and the outer repetition. Five a's could be one group of five, or four then one, or two then three, and so on. As long as more a's keep coming, the greedy path just extends and the division never has to be reconsidered; the engine takes the first split that works and moves on.

The trouble starts at the character after the run. In our input that character is !, and the pattern still needs $ (end of string) there. The match fails at that point. A backtracking engine does not give up there. It backs up and tries the next way of dividing the a's, then the next, then the next, on the theory that some other division might let the rest of the pattern match.

The number of ways to split a run of n a's into ordered groups is 2 to the power n-1. At n=28 that is 2^27, which is 134,217,728 divisions the engine works through before it can be sure there is no match. Every extra a doubles that count. That is where the "quadruple every time n goes up by two" in the table comes from: one more character, twice the work; two more, four times.

RE2 does not search

RE2 compiles the pattern once into a finite-state machine. Then it reads the input one character at a time, and instead of tracking a single guess it tracks the entire set of states the machine could be in at that point. Each character advances that whole set by one step. The read pointer only ever moves forward; it never backs up to retry a division, because RE2 is not trying divisions at all. It is asking, after these characters, is any accepting state reachable.

The linear-time guarantee is exactly this: n characters take exactly n steps, and no input, however it is crafted, can push an RE2 match into exponential time. There are no divisions to enumerate, so there is nothing to enumerate exponentially many of.

The engine behind the re2 package is an FFI binding to Google's RE2, the same C++ engine, exposed to Dart.

Why Dart's built-in RegExp is the backtracking kind

Dart's RegExp is Irregexp, the engine that came from V8. Irregexp is a backtracking engine, which is why it is fast and full-featured on ordinary patterns and can handle features like backreferences. The same design is what lets a nested quantifier like (a+)+ blow up. Every backtracking engine behaves this way when a nested quantifier fails to match. The exponential search is the algorithm working as designed. There is no patch for it; a backtracking engine does this by construction.

The million-character match

Because RE2 takes one step per character, you can throw genuinely large input at it and watch the time stay reasonable. Each of these is n a's followed by one non-matching character, the same failing shape as before, just longer:

input length (n)	re2 match time
1,000	50 us
10,000	138 us
100,000	111 us
1,000,000	1,894 us (1.9 ms)

Those numbers do not climb smoothly. At the microsecond scale, fixed overhead (crossing into native code, marshalling the string) and ordinary measurement noise dominate, so n=100,000 can clock in under n=10,000. The trend is the point: ten times the input is nowhere near ten times the time, and a million characters match in 1.9 ms.

Put that same million-character hostile input in front of a backtracking engine on (a+)+$ and it would have 2^999999 divisions to work through, which is longer than the age of the universe. RE2 finishes it in under two milliseconds because it never asks that question.

Using it in Dart

The API is small. You construct a Re2 from a pattern and call hasMatch, firstMatch, or allMatches.

import 'package:re2/re2.dart';

void main() {
  // The classic catastrophic-backtracking pattern.
  final re = Re2(r'(a+)+$');
  final hostile = 'a' * 30 + '!';
  print(re.hasMatch(hostile)); // returns false in microseconds; the built-in
                               // RegExp would take seconds on the same input
  re.dispose();
}

I used 30 a's here; since each a doubles the backtracking engine's work, 30 is well past the point where the built-in RegExp stalls for seconds, while RE2 does not notice the difference.

Re2 implements Dart's Pattern, so an instance drops into String.split, String.replaceAll, and the other methods that take a Pattern. Call dispose when you are done with it; it holds a native resource behind the FFI boundary.

The honest trade-off

RE2 is not a general speed boost for everyday regexes. On ordinary patterns and ordinary input, Dart's built-in RegExp is usually the faster of the two, because every RE2 call has to cross the FFI boundary and marshal the string, and that costs something (roughly 2x in my measurements). What RE2 buys you is a ceiling on match time that holds no matter what the input is. That is a security property, and it only matters when the pattern or the input is outside your control. Most of your regexes run against strings you control, and the built-in RegExp is the right tool for those.

So the rule I use:

• Reach for re2 when the pattern or the input is attacker-reachable: user-supplied search terms, validating uploaded content, a WAF-style ruleset, anything where someone else picks the string you match against.
• Keep the built-in RegExp everywhere else, which is most places.

One constraint is worth knowing before you commit. RE2 does not support backreferences (\1) or lookaround ((?=...), (?<=...)) at all. Those are the features that force a backtracking implementation and open the door to the exponential blow-up, so RE2 leaves them out by design. A pattern using them throws a FormatException the moment you construct the Re2, long before it could bite you in production.

The 2.75-seconds-versus-2-microseconds gap comes from RE2 refusing to enumerate divisions at all, which is a game a backtracking engine has no way to refuse. Once a regex runs against input someone else chose, the exponential case turns from a curiosity into an availability bug, and a linear-time engine earns its FFI cost. The package is re2 on pub.dev; the engine underneath is the one Google wrote for exactly this problem.

Disclosure: re2 is my package; the RE2 engine it binds is Google's.