Repository navigation
Analysis search is nogood-dominated on a template-heavy Bantu grammar; memoization yields ~6%, and the HasReachableRoot prune is absent from all refs #485
Description
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:
complexity-cap'sVisitedStatesalone (2.43x) beats Server GC (1.77x). Its own comment cites replacing a per-instanceHashSet<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.- COW and
complexity-capreduce allocation at different layers (Word/Shapecloning 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
- Consider porting the Phase-5
HasReachableRootgate, 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.mdrecords the decoupling rationale (keepingmemo-on == memo-offa true invariant); a separately-toggled gate would preserve that. memoization.mdcitesparse-optimization-archiveas preserving the 23-commit chain includingAnalysisScope.cs,AnalysisStateKey.csand Phase-3b work. That branch is not present in this repository —HasReachableRootappears in no ref. If it exists only locally, it is a single point of failure for the design record.- Optional:
memoization.mdcould note that the documented speedups assume COW is present (ReplayOntodeep-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.
Activity
MattGyverLee commentedon Aug 22, 2026
@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'sVisitedStatesand the COW branch both help substantially and at different layers. The concrete asks are in §Requests — chiefly whether the Phase-5HasReachableRootprune could be revisited, and thatparse-optimization-archiveappears to exist only locally.johnml1135 commentedon Sep 16, 2026
An independent data point, and a candidate cause: PR #494/#493 remove most of the work the memo exists to cache
Measured on HC-Rust (PanGloss), the Rust port of
SIL.Machine.Morphology.HermitCrab, not onhc.dll. C# remains our oracle, so nothing below is a measurement of C# — it is evidence about the shared algorithm, and a prediction for C# that someone with the C# harness can falsify cheaply.The memo's value collapsed at one commit, and it is the port of #494 + #493
We bisected the memo's own value (
t_memo_off / t_memo_on, paired and interleaved in the same binary) over a 300-word Sena corpus, uncapped, single-threaded:Ten other candidate commits were measured (memo word/byte caps,
apply_mrules/apply_templatesstreaming,Rc-shared alternatives, push-time alternative pruning, memo-key count saturation). None reproduces the effect; the caps only refuse future stores, and the representation changes touch the live frontier rather than memo-able subwork.The deterministic evidence is better than the timing
A step probe across the same boundary — steps being the algorithm's own unit of work, so this does not depend on wall clock:
A 91.5% reduction in the work gap the cache exists to close. The analysis changes remove the redundant work rather than making it cheaper to re-do, so there is very little left for a cache to save. What remains does not pay for the memo's own per-lookup cost: our state key clones a
Shape, two feature structures and a rule-count map on every lookup, hit or miss.Where that leaves the memo in the port
On a pathological template-heavy grammar (Aweti, 44 words, 200,000-step cap) the memo is now a net cost: 21,262 ms with it against 9,683 ms without, and 362.7 MB peak against 43.4 MB. Every capped word consumes exactly 200,000 steps by definition, so the per-word figures are directly comparable work-for-work — 1,136 ms with the memo against 363 ms without, i.e. each step is about 3x dearer with it on.
This is the same shape you reported, further along: your Mbugwe measurement found engaging the memo cost more than it saved. We now have a mechanism for why, and a commit that marks the transition.
The prediction, and how to falsify it
#493 merged on 2026-09-14, after this issue was filed, so the ~6% here predates it. #494 is still open. Our port applied both together, and we could not isolate them within the same five-pair benchmark — a separate five-grammar attribution run points at #494's
PriorityUnionas the stronger contributor, but that used a different harness and is not reproduced in this bracket.So, concretely:
master(which now has Fix bug in MergeEquivalentAnalyses #493) should already show less than 6%.If either fails to reproduce, the sub-attribution is wrong and we would want to know.
What we have done with it
We are removing memoization from the Rust port rather than keeping a mechanism that costs time and an order of magnitude of memory to save work that no longer exists. That is a deliberate divergence from C#, recorded in our ledger and reported here rather than kept quietly on our side.
It is not free, and we would flag the same cost for C#. The memo saves steps, and under a step cap that is what lets some words finish at all — 8 words in our Aweti corpus complete only with the memo on. Removing it loses them. Anyone weighing the same change under a step or time budget should price that, not just the wall clock.
Limits of this evidence
hc.dll. Different language, allocator and GC behaviour; the C# figures could differ in magnitude even if the mechanism holds.johnml1135 commentedon Sep 16, 2026
Follow-up: I've opened #509 with the full bisect and a concrete proposal to measure and likely remove the memo in C#, rather than leaving that buried in a comment here. The short version is that the memo's value collapses at the port of #494 + #493 (91.5% reduction in the steps it avoids), and the falsification test is cheap: re-running the Mbugwe case on current \master\ should already show under the ~6% reported here.