Where the table starts paying

Two machines for one expression and two cost structures.

The NFA costs nothing to prepare beyond its own construction and thirty-nine operations a character.

The DFA costs five thousand and sixty-five operations to build and one operation a character.

The crossing #

At 16 characters: NFA 650, DFA 5,081. The table is eight times worse.

At 64: 2,625 against 5,129.

At 256: 9,402 against 5,321. The table wins.

At 1,024: 40,136 against 6,089.

At 16,384: 639,902 against 21,449. Thirty times better.

So the crossing is between sixty-four and two hundred and fifty-six characters, and past it the table’s advantage grows without bound because its slope is thirty-nine times shallower.

The two lines are worth reading as what they are: a line through the origin against a line with an intercept. That is the simplest possible crossing and it has exactly one solution, which is why this plate is a crossing rather than a region.

The NFA’s line is 39n. The DFA’s is 5,065 + n. They meet at n = 5,065/38 = 133.

The measured crossing is between 64 and 256, and interpolating on the log axis puts it near 190 — above the arithmetic’s 133 because the NFA’s per-character cost is 39 at large n and 40.6 at small n, where the state set has not settled.

That the arithmetic predicts the crossing to within a factor of 1.4 is what makes the formula worth having: a system can compute where the crossing is without measuring, from two numbers it has.

The same shape, elsewhere in this collection #

A fixed construction cost against a per-unit query cost is one of the commonest shapes in this field and this collection has met it four times, which makes the crossing worth placing rather than treating as new.

An index larger than what it indexes is the same trade for a suffix array: build it once, then every search is logarithmic rather than linear. Its crossing is at a handful of queries rather than at a text length, because the construction is amortised over queries and not over characters.

The sort the library ships has a version too: a run-detection pass costs a scan and buys a merge that may be much cheaper.

What makes the regular-expression case different is that the construction’s cost is not bounded by the input. A suffix array’s construction is linear in the text; a subset construction’s is exponential in the expression, so the crossing can be anywhere and there is no bound that makes the decision safe.

That is the property that forces the lazy design, and it is worth stating as the distinguishing one: a fixed construction cost is fine when it is bounded and requires a fallback when it is not.

What the crossing is a function of #

Three things move it and only one is under anybody’s control.

The DFA’s state count, which decides the construction cost. Sixty-four states here; five hundred and twelve at k = 8, which would put the construction at about 45,000 and the crossing at about 1,200 characters.

The NFA’s size, which decides the slope. Twenty-four states here, giving thirty-nine operations a character.

The alphabet, which multiplies the construction — a state’s row is one entry per symbol, so a byte alphabet is 128 times a binary one.

Substituting: the construction is roughly S·σ·m and the NFA’s slope is roughly m, so the crossing is at about S·σ characters.

At S = 64 and σ = 2 that is 128, and the measured crossing is a little above it. At S = 500 and σ = 256 — a realistic expression on real text — it would be 128,000 characters.

That is the useful form. The table pays after about (states × alphabet) characters, and on a byte alphabet with a few hundred states that is over a hundred kilobytes.

Halving the expression’s k quarters the state count and therefore the construction, and it barely moves the NFA’s slope — so the crossing moves left by about a factor of four.

That is the direction the formula predicts and it is worth confirming, because the alternative reading is that the crossing is a property of the machinery rather than of the expression.

It is a property of the expression, through S. Every parameter of the construction — the alphabet, the machine’s size, the state count — enters through the construction’s cost, and the NFA’s slope enters through m.

What that means for a search #

A regular-expression search over a document, a log line, or a field is almost always under that threshold.

A search over a whole file, a corpus, or a stream is almost always over it.

So the compile decision is not a property of the expression; it is a property of how much text the expression will be run against, which the engine does not know when it compiles.

That is why the decision is deferred, and deferring it is what the lazy construction is.

What the lazy machine does to the crossing #

A lazy DFA builds each state the first time it is needed, so its construction cost is spread through the run and only the states the text reaches are paid for.

Its cost is therefore between the two lines: the NFA’s slope while it is missing, and the DFA’s while it is hitting.

Measured on the same expression: 50.9 operations a character at 128 characters — essentially the NFA’s — and 5.8 at sixteen thousand, approaching the DFA’s.

So it never pays the full construction and never has the DFA’s flat cost, and its own crossing against the pure NFA is much earlier: it starts hitting after a few hundred characters, because a short text reaches few states and those few are reused.

That is the whole argument for the lazy machine and it is why every production engine ships one.

The lazy machine’s cost has a shape the two-line plate cannot show, and it is worth stating because it is the shape a real system actually pays.

It is 40·(miss rate) + 1 per character, roughly, where the miss rate is the fraction of steps that need a state built. And the miss rate falls as the text lengthens because the reachable set is finite: 100% at 128 characters, 86% at a thousand, 37% at four thousand, 9.4% at sixteen thousand.

So the lazy machine’s line is concave — it starts on the NFA’s slope and bends toward the DFA’s — and it never has an intercept, because nothing is built before the first character.

That concavity is why it is never much worse than the better of the two, and it is also why it has no single crossing with either. A concave curve between two lines crosses each once and lies between them everywhere, which is the best possible behaviour for a machine that has to work without knowing the text’s length.

The decision that cannot be costed #

There is a circularity in the compile decision worth naming because it explains the design of every real engine.

To decide whether to build the table, a system needs the construction’s cost, which is S·σ·m.

S — the number of reachable subsets — is not known until the construction has run.

So a system cannot cost the decision without making it. Bounding S from the expression is possible only by the exponential, which is useless: a twenty-character expression’s bound is astronomical and its actual S might be eleven.

The available responses are three.

Build it and cap it. Run the construction with a state limit; if it exceeds, throw it away and use the NFA. That costs the capped work on the bad case.

Build it lazily. Never make the decision; let the text decide by reaching states or not.

Guess from the expression’s shape. Count the closures and alternations; an expression with few is likely to have a small S. That is a heuristic and it can be wrong in both directions.

Real engines do the second, with the first as a backstop.

Why the crossing is not a rule #

Every number above is for one expression on one alphabet, and the crossing moves by three orders of magnitude across realistic inputs.

A literal of twenty characters: S = 21, σ = 256, so the construction is about 5,400 NFA steps and the crossing is at a few thousand characters.

The blowup family at k = 8 on a binary alphabet: S = 512, construction about 45,000, crossing about 1,200.

The blowup family at k = 8 on a byte alphabet: S = 512, construction about 5,700,000, crossing about 150,000.

So a system quoting “compile if the text exceeds a thousand characters” has quoted a number about one of those three.

That is the same shape as most thresholds in this collection — the threshold that reaches zero is a filter’s, and where the sparse representation loses is a bit vector’s — and the resolution is the same: the threshold is a formula rather than a number, and the formula’s arguments are measurable.

What the construction is actually doing #

Five thousand and sixty-five operations for sixty-four states is seventy-nine operations a state, and it is worth unpacking because that number is the crossing’s numerator.

Building a state means, for each alphabet symbol, running one NFA step from the state’s subset: walk the subset testing each state’s predicate, collect successors, close under free edges. That is one NFA step per symbol per state.

An NFA step over a 24-state machine costs about forty operations, so two symbols is eighty a state, and sixty-four states is 5,120. The measured 5,065 is that.

So the construction is S·σ NFA steps, and an NFA step is what the NFA simulation pays per character. Building a DFA costs as much as running the NFA over S·σ characters — which is the crossing, derived rather than measured.

That equivalence is worth having because it makes the trade concrete: compiling is running the slow machine over a synthetic text of S·σ characters, in exchange for making the real text free. A system that expects less than that much text should not compile.

Why an engine compiles anyway #

Everything above argues for the lazy machine and most engines that use these techniques do compile eagerly in some cases, so it is worth saying when the argument does not apply.

A pattern known at build time. A tokeniser, a protocol dissector, a lexer generator: the expressions are fixed, the construction happens once ever, and the amortisation is over the program’s whole life. Every crossing is passed by a wide margin.

A pattern applied to a stream. A log filter matching a million lines a second is past the crossing within the first second, and the construction is a startup cost.

A pattern whose S is small and provable. A literal, a character class, a bounded alternation — these have deterministic machines of a few states and no risk. A system able to recognise those cheaply can compile them and defer on everything else, which is a heuristic and is what several engines do.

What the argument rules out is compiling an arbitrary user-supplied expression eagerly against an unknown amount of text, which is the case a search interface is in — and which is the case where the exponential is not merely a slowdown but a way for a user to exhaust a server’s memory with fifty characters.

What is not in the crossing #

Two costs the plate omits and both matter to a real decision.

Memory. The table is S·σ entries, and a system may be unable to build it regardless of the text’s length. That is a hard constraint rather than a trade, and it is what a state cap is really for.

Cache behaviour. A table lookup into a large table is a memory access with poor locality; a state-set walk over a small machine is a few accesses to a hot object. So the DFA’s one operation and the NFA’s thirty-nine are not thirty-nine to one in time, and the direction is against the table.

That second is the one this collection’s instrument cannot see. The comparison that is not one comparison is the habit that requires saying so, and here the honest statement is that the crossing measured in operations is later in time than in operations — the table’s advantage per character is smaller than thirty-nine.

What the plate holds fixed #

Every plate in this collection holds things fixed and it is worth saying which, because the crossing moves with all of them.

The expression is one member of the blowup family at k = 5: sixty-four deterministic states, twenty-four non-deterministic ones.

The alphabet is two symbols. On a byte alphabet the construction is 128 times larger and the crossing moves right by the same factor.

The text is uniform random over that alphabet. A text that kept the machine in few states would make the NFA’s slope shallower and move the crossing right; one that kept it in all of them would do the reverse — and this text does the second, because the expression’s (a|b)* prefix accepts everything.

And the measurement is operations rather than time, which as noted cuts against the table.

So the 256 is a number about a specific expression on a specific alphabet against a specific text, and its value is the formula it confirms rather than itself. The exponential is in the expression is where the first of those four is shown to span a factor of forty-six across two families of the same length.

The crossing as a system’s default #

Putting the pieces together, what a system should do is not “compile above a threshold” but something narrower.

Always build the NFA. It is linear, it always works, and it is the fallback.

Run the lazy machine. It costs the NFA’s rate while missing and converges on the table’s while hitting, so it is never much worse than the better of the two.

Cap its cache by memory rather than by a state count, and fall back to the pure NFA on a flush loop — because a cache that thrashes is worse than no cache at all, which a cache below the reachable set measures.

And build the full table only for expressions that are known to be reused, where the construction amortises over many texts rather than over one.

That last is the case the crossing on this plate is actually about: an expression compiled once and matched against a million lines is past every crossing, and the plate’s x-axis should be read as total characters matched rather than as one text’s length.

What a reader should compute #

Two numbers, both available before anything is built, and a formula.

The NFA’s size, m, which is the expression’s length plus one. That is the per-character slope: about 1.6m operations, from the measured 39 on a 24-state machine.

The alphabet’s size, σ, which the data gives.

Then the crossing is at about S·σ characters, and S is the one thing not available — so the practical form is a decision procedure rather than a formula.

Start lazy. If the machine settles — its miss rate falls below a few per cent — it has found its S, and S·σ is now known and the decision can be made properly for the next text.

If it thrashes, S exceeds the cache and the expression is one the table cannot serve. Fall back permanently.

That is a controller rather than a threshold, and it is the shape a decision takes when its own input is discovered by making it. This collection has one other of those — the boundary that hides the burst is a schedule chosen by a stream — and both share the property that the measurement and the decision are the same act.