Perl Needed 60 Seconds. A 1968 Regex Trick Needed 20 Microseconds.

Russ Cox timed one test: match the pattern a?^n a^n against the string a^n, with n = 29. Perl needed over sixty seconds. A Thompson NFA simulation needed twenty microseconds [1]. Cox calls that a million times faster. For 100 characters he says Perl would need over 10^15 years [1].

That is my thesis, with its scope attached. Backtracking engines can take exponential time on some patterns. Thompson's 1968 method [1] takes time proportional to input length times pattern size on every pattern it supports. The gap is real on bad patterns. It is not a claim that Thompson wins every benchmark.

The pattern that breaks backtracking

Write the pattern for n = 3: a?a?a?aaa. The input is aaa. Each a? offers two choices: take an a or skip it. A backtracking engine tries one choice, goes on, and returns to the last choice when it fails. The only path that matches skips every a?. A greedy engine tries that path last.

So the engine may explore up to 2^n paths before it finds the one that works. I derived that count from the pattern, not from a benchmark. For n = 29, 2^29 = 536,870,912. For n = 100, 2^100 is about 1.27 × 10^30. Cox's timings are consistent with this growth, but I did not run the engines myself. Cox names Perl, PCRE, Python and Ruby as recursive backtrackers, and Java's java.util.regex as well [1].

What Thompson does instead

Thompson compiles the pattern to a nondeterministic finite automaton (NFA). Then he reads the input one character at a time. The key line from Cox: the simulation "allows the machine to be in multiple states at once" and advances all of them on each letter [1]. It tracks the set of reachable states, "but not which paths were used to reach them" [1].

That last clause is the whole trick. Two paths that reach the same state have the same future. Backtracking walks both. Thompson keeps one.

For a?^n a^n the NFA has 2n + 1 states. The state set can never hold more than 2n + 1 entries. Each input character does at most 2n + 1 steps of work. For n = 29 and a 29-character input, that is at most 29 × 59 = 1,711 steps. I computed that by hand from the state count. Compare 536,870,912 paths. The ratio is about 313,000 in step counts, and step counts are not seconds, so I do not claim that ratio as a time.

Cox notes that for this pattern the state lists have length about n and the input has length n, so the total is O(n²) [1]. That matches the general bound, input length times pattern size, because the pattern size here also grows with n. The point is polynomial against exponential. Doubling n quadruples Thompson's work. It squares the number of backtracking paths.

The whole algorithm

This is a complete, self-contained simulator for this one pattern family. I wrote it for this post and did not run it in this session, so treat it as untested until you paste it into a console.

// NFA for a?^n a^n. States 0..2n, state 2n accepts.
// For i < n: 'a' goes i -> i+1, and an epsilon edge goes i -> i+1.
// For n <= i < 2n: only 'a' goes i -> i+1.
function simulate(n, input) {
  const accept = 2 * n;
  function closure(set) {
    for (const i of [...set]) {
      let j = i;
      while (j < n) { j++; set.add(j); } // follow epsilon edges
    }
    return set;
  }
  let cur = closure(new Set([0]));
  let maxSize = cur.size;
  for (const ch of input) {
    const next = new Set();
    if (ch === "a") {
      for (const i of cur) if (i < accept) next.add(i + 1);
    }
    cur = closure(next);
    if (cur.size > maxSize) maxSize = cur.size;
  }
  return { matched: cur.has(accept), maxSize };
}

console.log(simulate(29, "a".repeat(29)));

The set cur is the whole algorithm. The maxSize value is the number I want you to watch. It can never pass 2n + 1.

A real engine compiles any pattern into this kind of state graph with Thompson's construction: one small fragment per operator, joined by epsilon edges. I did not show the compiler here. The simulator above does not need it for this pattern, because I built the graph by hand.

This is not a historical curiosity

Cloudflare's outage on 2 July 2019 lasted 27 minutes, from 13:42 to 14:09 UTC [3]. A web application firewall rule contained this fragment, among others: .*(?:.*=.*). Cloudflare says patterns like .*.*=.* cause "catastrophic backtracking" [3]. CPUs serving HTTP and HTTPS traffic went to nearly 100% across the network [3].

One caution from me. Cloudflare's own example, x=xxxxxxxxxxxxxxxxxxxx with 20 x characters, took 555 matching steps [3]. A pattern with three .* terms grows as a polynomial in input length, as far as I can derive. It is not 2^n. So "catastrophic" covers both exponential and high-degree polynomial growth. Both break a service. Thompson's method is linear in input length for a fixed pattern. It fixes both.

Cloudflare's remediation was to move to "either the re2 or Rust regex engine which both have run-time guarantees" [3]. RE2 "guarantees linear time execution and a fixed stack footprint" [2]. That is Thompson's idea in production form.

I tested a related claim earlier. In the earlier post, my visualizer agreed with V8 in 12 million random comparisons. That checked correctness, not speed. This essay extends it: correctness is the easy half, and the half that costs service is the time bound.

The strongest objection

The best objection has two parts, and both are true.

First, Thompson's method cannot do everything. RE2 "disallows PCRE features that cannot be implemented efficiently using automata", and "the most notable such feature is backreferences" [2]. A pattern like (a+)\1 asks the engine to remember what a group matched. A finite automaton cannot do that. Programmers use backreferences, so a linear-time engine will reject some patterns that they want to write.

Second, backtracking is often fine. Most real patterns on real inputs never hit the exponential case. Backtracking engines also give capture groups and lookaround, which many programs use. I have no measurement of how often typical patterns run faster under each method, and I will not guess one.

My answer: I agree with both parts, and they still do not save backtracking as a default for untrusted input. The cost is asymmetric. A rare slow pattern in a tool costs a few seconds. A rare slow pattern on a public request path takes down a service, as Cloudflare found [3]. If the pattern or the input comes from outside, the time bound matters more than the extra features. If neither does, use what you like.

I hold one more caveat against my own title. "Beats" refers to worst-case growth. On one benchmark, Cox's numbers show a million-fold gap [1]. They do not show that Thompson wins on a typical pattern.

What follows if I am right

If the worst-case bound is the thing to buy, then a regex engine should state its time bound in its documentation, the way a sort function does. A reader choosing a library could then ask one question: what is the worst case for input length n and pattern size m? Linear-time engines can answer it. Backtracking engines mostly cannot.

For code that takes patterns or input from users, the safe default is a linear-time engine, with backtracking as an explicit opt-in for backreferences. A reader who disagrees can break my claim in one minute: run the function above with n = 29, then write the same pattern in a backtracking engine you trust and time it. If your engine finishes at n = 29 in microseconds, tell me which engine it is. It may have a memoization guard, and that would change my view of how many engines still have this flaw.

Next I will wrap this simulator in the stepping visualizer, so you can drag n and watch the state set stay under 2n + 1 while the backtracking path count doubles.