Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

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

Đang mở
  • Có gì không ổn?
#485 3 bình luận 0 reaction 1 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

@johnml1135 đang làm issue này rồi.

Từ ngày 25/8/2026.

Đánh giá

Issue này chưa được đánh giá.

Mô tả

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.

Ngôn ngữ chính
C#
Star
29
Fork
17
Merge trung bình
2 ngày 5 giờ
Pull request đã merge (30 ngày)
7

Chuẩn bị môi trường

Chúng tôi chưa kiểm tra các tệp thiết lập môi trường của dự án này. Hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của sillsdev/machine

Tất cả issue của sillsdev/machine

Issue tương tự

Thêm issue về C#

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.