Repository navigation
HermitCrab FST: two-pass nondeterministic traversal (rejected: 2.3x traversal instances, arc checks down only 1.6%) #596
Description
A port of the investigate_linear_traverse approach. It first merged traversal instances by state, position and variable bindings, then rebuilt captures. It was removed from production.
Measured. On 45 Sena words it used 2.3 times as many traversal instances, cut arc checks by only 1.6%, produced more duplicate matches and raised word clones by 27%. Conformance fixtures pointed the same way.
Why rejected. HermitCrab's traversal already pools instances, and its patterns lack the repeated-group shape needed to repay the capture rebuild. Reopen only for a corpus whose automata have substantial equivalent active-state convergence, with a census showing that capture reconstruction is cheaper than the current traversal. See also the (State, AnnotationIndex) record, which drops bindings from the key and is unsound for the same captures.
Record: see the archived write-up below
Ledger: #490 (comment); disposition: #490 (comment)
From #490 (closed).
Activity
johnml1135 commentedon Nov 7, 2026
Archived from
docs/hc-optimization-ledger@ 2eba2f5 (docs/rejected-optimizations/two-pass-nondeterministic-traversal.md), which is being deleted:Two-pass nondeterministic traversal
Status: measured negative and removed from production.
This port of the
investigate_linear_traverseapproach first merged traversal instances by state, position,and variable bindings, then rebuilt captures. HermitCrab's existing traversal already pools instances, and
its patterns do not have the repeated-group shape needed to repay the extra bookkeeping.
On the 45-word Sena battery the alternative used 2.3 times as many traversal instances, reduced arc checks by
only 1.6%, produced more duplicate matches, and increased word clones by 27%. Conformance fixtures pointed in
the same direction. Toggle hooks, alternate algorithms, and counters were removed; only this result remains.
Reopen only with a corpus whose automata have substantial equivalent active-state convergence and a census
showing that capture reconstruction is cheaper than the current pooled traversal.
See also
state-position-traversal-dedup.md, which drops bindings from the key instead of keeping themand skips capture reconstruction entirely. It is cheaper than this experiment and unsound for the same
reason this one was expensive: the captures are load-bearing for
AllSubmatchescallers.