Repository navigation
HermitCrab analysis: a per-word root-search cache cut Sena work 21.3% in the port; C# repeat-lookup share unmeasured #600
Description
Claude-drafted.
A per-word root-search cache cut Sena work by 21.3% in the Rust port, but the C# record says repeated root lookups are only 0.5 to 3.3% of parser work. Whether C# has the same gap is unmeasured. Analysis branches that reach the same (stratum, shape) repeat the identical root-trie search.
Status: merged in the port; not built in C#.
What we know (port, work steps; parses identical on every completed word):
- Sena: 182,297,249 to 143,399,740 (-21.3%, measured before the edge index of HermitCrab analysis: an affix-rule index cut port work 11.8% on Cebuano; C# gain unmeasured #599 landed). Mbugwe -0.6%; Cebuano -0.1%, or -1.2% with an added enclitic; the other samples and fixtures about 0.
- It holds the raw ordered trie result per word, keyed by exact (stratum, shape), capped at 1 MiB (peak 1.04 MB on Sena), and is discarded after each word. Lexical-entry filtering, overlay and dedup still run on every lookup. A capped or timed-out search is never cached. A result is stored only if its search cost more than a hit is charged, so no path costs more.
- Ledger row 28 closed a similar C# cache: untraced C# makes 1.13 to 1.49 calls per distinct (stratum, shape).
- Inferred: the port's larger gain comes from charging a lookup per trie edge, which makes repeats dearer than in C#'s unit.
Not known: the share of C# work spent on repeated lookups on Sena.
Proposed change: measure that share first, on hc.dll, in lookups and work steps. Port the cache only if the share is material, and then only after an explicit decision against the no-memoization rule (ledger row 38): it is a bounded memo.
Related:
- PanGloss: Per-parse exact root-search cache, hard-capped at 1 MiB PanGloss#92 (closed by PR perf(lookup): per-word root-search cache, capped at 1 MiB (#92) PanGloss#96, merged).
- HermitCrab analysis: an affix-rule index cut port work 11.8% on Cebuano; C# gain unmeasured #599 (open); HermitCrab optimization round record: what was tried, and a faster package that is not mergeable #490 (closed PR, retired record).
Next: count untraced repeated (stratum, shape) lookups and their work on Sena in hc.dll.
Evidence -- numbers, method
From PanGloss PR #96 and its lane report (single-threaded --stats).
| Grammar | Work before | Work after | Peak cache |
|---|---|---|---|
| Sena | 182,297,249 | 143,399,740 (-21.3%) | 1,042,524 B |
| Sena, with the port's edge index (#599) and cache together | 182,297,249 | 138,405,255 (-24.1%) | 1,042,524 B |
| Mbugwe, 1,636 completed words | 35,582,069,812 | 35,354,992,356 (-0.6%) | 1,048,396 B (cap 1,048,576) |
| Cebuano base | 5,395,400 | 5,392,090 (-0.06%) | 427,336 B |
| Cebuano with enclitic | 6,340,178 | 6,265,316 (-1.2%) | 427,336 B |
Cebuano rows compare against a build with the edge index but no cache. Seven Mbugwe words never complete on either build and are unverified. Cache bounds are conservative allocation estimates, not allocator measurements.
Surprising findings -- why this reopens a closed ledger row
Row 28 closed the cache because trace mode (which disables merging) had inflated the lookup count to 97,575 over 56 shapes. Untraced, repeat-lookup work was 0.5 to 3.3% of parser work (10.4% only on row 25's pre-fix bug); lookup was 1 to 12% of parser work. PanGloss merged a narrower version anyway: per word, exact key, capped, discarded after each word.
Lookup gap (search-cost round, open lead 14): on the slowest word of one private project, the port made 18 lookups on C#'s export against C#'s 49. Parses were identical and the cause was not investigated there. Ledger row 24 later attributed a related gap (18 lookups against 1,655 on the port's own snapshot) to a loading difference, not search. Neither figure is evidence about repeats in C#.
Activity
johnml1135 commentedon Oct 31, 2026
Claude-drafted. Reconciliation with the closed #490 ledger. Ledger row 28 closed the root-result cache because repeat lookups were only 0.5–3.3% of work. PanGloss merged a narrower version anyway (PanGloss#96): per word, keyed by exact stratum and shape, capped at 1 MiB and discarded after each word. It is the owner's only approved memoization exception. Open question for C#: on the slowest Sena word, HC-Rust makes 18 root lookups and C# makes 49 (search-cost round, open lead 14). If C# repeats lookups more than the port, the gain here may be larger than the ledger's figure. Measure lookups and work steps on hc.dll before building.
[-]HermitCrab analysis: measure repeated root lookups per word; bounded per-word root-search cache[/-][+]HermitCrab analysis: a per-word root-search cache cut Sena work 21.3% in the port; C# repeat-lookup share unmeasured[/+]