Analysis search is nogood-dominated on a template-heavy Bantu grammar; memoization yields ~6%, and the HasReachableRoot prune is absent from all refs

[MattGyverLee]

Summary

On a template-heavy Bantu grammar, the analysis search is dominated by repeated dead ends rather than by repeated successes, so the memoization landed in 8121049f..5d26fac6 yields ~6% instead of the ~4.5x recorded in memoization.md. The mechanism that would address this shape of workload — the Phase-5 HasReachableRoot lexical reachability gate — is documented as deliberately excluded, and is not present on any branch in the repository.

Filing this as a data point on a real grammar, not as a regression: everything below is measured, and the memo is behaving as designed.

Evidence

Grammar: a FieldWorks Bantu project (Mbugwe), 26 symbolic features, 17 affix templates, 2 unordered strata. HC config generated via GenerateHCConfig. Driver calls XmlLanguageLoader.Load + new Morpher(...) + ParseWord, tracing off. All configurations produce identical results (6 analyses, signature 408e52b3c3d6), so timings are comparable.

Memo diagnostics from Morpher, sequential cascade (MaxDegreeOfParallelism = 1), 3 words:

MemoHits=898   NogoodHits=81,038   TemplateMemoHits=1,445   TemplateNogoodHits=18

98.9% of memo activity is nogood recognition. The template-battery memo — which memoization.md identifies as "the real win: 93% of instrumented wall time" — hits only 1,445 times here, against the ~38,840 battery invocations / ~2,581 unique keys reported for the reference heavy word. There is little repeated successful subwork to reuse; the cost is breadth of failing exploration.

Consistent with memoization.md's own note that nogood "hits are cheap because guard clauses already reject fast", caching them saves little:

configuration	time	allocated
sequential, no memo (SINGLE_THREADED build)	128.8 s	—
sequential, memo (MaxDegreeOfParallelism=1)	121.5 s	109.1 GB
parallel cascade, no memo (default)	95.4 s	124.4 GB

Engaging the memo costs more (losing the parallel cascade) than it saves, on this grammar.

What does help here, for calibration

Same grammar and word set, so these are directly comparable. Allocation was reproducible to within 0.24% across runs; timings to within ~5%.

configuration	time	allocated	gen0
baseline (parallel, no memo)	138.7 s	124.7 GB	16,176
+ Server GC (DOTNET_gcServer=1)	78.3 s	124.6 GB	1,417
complexity-cap branch	57.0 s	54.1 GB	7,009
complexity-cap + Server GC	42.3 s	56.8 GB	634
feature/memoization-plus-cow + Server GC	43.7 s	43.9 GB	651

Two observations that may be useful beyond this grammar:

1. complexity-cap's VisitedStates alone (2.43x) beats Server GC (1.77x). Its own comment cites replacing a per-instance HashSet<State> (~1.17M allocations per word on Sena). For a nogood-dominated search that creates enormous numbers of traversal instances, this lands exactly on the hot path.
2. COW and complexity-cap reduce allocation at different layers (Word/Shape cloning vs FST traversal state sets) — 43.9 GB vs 54.1 GB, with equal wall time. They look complementary rather than overlapping, so combining them may compound.

Requests

1. Consider porting the Phase-5 HasReachableRoot gate, or an equivalent reachability prune. It is the only available lever that reduces the search rather than making each branch cheaper, and this profile is where it would pay. memoization.md records the decoupling rationale (keeping memo-on == memo-off a true invariant); a separately-toggled gate would preserve that.
2. memoization.md cites parse-optimization-archive as preserving the 23-commit chain including AnalysisScope.cs, AnalysisStateKey.cs and Phase-3b work. That branch is not present in this repository — HasReachableRoot appears in no ref. If it exists only locally, it is a single point of failure for the design record.
3. Optional: memoization.md could note that the documented speedups assume COW is present (ReplayOnto deep-clones without it), and that the win is contingent on template-memo hit rate. That would set expectations for grammars whose analysis search is nogood-dominated.

Environment

sillsdev/machine at fb30fed3 plus origin/master 5d26fac6, origin/complexity-cap c1d7db64, origin/feature/memoization-plus-cow ede36d02. Driver on .NET 10 (net10.0); note FieldWorks itself runs .NET Framework 4.8, so absolute figures there will differ.

Measurements are 1–3 runs per configuration on 3 words of one grammar. The large effects exceed the observed noise; the 42.3 s vs 43.7 s difference between complexity-cap and COW does not, and should be treated as a tie.

[MattGyverLee]

@johnml1135 — flagging this for you as the author of the memoization / complexity-cap work.

I don't have triage permission on this repo, so I couldn't set you as assignee; please reassign as appropriate.

The short version: on this grammar the memo is working as designed but has almost nothing to reuse (81,038 nogood hits vs 898 positive, 1,445 template-memo hits), so the documented speedup doesn't materialise. complexity-cap's VisitedStates and the COW branch both help substantially and at different layers. The concrete asks are in §Requests — chiefly whether the Phase-5 HasReachableRoot prune could be revisited, and that parse-optimization-archive appears to exist only locally.