Skip to content

HermitCrab FST: use flat register arrays in the traversal (CreateInstanceMDArray 11.5% to 0.2% of profile, wall-clock only) #591

Open

Description

@johnml1135

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: https://github.com/sillsdev/machine/blob/2eba2f502338705a4d529d7034cecb6303db7f35/docs/optimizations/flat-register-arrays.md
Ledger: https://github.com/sillsdev/machine/blob/2eba2f502338705a4d529d7034cecb6303db7f35/docs/hermitcrab-optimization-ledger.md; disposition: https://github.com/sillsdev/machine/blob/2eba2f502338705a4d529d7034cecb6303db7f35/docs/hermitcrab-perf-2026-09-disposition.md
From #490 (closed).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    • Status
      🆕 New

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions