A cache below the reachable set

The lazy deterministic machine is the answer to the subset construction’s exponential. It builds a state the first time a character asks for it and keeps a bounded cache, so an expression whose full table is five hundred and twelve states costs only what the text reaches.

The obvious question is what happens when the cache is smaller than that, and the answer is not a graceful degradation.

The measurement #

Four thousand characters, an expression whose deterministic machine has five hundred and twelve states, a cache swept from four to five hundred and twelve.

At a cache of 4: 52.6 operations a character, 2,039 flushes. At 8: 52.6, 1,014 flushes. At 16: 52.6, 502. At 32: 52.6, 246. At 64: 52.5, 119. At 128: 52.3, 55. At 256: 50.9, 23. At 512: 10.6, no flushes.

The plain non-deterministic simulation costs 52.7.

For scale: the machine has five hundred and twelve states and the text is four thousand characters, so a cache holding every state the text reaches is about a kilobyte of transition table on a binary alphabet. The caches below the cliff are all smaller than that and all equally useless.

That the useless region extends up to half the reachable set is the part worth carrying. A system sizing a cache generously — half of what it might need, on the reasoning that half the benefit is better than none — gets three per cent.

Flat, and then a cliff #

Across two orders of magnitude of cache size — four to two hundred and fifty-six — the cost does not move. Fifty-two point six to fifty point nine, which is three per cent.

At five hundred and twelve it falls to 10.6, a factor of five.

There is no gentle trade. The cache either holds the machine the text needs or it holds nothing useful.

Why #

The lazy machine fills its cache, finds it full, and throws the whole thing away rather than evicting an entry — which is what real engines do, because a partially valid transition table is harder to reason about than an empty one.

So a text reaching more states than the cache holds cycles: fill, flush, fill, flush. Two thousand and thirty-nine flushes at a cache of four, over four thousand characters — a flush every other character.

Between flushes the machine has a few states and almost every step is a miss, and a miss is an NFA step plus the bookkeeping of interning a subset. So the cost is the NFA’s plus overhead, which is what 52.6 against 52.7 is.

The cache is not merely useless below the threshold. It is slightly worse than not having one, and the difference is the bookkeeping.

The hit rate makes the mechanism legible without any reasoning about flushes.

At a cache of four: seven hits and 8,185 misses over four thousand characters. A hit rate of 0.09%.

At sixteen: nine hits. At sixty-four: twenty-four. At two hundred and fifty-six: two hundred and sixty-three, which is 3.2%. At five hundred and twelve: 6,659 hits and 1,533 misses — 81.3%.

So the cache is doing essentially nothing across the flat region and almost everything past the cliff. A structure whose hit rate goes from three per cent to eighty-one across one doubling is not a structure with a gradual trade in it.

Why the flat part is so flat #

A reader might expect a cache of two hundred and fifty-six, holding half the reachable set, to get about half the benefit. It gets three per cent.

The reason is that the flush discards everything. A machine that has built two hundred and fifty-five useful states and needs a two hundred and fifty-sixth throws away all two hundred and fifty-five, and starts from one.

So the useful work per flush cycle is the states built since the last flush, which never reaches a steady state where most steps hit. The hit rate at a cache of two hundred and fifty-six is 3.2%; at five hundred and twelve it is 81.3%.

An evicting cache would behave differently — it would keep the hot states and lose the cold ones, and its curve would be a gradual improvement rather than a cliff. That is a different design with different reasoning problems, and it is not what this collection built or what production engines ship.

The check that had to change #

The measurement in this essay corrected a check, and the correction is the same shape as several in this slate.

The first version asked whether every machine’s cost per character is constant across text lengths, which is true of three of the four and is the property that makes a per-character number meaningful.

It failed on the lazy machine — 5.40 times more per character at one length than another — and the failure is correct.

The repair available was to widen the tolerance until the lazy machine passed, which would have required a factor of six and would have accepted a machine whose step cost varied by that much for any reason.

The repair taken was to split the claim: the three fixed machines must be flat within fifteen per cent, and the lazy one must not be. Two-ended, and the second half is the finding.

Measured spreads: 1.03, 1.00, 1.03, and 8.74.

That is the third time in this slate a check has had to be split rather than loosened — a code word is at least one bit and where the sparse representation loses are the others — and the pattern in all three is that a check failing on one case out of four is usually a check whose claim covers a case it should not.

What the reach curve says #

The cliff’s position is the reachable set’s size, so the question becomes how much of the lattice a text reaches.

At 16 characters: 17 states of 512. At 64: 61. At 256: 188. At 1,024: 456. At 4,096: 511. At 16,384: all 512.

So a random binary text reaches the entire subset lattice within sixteen thousand characters, and reaches nine tenths of it within a thousand.

The lazy construction does not remove the exponential. It decides when it is paid.

That is a correction to how the technique is usually described, and it is the strand’s retraction. A lazy machine is described as making the state explosion go away; what it does is make it a function of the text’s length, and on a text of any size it is paid in full.

The cliff’s position doubling with k is the reason a fixed cache size is not a policy. At k = 6 the reachable set is a hundred and twenty-eight and a cache of two hundred and fifty-six is comfortable; at k = 8 it is five hundred and twelve and the same cache is on the flat part; at k = 10 it would be two thousand and forty-eight.

So one more (a|b) in an expression — five characters — moves a system from the good side of the cliff to the bad side, and a system with a fixed cache has no warning.

The miss rate is the warning. It is one counter, it is available at run time, and it separates the two regimes cleanly: 0.09% hits on the bad side and 81% on the good one.

What that leaves the technique doing #

The retraction is not that lazy construction is useless, and it is worth being precise about what it does buy.

It never pays for unreachable states. The full construction here builds five hundred and twelve because all five hundred and twelve are reachable; on an expression whose lattice is mostly unreachable, the lazy machine builds only what is needed and the saving is the difference.

It spreads the cost. A system with a latency budget per character prefers a hundred small charges to one large one.

And it never blocks. The full construction on an expression with a million states does not finish; the lazy one starts matching immediately and degrades.

Those are real and none of them is “the exponential goes away”.

What the retraction changes #

The strand’s own header expected the lazy construction to be the answer to the exponential, and it is worth stating what has actually been established instead.

The exponential is real and is met exactly by a family with a twenty-character expression. The exponential is in the expression.

A random text reaches all of it, within sixteen thousand characters on that family. So laziness defers rather than avoids.

And a cache below the reachable set is worth nothing at all — three per cent at half the set, and slightly worse than no cache below that.

Together those say that the lazy machine is a scheduling device rather than a space device: it decides when the construction happens, and given enough text it happens in full.

That is a smaller claim than the one usually made and it is not a criticism of the technique. Scheduling is worth a great deal when the alternative is blocking, and a machine that starts matching immediately and degrades is better than one that does not start.

What it is not is a way to match an expression whose deterministic machine will not fit. For that the answer is the non-deterministic simulation, and the lazy machine’s job is to find out that it is needed.

The two-ended check #

The strand’s rejection test requires both ends of the curve.

A cache of two must flush. Measured: 2,045 flushes over four thousand characters.

A cache of five hundred and twelve must not. Measured: zero.

And the small cache must cost more per character. 52.7 against 19.9, a factor of 2.65 at the parameters the test uses.

A check requiring only the third would pass on a cache that never flushed and was merely slower for some other reason. A check requiring only the first two would confirm that the flush counter works.

Together they say the cliff is where the reachable set is, which is the claim.

Where the cliff is, in general #

The cache has to hold the states a text reaches, and that is bounded by the whole lattice and reached in practice.

So the practical threshold is S, the reachable state count — the same quantity where the table starts paying cannot be known without running the construction.

A system therefore cannot size its cache from the expression. What it can do is observe: a machine flushing repeatedly has a cache below its S, and that is measurable in one counter.

The controller writes itself. Run lazily; count flushes; if the rate exceeds a threshold, stop using the cache and run the pure NFA — which costs the same and does no bookkeeping.

That is a better response than growing the cache, because S can be arbitrarily large and a cache that grows to meet it is the eager construction with extra steps.

A cliff is not a trade #

The shape of this curve is worth naming because it decides how a parameter should be treated, and this collection has both kinds.

A trade is a curve with a gradient: more of one thing buys less of another, continuously, and a system picks a point. A sampling rate is one — bits and steps on one frame draws it — and so is a compressed vector’s block size.

A cliff is a curve with a threshold: below it nothing works and above it everything does. This is one.

The two want different treatment. A trade wants tuning, a measurement of the workload, and a point chosen deliberately. A cliff wants detection — establish which side the system is on and act, because there is no point in the middle worth choosing.

That is why the response to this curve is a controller reading a flush counter rather than a tuned cache size. Tuning a parameter whose curve is flat over two orders of magnitude is spending effort where none of it lands.

Recognising which kind a parameter has is one sweep, and it is the sweep this essay is.

What a real engine does #

Production engines do exactly the above and it is worth saying so, because the measurement here explains a design that otherwise looks arbitrary.

They cap the cache by memory rather than by state count — a few megabytes, typically — and they flush wholesale rather than evicting. When the flush rate is too high they fall back to the NFA simulation permanently for that expression.

Every part of that follows from the curve. Wholesale flushing because partial tables are hard to reason about; the fallback because the flat part of the curve is no better than the NFA; the memory cap because S cannot be predicted.

What a character costs on four machines is where the four are put side by side and where the lazy machine’s non-constant cost first appears as a measurement. What the curve adds is that the fallback is not a safety net for a rare case — it is the correct behaviour over the entire flat region, which spans two orders of magnitude of cache size.

What a text that reaches less would look like #

The reach curve is measured on a uniform random text and that is the worst case for the lazy machine, so it is worth saying what a friendlier text does.

The reachable set is the set of state subsets the text drives the machine into. A text that never contains the pattern’s triggering character keeps the machine in a few states — on the blowup family, a text of all bs keeps it in the states corresponding to (a|b)* alone, which is a handful.

So a text with structure reaches less of the lattice, and the amount is a property of the text and the expression together rather than of either.

Real text is structured. A log file matched against a pattern with a rare trigger keeps the machine in a small region most of the time, and reaches the full lattice only if the trigger is common.

That is the reason a lazy machine works in practice on workloads where the arithmetic says it should not: the arithmetic is about the worst text and the workloads are not. And it is also why the failure is unpredictable — the same expression on a different corpus can move from the good side of the cliff to the bad one without anything about the system changing.

Where this leaves the four machines #

The strand has four machines and the measurements sort them.

The DFA is right for a reused expression with a small S.

The NFA is right for a short text and for any expression whose S exceeds the cache.

The lazy DFA is right in between and is the only one that finds out which case it is in.

The bit-parallel machine is a constant factor on the NFA and would be more on a construction without epsilon edges.

And the case not covered — a large S and a long text — has no good machine. The table cannot be built and the NFA costs m a character over a long input. That is the case a filtering scheme exists for, and it is not in this strand.

What the strand ends on #

Four machines, one language, and three crossings between them.

Where the table starts paying is the first: a construction cost against a per-character cost, crossing at about S·σ characters.

This is the second: a cache size against a reachable set, which is not a crossing but a cliff.

And the folklore is about a matcher is the third, which is not a crossing at all — two machines on completely different scales, one linear in the text and one exponential in it.

Three comparisons, three shapes: a crossing, a cliff, and a separation. Naming which is which is most of what the strand does, because the response to each is different — a crossing wants a decision, a cliff wants detection, and a separation wants one of the two never to be used.