What a character costs on four machines

One expression, one text of four thousand characters, four machines.

Thompson’s NFA, carrying a set of states: 43.7 operations a character, 24 to build.

The subset DFA, one table lookup: 1.0 a character, 11,297 to build.

The lazy DFA with a cache of sixty-four: 41.8 a character, and 45 cache flushes.

The bit-parallel simulation, one machine word: 37.2 a character, 24 to build.

The two currencies #

A matcher’s cost has two parts and reporting only one of them makes a machine look free.

The construction is paid once per expression. The DFA’s 11,297 operations are 64 states each requiring an NFA step per alphabet symbol, and each NFA step is a state-set walk with closures.

The steps are paid once per character. The DFA’s are one table lookup, exactly, at every text length.

So the DFA is a hundred and seventy times more expensive to build than the NFA and forty-four times cheaper to run, and which is better is a question about the text’s length. Where the table starts paying is the crossing.

That the two currencies have to be separated is not an accounting nicety; it is what makes the four machines comparable at all. Three of them have a construction cost of about twenty-four operations and one has eleven thousand, and a total that mixed the two would report the DFA as the most expensive machine on any text under eleven thousand characters — which is true and is not what a per-character comparison is asking.

The convention this settles: a cost paid once and a cost paid per unit are separate columns, and a plate showing one says which. This collection has applied it to construction against query throughout, and the regular-expression machines are the first case where the two differ by three orders of magnitude.

Why the DFA’s step is exactly one #

A deterministic machine’s state is an integer and its transition is table[state][symbol]. One array read.

That the measurement is exactly 1.000 rather than approximately one is worth checking rather than assuming, because the construction runs NFA steps and charges the same counters a query does — so an implementation that did not zero them between the two phases would report a per-character cost that falls as the text lengthens, which is amortisation reported as a step cost.

That is what the first version of this measurement did: 4.85 times more per character at one length than at another, on a machine whose step is a constant. The repair is to separate the two currencies at the point of measurement rather than in the prose.

Why the NFA’s step is forty-four #

The set carried by a Thompson simulation over this machine holds several states, and one step visits each of them, tests its predicate, follows the successors of those that match, and closes the result under the free edges.

Measured: 119,266 state visits and 59,636 transitions over four thousand characters — 29.8 and 14.9 a character, summing to 43.7.

That the transitions are exactly half the visits is structural: every split state visited during a closure pushes two successors, and the closure visits each state once.

The machine has 24 states, so a set can hold up to 24 and the measured 29.8 visits a character means the average set is large — most of the machine, most of the time, on a text over an alphabet the expression’s (a|b)* accepts entirely.

There is a second reason the NFA’s step is large on this particular expression and it is worth separating from the machine’s size.

The expression begins with (a|b)*, which accepts every character. So the machine is always in the states corresponding to that prefix, and every character keeps them alive — the set never shrinks to a few.

An expression beginning with a literal would behave differently: after a mismatching character the set collapses to the start state’s closure, and steps become cheap until a match begins.

So 43.7 is a measurement of a machine that is always fully alive, which is the bad case for a set-carrying simulation and the case a prefix-unanchored search is always in. That is the realistic case for regular-expression search — as opposed to a full match — and it is why a search over a long text is where the DFA earns its construction.

Why the bit-parallel machine is not much better #

The state set fits in one 32-bit word for this machine, so a step could in principle be a handful of word operations.

It is 37.2, which is 85% of the set-carrying simulation’s.

The reason is the epsilon closure. Thompson’s splits point anywhere, so following the free edges is not a shift — it is a reachability computation over an arbitrary graph, iterated to a fixed point, and each iteration ors a successor mask into the accumulator for every set bit.

So the word representation makes the union cheap and leaves the iteration alone, and the iteration is most of the work.

A construction whose transitions are local — Glushkov’s, with no epsilon edges at all — is what a genuinely bit-parallel matcher uses, and its step is a masked shift. This collection builds Thompson’s, so its bit-parallel machine is a constant factor rather than the technique the literature means. Two states per operator records that choice and its consequence.

The lazy machine, which is not a constant #

Three of the four have a per-character cost that does not depend on the text’s length. The fourth does, and by a factor of nearly nine.

At 128 characters: 50.9 operations a character. At 512: 49.1. At 2,048: 33.5. At 16,384: 5.8.

The lazy DFA builds a subset state the first time a character asks for it. Early in a text almost every step is a miss — an NFA step plus the bookkeeping. Later, most steps are hits — one lookup.

So its cost per character falls as the text lengthens, and the number quoted for it is a number about a text length.

That is the two-ended check this measurement carries: the NFA, the DFA and the bit-parallel machine must each be flat within 15% across a factor of a hundred and twenty-eight in text length, and the lazy machine must not be. Measured spreads: 1.03, 1.00, 1.03, and 8.74.

A check requiring all four to be flat would fail correctly and would be testing a claim nobody makes. One requiring only the first three would pass on a lazy machine that happened to be flat, which would mean its cache was thrashing at every length.

The lazy machine’s falling cost is the reach curve read as a cost. At 128 characters it has built seventeen states of five hundred and twelve and every step is a miss; at sixteen thousand it has all of them and the miss rate is 9.4%.

So its per-character cost tracks 1 − (hit rate), scaled by what a miss costs relative to a hit. A miss is an NFA step — about forty operations — and a hit is one lookup, so the cost is roughly 40·(miss rate) + 1.

At a miss rate of 9.4% that predicts 4.8 and the measurement is 5.8, which is the bookkeeping the model omits.

That the model is close enough to be worth writing is what makes the lazy machine’s behaviour predictable from the reach curve, and the reach curve is a property of the expression and the text rather than of the implementation.

What the machines are made of #

The four differ in what they carry between characters, and that is the whole of the classification.

The NFA carries a set of states — up to m of them.

The DFA carries an integer — the index of a set.

The lazy DFA carries an integer and a cache of the sets it has named.

The bit-parallel machine carries a word — the set, packed.

So the DFA has traded space for the ability to carry one number, and the other three carry the set in three representations. The exponential is in the expression is where the space that trade costs is measured: 512 states for a twenty-character expression, and unbounded in general.

What the four agree about #

Before any of the costs, the four have to be four machines for one language, and the check is that they agree.

Five expressions — a(b|c)*d, (a|b)*abb, [a-c]+d?, a*b*c*, and the blowup family at k = 3 — sixteen texts each, over a four-symbol alphabet. Eighty comparisons per machine, and a backtracking matcher as a fifth opinion.

All five agree on all eighty.

That is worth more than it looks because the five are built by genuinely different routes. The NFA is Thompson’s construction; the DFA is the subset construction over it; the lazy DFA builds the same subsets on demand and throws them away; the bit-parallel machine builds mask tables from the same states; and the backtracking matcher does not use the machine at all — it walks the parse tree.

So a disagreement would localise a bug to one of five independent pieces of machinery, and agreement across all five is a strong statement that the parse and the construction are right.

That fifth opinion is why the backtracking matcher is in the code at all. It is the slowest thing here by orders of magnitude and it is the only implementation that does not share the machine, which makes it the reference the other four are checked against.

What the numbers are per character of #

The unit needs saying because “operations” covers four different things across the four machines.

For the NFA: a state visit or a transition followed.

For the DFA: a table lookup.

For the lazy DFA: a lookup on a hit, or an NFA step’s worth on a miss.

For the bit-parallel machine: a word-sized or, counted once per word per operation.

None of those is the same amount of real work, and this collection’s habit requires saying so. A table lookup is a memory read that may miss cache; a state visit is a predicate test on a small object; a word or is a register operation.

So the ratios here are ratios of operation counts and would not be ratios of time. The comparison that is not one comparison is the essay this habit came from, and the direction it cuts is against the DFA: one table lookup into a five-hundred-state table is a memory access with poor locality, and forty word operations on a register are not.

Why the flat lines have to be checked #

Three of the four machines have a constant per-character cost and checking that they do is not a formality, because the first version of this measurement found one of them not being constant.

The DFA’s cost came out 4.85 times larger at 512 characters than at 4,096 — a machine whose step is one array read, apparently getting cheaper as the text lengthened.

The cause was the construction: it runs NFA steps, which charge the same counters a query charges, and the counters were not zeroed between the two phases. So the construction’s eleven thousand operations were being divided by the text’s length and reported as a step cost.

That is amortisation reported as a step cost, and it is invisible at any single text length. A measurement taken at one length would have reported a plausible number — 3.7 at four thousand characters — and nothing about it would look wrong.

What found it was sweeping the text length and requiring flatness. A quantity that ought to be constant and is not is a quantity with a term in it, and the term here was the construction leaking into the query.

The comparison that is not one comparison is the essay this habit came from, and this is the same lesson about a counter rather than about a unit: a counter shared between two phases measures both unless something separates them.

What each machine is for #

The measurements sort the four into uses.

The DFA is for an expression matched against a lot of text. One lookup a character is unbeatable and the construction amortises.

The NFA is for an expression matched once against a little. No construction beyond the machine itself, and a bounded cost per character.

The lazy DFA is for the case nobody can predict, which is most of them. It converges on the DFA’s cost given enough text and never pays the DFA’s construction up front — provided its cache is large enough, which a cache below the reachable set is about.

The bit-parallel machine is for a machine that fits in a word or two and an expression whose construction has no epsilon edges. Neither holds here, and its 15% is what a Thompson machine gives.

What a fifth machine would look like #

The four measured here are the four this collection builds, and there is a fifth in every production engine that is worth naming because it changes the picture.

A hybrid: run the lazy DFA, and if its cache thrashes or its state count exceeds a cap, fall back to the NFA simulation for the rest of the text.

That is what a real engine does and its cost is the minimum of two of the four lines, plus a branch. It never pays the full DFA’s construction, never thrashes indefinitely, and is never much worse than the better of the two.

It is not built here for the reason this collection generally gives about adaptive structures: an adaptive structure hides the boundary it adapts across, and the boundary — the cache size at which thrashing starts, the text length at which the table pays — is what the measurements are for.

A hybrid measured on its own would report one line that is always reasonable and would say nothing about where its two components cross. Where the table starts paying and a cache below the reachable set are the two crossings, and a hybrid’s implementation needs both.

The construction costs, side by side #

Worth collecting because they span two orders of magnitude and the plate’s bars do not.

NFA: 24 operations — one per state added.

Bit-parallel: 24 for the machine plus a mask table built in one pass over the states, charged as words.

Lazy DFA: 24 for the machine and then whatever the text demands, spread through the run.

Full DFA: 11,297 — 64 states, each requiring an NFA step per alphabet symbol, each of those a set walk with closures.

So the DFA’s construction is 470 times the NFA’s, for a machine 2.7 times larger in states and 44 times cheaper per character.

That ratio is the whole trade and it is a ratio a system can compute before deciding: the construction is O(S·σ·m) for S states, and S is what the subset construction discovers.

Which is the awkward part. S is not known until the construction has run, so a system deciding whether to build a table cannot cost the decision without making it — and that is why the lazy machine, which finds out as it goes, is what production engines ship.

The four numbers, and their conditions #

Ending with what a reader should carry, and every one of them has a condition attached.

43.7 operations a character for a set-carrying simulation — on a 24-state machine, over a text the expression’s prefix accepts entirely. Proportional to the machine’s size and to how much of it stays alive.

1.0 for a table lookup — always, on any machine, at any text length. The only unconditional number here.

37.2 for a word-packed set — on a machine fitting in one word, with a Thompson construction’s epsilon edges. On a Glushkov construction it would be a handful.

Between 5.8 and 50.9 for a lazy table — depending entirely on the text’s length and the cache’s size, which is two conditions rather than one.

And 11,297 against 24 for the construction, which is the number that decides everything else and which is a function of a state count nobody knows in advance.