Skip to content

HermitCrab feature structures: allocation-free ValueEquals for frozen flat trees (no isolated measurement) #588

Open

Description

@johnml1135

Freeze marks a FeatureStruct as a flat tree when every reachable value is a SimpleFeatureValue, no value instance repeats and no nested FeatureStruct exists. FeatureStruct.ValueEquals then compares two such frozen structures by feature count, key and value, with no visited-pair set. This is equivalent to the general walk, because a flat tree cannot trigger its reentrancy or cycle guard. Shared leaves, nested structures and cycles use the general path. A test-only entry point lets randomized tests compare the two paths. The change is on the archived branch perf/hc-optimization-archive.

Measured. Nothing in isolation. The same profile that motivated traversal-state reuse put feature-structure equality and freezing at 13.7% of wall time on the heaviest Sena word. The record claims no standalone ratio.

What a revival must do first. Time it separately from the other feature-structure changes, in unification or visited-set operations avoided. Keep the randomized cross-check against the slow path (FeatureStructTreeFastPathTests, FeatureStructValueEqualsFreezeTests).

Record: https://github.com/sillsdev/machine/blob/2eba2f502338705a4d529d7034cecb6303db7f35/docs/optimizations/feature-struct-frozen-tree-equality.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