Repository navigation
HermitCrab FST: use flat register arrays in the traversal (CreateInstanceMDArray 11.5% to 0.2% of profile, wall-clock only) #591
Description
The FST traversal in SIL.Machine.FiniteState allocates Register<TOffset>[,], a multi-dimensional array, once per match call and per traversal instance. This goes through the slow Array.CreateInstanceMDArray allocator. The change uses a flat Register<TOffset>[] of length registerCount * 2, with an index helper. Internally it uses Array.Copy and a flat-layout RegistersEqualityComparer. The public FstResult.Registers stays two-dimensional and is built once per accepting state. It is a .NET allocation fix and does not port to Rust. The change is on the archived branch perf/hc-optimization-archive (the helper RegisterArray.Idx is not on master).
Measured. On the heaviest Sena word, CreateInstanceMDArray fell from 11.5% to 0.2% of the CPU profile (8.6% of it was under Matcher.AllMatches, 2.3% in traversal setup). Wall-clock only, not attributed: it was not timed alone. Counts are unchanged by construction.
What a revival must do first. Time it alone, since the 11.5% is a profile share and not a measured saving. Keep the RegistersEqualityComparerTests equality and hashing coverage.
Record: see the archived write-up below
Ledger: #490 (comment); disposition: #490 (comment)
From #490 (closed).
Activity
johnml1135 commentedon Nov 2, 2026
Claude-drafted.
Related and unmeasured: the same traversal hashes each new visited-set key twice, in
ContainsthenAdd, and allocates aTupleper candidate. No profile on disk gives its share. This is not the SipHash cost PanGloss removed in sillsdev/PanGloss#123; C# has none.Next: on the heaviest Sena word, read the inclusive time of
KeyGetHashCode,RegistersEqualityComparer.GetHashCodeandHashSet.Contains/Addwhen this issue is timed. Under about 3%, drop it. At 5% or more, file an issue for a singleAdd.johnml1135 commentedon Nov 7, 2026
Archived from
docs/hc-optimization-ledger@ 2eba2f5 (docs/optimizations/flat-register-arrays.md), which is being deleted:Flat register arrays in the FST traversal
Status: retained on
perf/hc-optimization-archive, not merged (SIL.Machine.FiniteState:Register<TOffset>[]indexed byRegisterArray.Idx(r, k)replacesRegister<TOffset>[,]internally; thepublic
FstResult.Registersstays two-dimensional and is materialized once per accepting state).Portable: no; a .NET-specific allocation path.
The observation
11.5% of the heaviest Sena word's CPU profile was inside
System.Array.CreateInstanceMDArray, the slowgeneric allocator for multi-dimensional arrays, called from
Matcher.AllMatches(8.6%) and traversalsetup (2.3%): one
new Register<TOffset>[n, 2]per match call and per traversal instance.The change
Mechanical: flat arrays of length
registerCount * 2, a two-constant index helper,Array.Copyon theflat struct array, and
RegistersEqualityComparercomparing the flat layout. No behaviour change.Measured
CreateInstanceMDArray11.5% → 0.2% of the profile. Counts unchanged by construction. Together with theother allocation changes it contributed to the heaviest word's wall time; not measured in isolation.
RegistersEqualityComparerTestscovers equality and hashing of the flattened layout, while the existing FSAand FST suites cover accepting results and register materialization. The complete conformance-inclusive run
passed 603 tests with one expected host-privilege skip.