Skip to content

HermitCrab analysis: finish each stratum as it completes instead of keeping every state until synthesis (per-word memory) #639

Open

Description

@johnml1135

HermitCrab analysis keeps every word of every stratum alive until the whole analysis ends, so per-word memory grows linearly with the number of distinct states reached. AnalysisLanguageRule.Apply adds each stratum's outputs to one results set, Morpher.ParseWord copies that into a queue, and only then does synthesis start. The only bound is MaxAlternatives, which counts alternatives, not bytes.

Recorded for later, in the same family as #593 and #595 (which shrink each word; this one is about how many are live at once). C# numbers for this mechanism do not exist yet; the numbers below are PanGloss ones. The C# structure is the same: breadth-first stratum search, a deduplicating output set, equivalents folded into a canonical.

Idea (the PanGloss approach, owner-approved there): finish each stratum's results as the stratum completes (hand its canonicals to synthesis, drop them once the next stratum has consumed them), keep a compact exact visited key per state instead of the whole word, and keep the full search tree only when tracing (Try a Word).

Trade-off: uncapped words give identical analyses. A capped word's partial result changes in PanGloss because work is spent in a different order. In C# the cap throws MaxAlternativesExceededException rather than returning partials, so the outcome is expected to stay "throws", but where it throws and the enumeration order of results would change; that needs checking. The compact key must be exact: a hash-only visited set can lose a parse on collision and is not proposed.

Reference implementation: sillsdev/PanGloss#249 and #250 cover the sharing and alternative-storage parts; the per-stratum finishing is the planned next step there.

Evidence (PanGloss, Rust)

Word mindeshi, Mbugwe grammar, peak resident set, one thread. Linear growth with work, about 14 MB per million steps before any fix. With shape and syntactic feature-structure sharing plus trail-stored alternatives (#249, #250): 50M cap 199 to 59 MB, 200M cap 1,152 to 267 MB, 1G cap 5,074 to 774 MB. Remaining memory is one word per canonical state, which is what this issue targets. At a 200M cap the search held 379,394 words: 94,010 canonical, 285,384 folded alternatives.

Where C# retains states (origin/master)
  • AnalysisLanguageRule.cs:26, :44 results accumulates every stratum's output; :24-25 input and temp sets.
  • AnalysisStratumRule.cs:150 per-stratum output HashSet; :140-144, :177-178 merge-key cache wordCache of canonicals.
  • Morpher.cs:186 new ConcurrentQueue<Word>(_analysisRule.Apply(input)) materialises all analyses; synthesis starts at :200.
  • Morpher.cs:97 MaxAlternatives (throws, AnalysisStratumRule.cs:156-159); no byte accounting.
  • AnalysisStratumRule.cs:142 merging (and so alternatives) is skipped while tracing, so a traced parse already holds every state; see HermitCrab analysis: keep equivalent-analysis merging on while tracing #565.
  • A fix touches Morpher.Synthesize* (:345-420), which also has a parallel path using the queue count.

Next: recorded for later, not scheduled. Measure C# peak working set on a heavy word (for example Mbugwe mindeshi) after #593 and #595, to see how much remains.

Activity

  1. johnml1135 commented on Nov 14, 2026

    @johnml1135
    CollaboratorAuthor

    Claude-drafted. C# measurement for this issue's open "Next" (peak working set on a heavy word), on a synthetic calibration word.

    hc.dll built from machine 4d9b454 (net10.0), grammar calibration/cal-work-cap/grammar.xml at fieldworks-parser-conformance 3ba5db1b, word x^20 milm y^6 (20 x's, milm, 6 y's), batch, under ulimit -v 16000000 and timeout 900: "Out of memory", exit 134, after 2:05 at 8.08 GB peak RSS, no result row. C# has no work cap and MaxAlternatives counts alternatives, not bytes, so this word is not bounded in C# either.

    The PanGloss port on the same word grows about 6 to 10 MB per million work steps (17 MB at 1M, 638 MB at 100M, 10.1 GB at 1G) and aborts near 10 GB at its default cap; the retained set there is the stratum accumulator's words (69%) plus alternatives (18%). Details: sillsdev/PanGloss#303.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    • Status
      🆕 New

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions