HermitCrab: cull analysis candidates at emission by stratum+shape lexical lookup (memory on truncation-heavy grammars)

Summary

Morpher.ParseWord materializes every word the analysis cascade emits (all strata) into analyses and only then runs LexicalLookup → synthesis → IsWordValid → IsMatch over them. LexicalLookup depends only on input.Stratum and input.Shape, so the "matches no root" verdict for each analysis word is already known the moment the cascade emits it. Culling those words at emission (from the candidate set only, not from the next stratum's input) is parse-identical and removes the dominant memory term on grammars with many zero-width/truncation rules. The same holds for LexicalGuess, which also reads only input.Stratum and input.Shape, so the cull remains correct with guessRoot = true by retaining a word when it matches a root or a lexical pattern.

This is a performance/memory report, not a correctness bug. No observable parse changes.

Where the memory goes

On an Aweti FLEx export (41 zero-width truncation morphological rules, a 24-level derivation chain; the grammar is a real project so it is not attached here, a synthetic conformance grammar with the same shape can be authored on request) a single word such as wemulujaʼjawype never leaves analysis: ~570 s and ~43 GB managed heap before the host dies, 0 deterministic FST traversals, 9.4 M nondeterministic ones. In our Rust port of the same algorithm the same words reach 5–7 GB uncapped; allocator tracing attributes 81–94 % of live bytes to the per-canonical alternatives produced by MergeEquivalentAnalyses (PR #493) hanging off analysis words that later fail LexicalLookup.

Real-word trace (Aweti ajkulula, merging disabled so every trail is visible): 227 analysis words reached LexicalLookup.

~159 of 227 words needed nothing but their shape to be discarded, yet all 227 (plus alternatives when merging is on) are held until analysis of every stratum completes.

Why culling at emission is parse-identical

1. Morpher.LexicalLookup (Morpher.cs) is SearchRootAllomorphs(input.Stratum, input.Shape).Where(LexEntrySelector); nothing else on the word is read until a root has matched.
2. Morpher.LexicalGuess matches input.Shape against _lexicalPatterns with input.Stratum.CharacterDefinitionTable; also stratum+shape only.
3. MergeEquivalentAnalyses keys on a state that includes shape and stratum, so every alternative folded into a canonical shares the canonical's lookup and guess verdicts. Culling a canonical culls its family; alternatives of a retained canonical must be kept because synthesis follows each alternative's own trail (the ạj rows above).
4. An analysis word emitted by stratum s has exactly two later uses: (a) lookup + synthesis, (b) input to stratum s−1. (a) is shape-only, so its verdict at emission equals its verdict at the end. (b) is why the test is currently deferred: a culled word must still be passed to the next stratum; only in the deepest stratum is it dropped entirely.
5. AnalysisStratumRule.ApplyMorphologicalRules yields every node before recursing, so the cull applies per node, and a node's failure says nothing about its children (their shapes differ). This is a storage cull, not a search prune.
6. Guess path: ParseWord runs LexicalGuess over origAnalyses only when Synthesize returned nothing. With retention = (root match ∨ pattern match) the retained set contains every word LexicalGuess can produce output for, so guess results are unchanged. Tie order of matches.Sort by morph count is already unspecified (unstable sort).

Proposed change (C#)

In AnalysisStratumRule/Morpher.ParseWord: as each analysis word is emitted, compute SearchRootAllomorphs(word.Stratum, word.Shape).Any() (and, when guessing, a shape-only lexical-pattern match), cached per (Stratum, Shape) within one ParseWord. Add the word to analyses only if retained; still feed it to the next stratum. Expose counters (emitted / culled / retained-by-pattern-only / cache hits) for verification.

Acceptance criteria

• Soundness and recall: identical parse multisets (not sets) on the existing HermitCrab test suite and on the Aweti/Sena/Amharic/Mbugwe/Indonesian batch corpora, with guessRoot both on and off, including at least one grammar with lexical patterns.
• Performance, reported separately: peak managed heap on the Aweti hard words before/after; the culled counter > 0 on those words and = 0 on words where every analysis matches a root.
• A regression test that fails when the cull is disabled (counter) and one that fails if the cull ever removes a word that LexicalLookup would have matched.

Related

• PR #493 (MergeEquivalentAnalyses) and PR #494, which introduced the alternatives that dominate the retained bytes.
• AnalysisScope MaxMemoWords (5d26fac6) bounded the memo; this report is about the un-memoized candidate set.
• Our Rust port of HermitCrab is implementing the same cull on branch feat/early-lookup-cull; its divergence-ledger entry will link back to this issue, and a C# PR can follow once the Rust counters and parity runs are in.

Open evidence gaps

• The 43 GB C# figure is one word on one machine; no C# allocator attribution yet.
• The 227-word trace above is with merging off; with merging on the same words collapse into fewer canonicals plus alternatives, so the culled count differs while the culled bytes are the alternatives.
• Whether the retained-by-pattern set is small enough to matter in guess mode depends on how broad a project's lexical patterns are; unmeasured.

Start with AnalysisStratumRule.ApplyMorphologicalRules and Morpher.ParseWord, then inspect Morpher.LexicalLookup and LexicalGuess to understand the proposed retention decision. Validate the change against the existing HermitCrab test suite and the named language corpora, with guessing enabled and disabled. Done means identical parse multisets, regression coverage for lookup soundness, and the requested emission, culling, retention, and cache counters.