What does a regex engine's lazy DFA cache store, and what happens when it reaches its memory cap?
answer
- determinise on demand, not up front
- one entry per distinct set of states
- subset construction, memoised
- capped because subsets can be exponential
- at the cap: flush, fall back, or refuse
basics
~20 sA lazy DFA cache stores subset-construction results computed on demand: each distinct set of live states becomes one deterministic state with its transitions. At the cap the engine flushes and rebuilds, or falls back to simulating the state set directly.
solid answer
~40 sDeterminising a pattern up front can produce up to `2^m` states for a pattern of m machine states, and most of them are never reached by real input - so the engine builds them lazily. The first time it needs the successor of a given state set on a given character it computes that set once, interns it, and stores the transition; afterwards the step is a single table lookup, so per-character cost stops depending on how many states are live. Because the table can still grow exponentially, it is capped. On reaching the cap an engine typically flushes the cache and rebuilds, or abandons the cache and simulates the state set directly. Matching stays correct and stays linear either way - only the constant factor changes.
go deeper
Know that some pattern engines remember the work they have already done for a given situation, so repeating that situation later is a lookup rather than a recomputation.
Explain that the cache is subset construction done on demand, keyed by a set of live states, and that the cap is there because the number of distinct sets can be exponential in pattern size.
Recognise the signature - correct results, unchanged output, sudden and sustained latency rise - and know the levers: cap size, splitting the pattern set, shrinking the combined pattern.
Decide how much memory the matching layer is allowed to hold, and whether degradation at the cap should be silent and slower or loud and rejected; that choice belongs in the platform contract.
## Why not determinise up front Subset construction turns a nondeterministic machine into a deterministic one whose states are **sets** of the original's states. For a pattern with m states there can be up to `2^m` such sets, so building the deterministic machine eagerly is a cost you may never earn back: the overwhelming majority of those sets are unreachable for the input you will actually see. A lazy determiniser sidesteps the problem by building only the part of the deterministic machine that this input walks through. ## What one cache entry actually is Each entry is keyed by **a set of live machine states** (plus any context flags the engine needs, such as whether the previous character was a line boundary). The value holds: - the **outgoing transition** for each input character or character class, pointing at another cached entry; - a flag saying whether this set contains an accepting state; - bookkeeping for eviction. The build is demand-driven. Starting from the closure of the start state, the engine asks for the successor of the current set under the next character. On a **hit** it follows a pointer - one lookup, constant work regardless of how many states are live. On a **miss** it does the subset-construction step once, interns the resulting set (so identical sets share one entry), records the transition, and continues. The cache is nothing more or less than **subset construction, memoised along the path the input takes**. ## Why there is a cap at all The cap bounds **memory**, not time. The time bound was already there: even with an empty cache the engine advances a set of at most m states once per character, so the scan remains proportional to input length times pattern size. What is unbounded without a cap is the table, because the number of distinct reachable sets can be exponential in the pattern size - and it grows fastest exactly where a large pattern set has been combined into one machine. ## What happens when the cap is hit Designs differ, and an engineer should recognise all three behaviours: 1. **Flush and rebuild.** The cache is cleared and refilled from the current position. Simple, and fine when the working set merely spiked. When the working set genuinely exceeds the cap, this becomes **thrash**: the engine repeatedly discards entries it is about to need again. 2. **Abandon the cache and simulate directly.** The engine falls back to stepping the live state set explicitly. Per-character work rises from one lookup to work proportional to the live set, so throughput drops - typically by a large constant factor - while the asymptotic bound holds. 3. **Refuse.** Some implementations surface an error or reject the pattern at compile time rather than degrade silently. Ecosystems differ on which of the three they choose, and on whether the cap is tunable. The point to be clear about in an interview: **none of these changes the answer**. A cache is a memo table; discarding it costs speed, never correctness. ## The three points on the spectrum | | Build cost | Memory | Work per character | |---|---|---|---| | Eager full determinisation | Up to exponential, paid before matching | Up to exponential, all of it | One table lookup | | Lazy cache with a cap | Paid incrementally, only for sets visited | Bounded by the cap | One lookup on a hit; a construction step on a miss | | Direct state-set simulation | None beyond compiling the pattern | Proportional to pattern size | Proportional to the live set | ## Operating it The failure mode is distinctive because it is **a throughput cliff with no error**. Records keep being matched correctly, results are unchanged, and per-record latency jumps and stays high for as long as the working set exceeds the cap. Things that push you over it: - combining a large pattern set into one machine, which multiplies the reachable sets; - patterns over a wide alphabet, which widens each entry's transition row; - long records that keep visiting new regions of the machine. The levers are correspondingly simple: raise the cap if memory allows, split the pattern set into several machines each with its own cache, or reduce the combined pattern size. Whichever you choose, the diagnostic that identifies the problem is the same - the symptom moves when the cap moves.
- Why is the cache keyed on a set of states rather than a single state?Because a nondeterministic machine can be in several places at once, and the deterministic equivalent of that situation is precisely the set. Subset construction makes each reachable set one deterministic state; two different sets are two different entries even when they overlap heavily, which is why the table can grow so much faster than the pattern.
- What does cache thrash look like from outside the engine?A throughput cliff with no error and no change in results: per-character cost jumps from one lookup to recomputing transitions, and latency stays high while the working set exceeds the cap. You confirm it with engine counters if they exist, or by moving the cap and watching the symptom move with it.
saying these in an interview costs you the question
- Says the engine builds the full deterministic machine before matching.
- Thinks hitting the cache cap can make a match incorrect.
- Believes the cap exists to bound match time rather than memory.
- Assumes deterministic states are as numerous as pattern states.
- Treats a cache flush as free because the pattern looks small.