The folklore is about a matcher

“Regular expressions are slow” is a sentence about an implementation and not about a language, and the measurement that separates the two takes twenty characters.

The witness #

The expression (a|a)*b. The text: n copies of a.

The expression cannot match — there is no b — so both matchers must explore whatever they explore and then report failure.

At 8 characters: backtracking 2,046 steps, Thompson’s NFA 137. At 12: 32,766 against 201. At 16: 524,286 against 265. At 20: capped at four million, against 329. At 24: capped, against 393. At 28: capped, against 457.

The ratio at twenty characters, before the cap truncates it: 12,158.

The growth rates #

The backtracking matcher’s steps go 2,046, 32,766, 524,286 — multiplying by sixteen every four characters, which is a factor of 2.0002 a character.

Measured over the three uncapped points, the per-character growth is 2.0002. That is 2^n, and the theoretical count for this witness is 2^(n+1) − 2, which gives 2,046 at n = 10 — the expression consumes two characters of context, so the effective n is the text’s length minus two.

Thompson’s NFA goes 137, 201, 265, 329, 393, 457 — sixteen more per four characters, which is linear. Its cost per character is flat at 16.3 across the whole sweep, moving by 4.1%.

So one machine is exponential in the text and the other is linear in it, on the same expression.

Putting the two plates side by side is the comparison worth making. The automaton’s plate spans two machines whose totals differ by a factor of thirty at sixteen thousand characters, and both are straight lines on a log-log plot with slope one.

The backtracking plate spans two machines whose totals differ by twelve thousand at twenty characters, and one of them is a straight line with slope one while the other has slope proportional to the length.

Those are not comparable pictures. Everything on the first plate is a constant factor argument about linear machines, and the second is a class argument about one machine that is not linear.

Conflating them is what “regular expressions are slow” does.

Why the backtracking matcher explodes #

It explores the ways the expression can be laid against the input.

(a|a)* can match a run of n a’s in 2^n ways: at each position the closure can take either branch of the alternation, and both consume one a. Every one of those parses is distinct as a parse and identical as a match.

So the matcher tries each, finds no b at the end, and backtracks. The alternation’s two branches are the same string, so there is nothing to distinguish them and nothing to prune.

That is why the witness has (a|a) rather than (a|b): the two branches must be interchangeable, so that every combination is explored and none is cut by a mismatch.

Why the automaton does not #

The NFA carries a set of states, and a set does not have multiplicity.

After reading k characters the machine could have arrived at its states by 2^k different paths, and it does not care — the set is the same set. So the work per character is the set’s size, which is bounded by the machine’s, which is fourteen states here.

A set is where the exponential goes. The backtracking matcher enumerates paths; the automaton enumerates reachable states; and the number of reachable states is bounded by the machine while the number of paths is not.

That is the whole of Thompson’s contribution and it is one sentence.

There is a version of the backtracking matcher that would not explode on this witness and it is worth naming because most engines do not have it.

Memoisation. Record the (position, expression-node) pairs already tried and failed, and skip them. That turns the search into a dynamic program over m·n cells, which is polynomial.

It costs m·n memory, which for a long text is a great deal — and it changes the leftmost-first semantics if implemented carelessly, because the memo table does not distinguish the order branches were tried in.

Some engines do it and most do not. The ones that do are the ones whose authors read the measurement above and decided the memory was worth it.

That option is the honest reason the folklore is about implementations rather than about a language: the same backtracking search with one table added is polynomial, so the exponential is not intrinsic even to backtracking.

Why every engine backtracks anyway #

The measurement makes backtracking look indefensible and there is a real reason it is everywhere.

Backreferences. A pattern like (a*)b\1 requires the matcher to remember what a group captured and compare against it later. That is not a regular language — no finite automaton recognises it — and no machine in this strand can express it.

Once an engine supports backreferences it needs a backtracking matcher for those patterns, and having built one it is simpler to use it for everything than to maintain two matchers and a classifier.

Capture groups, similarly: reporting where each group matched requires tracking positions through the parse, which a state set does not carry. There are automaton-based techniques for it and they are more complicated than backtracking.

Leftmost-first semantics. Most engines define alternation as “try the left branch first, and prefer its result”, which is a property of a backtracking search order rather than of the language. An automaton finds the leftmost-longest match, which is a different answer, and changing it would break every existing pattern.

So the folklore’s target is a matcher that exists for good reasons, and the reasons are all about features outside the regular languages.

The cap, drawn #

Three of the six points are the backtracking matcher hitting a four-million-step limit, and they are drawn as open circles rather than omitted.

A sweep that stopped at sixteen characters would be a shorter sweep. A plate that omitted the capped points would be reporting a measurement it did not make.

So the convention is to draw them and mark them, and the caption says what the cap was. That is this collection’s habit for a measurement that ran out of budget: the point is data — the matcher exceeded four million steps at twenty characters — and hiding it would understate the effect.

The capped points also flatten the plotted ratio, which is why the worst ratio on the plate is at twenty characters rather than at twenty-eight. The true ratio at twenty-eight is about 2^26 over 457, which is a hundred and forty thousand.

What the two machines carry #

The clearest way to hold the difference is what each carries between characters, and it is one line each.

The automaton carries a set of states — at most m of them, and a set has no multiplicity, so two ways of reaching the same state are one entry.

The backtracking matcher carries a call stack — one frame per choice point still open, and the number of choice points is the number of ways the expression has been laid against the input so far.

So the automaton’s state is bounded by the machine and the matcher’s is bounded by the search tree, and the search tree’s size is what the exponential is.

That framing also says why memoisation fixes it: a memo table is exactly the observation that two stack states differing only in how they got somewhere are the same state, which is what a set does automatically.

So the automaton is the backtracking matcher with its duplicates collapsed, and the collapse is the whole algorithm. Two states per operator builds the machine and this is what the machine is for.

What the sentence should be #

Three claims that are usually one.

Regular expression matching is linear in the text. True of every machine in this strand, for every expression.

A backtracking matcher can be exponential in the text. True, on witnesses like this one, and true of most production engines.

And determinising a regular expression can be exponential in the expression. True, measured at 2^(k+1) on a family with a twenty-character member — the exponential is in the expression.

The three are about different things: an algorithm, an implementation, and a construction. “Regular expressions are slow” collapses all three into a property of the notation, and the notation has none of them.

Where the automaton’s own limits are #

Since this essay is about a claim being too broad, it is worth being precise about what the automaton does not give, so that the correction is not itself too broad.

It does not give capture groups. Reporting where each parenthesised group matched requires tracking positions through the match, and a state set carries no positions. There are techniques — tagged transitions, parsing automata — and all of them are more complicated than the machine here.

It does not give leftmost-first alternation. An automaton finds the leftmost-longest match; most engines define alternation as preferring the left branch, which is a search-order property. Changing the semantics would break existing patterns.

And it does not give backreferences, which are not regular at all — the feature two states per operator records as the reason this language is deliberately small.

So the correct version of the claim is: matching a regular expression, in the regular-language sense, against a text is linear in the text. Most of what people call regular expressions is not that, and the extra features are where the cost is.

The measure that cannot see the alphabet is this collection’s habit for a definition and an implementation coming apart, and the regular-expression case is the clearest instance it has: a notation named after a class of languages, extended past the class, and then judged on the performance of the extension.

Which exponential is worse #

Two exponentials have now appeared in this strand and it is worth comparing them, because the one with a name is the milder.

The subset construction’s is in the expression, is paid once at construction, and can be capped with a fallback. A user cannot trigger it without writing a long expression, and a system can refuse.

The backtracking matcher’s is in the text, is paid on every match, and cannot be capped without abandoning the query. A user triggers it with a twenty-character pattern, and the input that triggers it may come from somewhere else entirely.

So the dangerous one is the one every engine has and the manageable one is the one described as pathological. That inversion is an accident of which literature each belongs to: state explosion is a theory result with a name and backtracking blowup is an operational hazard with a mailing-list post.

The comparison has one more asymmetry worth stating and it is about who pays.

The construction’s exponential is paid by the system that compiles the expression, at a moment it chooses, with a budget it controls. It can cap, defer, or refuse.

The backtracking exponential is paid during a match, on input the system may not control, at a moment determined by the data. Capping it means abandoning a query that might have succeeded.

So the two differ not only in magnitude and axis but in whether the paying party can decline. A system can always decline to build a table; it cannot always decline to answer a query.

What a system should do #

The measurement supports a narrow recommendation.

If the patterns are trusted and simple, an automaton. Every machine in this strand is linear in the text and the choice among them is where the table starts paying.

If the patterns need backreferences, a backtracking matcher and a step budget. The budget is what turns an exponential into a refusal, and a refusal is a correct answer to a query that cannot be afforded.

And if the patterns come from users, both: classify the pattern, use an automaton when the pattern is regular, and use a budgeted backtracker otherwise.

That third is what a careful engine does and it is more machinery than either alone. The reason it is worth it is on the plate: an unbudgeted backtracker matching a user-supplied twenty-character pattern against a user-supplied twenty-character string is a way to hold a server for as long as the attacker likes.

The fifth machine, which is the reference #

The backtracking matcher is in this collection’s code for a reason other than being measured, and it is worth saying because it explains why it exists at all.

It is the reference implementation the four automaton machines are checked against. Five expressions, sixteen texts each: the NFA, the DFA, the lazy DFA, the bit-parallel machine and the backtracking matcher all agree on eighty comparisons.

That fifth opinion matters because the four machines share a construction. A bug in Thompson’s construction — a patch applied to the wrong output set, a closure whose back-edge points at the wrong split — would produce four machines agreeing on a wrong answer.

The backtracking matcher walks the parse tree directly and never touches the machine. So it is the only implementation that could disagree with all four, which makes it the one that establishes the construction is right.

That is a use for a slow, exponential, indefensible matcher that its performance measurements do not suggest: it is the independent check, and its slowness is irrelevant because it runs on sixty-four-character texts.

Two states per operator is where the construction it checks is described, and the check’s eighty comparisons are what stand behind every number in this strand.

What is measured and what is not #

The plate is one witness and it is worth saying what it does and does not establish.

It establishes that a backtracking matcher’s cost can be exponential in the text on a fixed short expression, that the exponent is one per character, and that an automaton’s is not.

It does not establish how often that happens on real patterns, which is a question about a distribution nobody here has.

The honest state is that the witness is contrived — (a|a)* is not a pattern anybody writes — and that near-misses are common: (a|b)*, (\s|\w)*, (x+)+ all have the same interchangeable-branch structure and all appear in real patterns by accident.

So the hazard is real and its frequency is unmeasured, which is the same position every worst-case result in this collection is in. A guarantee is not a result is the habit: a worst case says what can happen and a measurement of real inputs says what does, and both are needed. The threshold that reaches zero is where this collection last had to separate a worst case from a distribution, and the resolution there was the same: report the witness, name the shape, and say that the frequency is unmeasured.

The last thing the automaton strand does #

This field began with a machine built from a text and one built from a set of patterns, both deterministic and both linear in their input.

It ends with a machine built from a program supplied at run time, whose deterministic form is exponential in that program, whose non-deterministic simulation is linear in the text, and whose most widely deployed implementation is neither.

Three machines, three inputs, and the third is the only one whose size a system does not control. That is what makes it the strand’s hard case, and it is why the four essays before this one are all about a trade rather than about a construction.

The strand’s own retraction sits in that sentence. It set out to measure four machines and expected the interesting result to be which is fastest. What it found is that three of the four are linear in the text and differ by constants, that the fourth — the lazy one — is the only one whose cost depends on the text at all, and that the machine everybody actually uses is not among the four and is on a different scale entirely.

So the strand’s largest number is not a comparison between its machines. It is a comparison between all of them and something outside them, at a factor of twelve thousand on a twenty-character input.